DiplomacyRoadmapJohn Newbury 4 October 2010 |
Home > Diplomacy > Cogitation > Roadmap
AI in the Game of Diplomacy: Roadmap
NB: The timescales below are unduly optimistic, for instance the release date for BlabBot 3 (BB3) has already passed. Just as fusion power and manned landings on Mars are always 30 years away, so the release of BB3 has always been 3 months away. Apart from the usual reasons for deadlines being missed (more than once!), BB has been radically revised in during 2009, thereby requiring many unanticipated consequential revisions. Until these issues have been resolved, and BB3 has actually been released, I am (clearly) unable make reasonable estimates of timescales. I have, at least, frozen further development until released. So, as politicians sat: I shall release BB3 when I judge the time is right to do so – and not before! Only then shall I revise the estimated timescales; hopefully being more accurate in future.
Here is an outline roadmap plan of my future work on my Diplomacy (TinKing) project.
The first release BlabBot (BB) source, comprising all my existing code that I intended to release as source, handing all forms of DAIDE press, a few experimental exotic press extensions, and much else besides to support the foundations of a DAIDE bot (not just press) – as hinted at in many of my posts in DipAi. The most important part, which will form the base of DeepLoamSea (DLS) version 2, but is offered for use in other bots, is called the BlabBotBase (BBB).
BB was mostly written and tested, but some recent important revisions and enhancements now to be completed and checked. Some documentation, now mainly on this web. Further deferral due to problems of how to evaluate "expectations" due to observed press, and improvements to future such evaluations – see below – now probably solved in outline. Also made a major restructuring, which should greatly simplify and slightly improve efficiently of core press classes (combining many classes). Estimated release: end 3Q2009.
All standard DAIDE syntax and semantics;
BlabBot 3 still only uses level 10 press in earnest – albeit in very slightly more general way. But, for testing and demonstrating its latent abilities, and other press bots, it can be set to use all levels up to and including 8000, handling any number of recipients.
Optionally reduce the press level (accepted or used) below that allowed by Server.
Extensive parameterization, settable by command-line arguments;
Extensive extensible hierarchical classes for all forms of press and other concepts, such as powers, provinces and sites (power/coast/unit-type combinations).
Separation of syntactic and semantic representations of press.
Common code for input and output of press.
Extensive validation tests for press received or about to be sent.
In-memory history of press and orders, with logical- and real-timestamp, for AI analysis. Also prepares for BlabBot 4 enhancements, such as loading and unloading the game-state, and rolling it forward or backwards to any turn (e.g., see Viewer).
Exotic press syntactic and semantic extensions. (Useful for internal logging, dumping and loading, etc., even when not used to extend press. Also allows a Mapper/Viewer user to send a note to a bot's log.)
Example, but also logical and potentially useful, extensions to official syntax (exotic press), such as the TransactionStatement.
Extensive negotiation methodology and tools. Using standard syntax, includes methodology and tools properly to ensure that all parties have the same belief about what has and has not been, or no longer is agreed; any party can withdraw "agreements", or revoke (by negotiation or unilaterally) previously agreed agreements ("treaties" if PRP or INS; "accords" otherwise). Also includes methodology and tools properly to specify exceptions to a situation (a.k.a. an "offer"), such a specific DMZ except for a set of specific incompatible XDOs.
Game-time (turn) limitations on press, including default periods (depending on type of situation), overrideable by FOR.
Extensive canonicalization of semantically equivalent press, e.g., PCE(y x) => PCE(x y), where the ordering is arbitrary, but consistent in a given instance of the bot; NOT(NOT(x)) => x, which is simpler. Helps eliminate redundant processing and coding.
Recognition of "necessity", such as, for any parameters, ALY(w x y)(z) contradicts ALY(x z)(v); XDO(x MTO y) exempts XDO(z MTO y); ALY(x y z)(w) entails PCE(x y); PCE(x y z) allows PCE (x y). (Four operators to deal with positive and negative senses of each argument.) Incorporates dominance hierarchies of expressions, i.e., INS > PRP > SUG; FCT > THK. Various uses, including checking for breaches of agreements, and recognition of situation exceptions.
Producing "clumped" forms of expression from "scattered" ones, e.g., AND(DMZ(x)(y))(DMZ(x)(z)) => DMZ(x)(y z). (This can sometimes avoid sending higher level forms, such as AND, which may not be understood, or tend to be less easily understood by a human. The scattered form may have been produced by a press generator that does not realize the inherent redundancy; it is a common result of canonicalization.
FOR uses relative turns internally, to be compatible with default periods (aiding canonicalization) and more meaningful in most cases (two essentially equivalent situations appears the same in different turns).
A tool to try find some way of expressing certain concepts, within any known constraints on press ability of all recipients.
Self-monitoring/prioritizing "agents" to manage use of resources, including CPU and network, to avoid under or overload of these, and the server and recipient players. Methodology and tools to help fully utilize multi-core computers. Dummy load generator for testing. Agents to generate or control other agents.
Methodology and tools to help give good response, even when running CPU-intensive work, both to DAIDE messages and to windows redrawing, etc., preparing the way for more sophisticated use of windows (for monitoring an control, e.g., see Viewer). Illustrated by a "state" indicator, and a button to control whether to offer a draw, thereby allowing a game to end immediately all are of a like mind.
Methodology and tools to fully utilize, yet help avoid overrunning, real-time limits, and to mitigate problems when it does happen (due to an operating system glitch, or game suspension, say). Caters for Deadline Stops on Disconnection.
Flow control to regulate sending press to avoid overloading recipients.
GOF control to avoid premature end of turn before incoming press has been analysed, or outgoing press or orders have been accepted by Server.
Detection of looping forwarded press.
Central overall monitoring and time-oriented activation – periodically, or after one or more applicable events.
Convoy generator, with hooks for heuristic pruning.
Table lookup of minimum number of non-convoy steps, if possible, between any pair of provinces or sites (province with unit type or coast).
Power token included on the bot's own window when known.
Optional extensions to the bot's name (on own window and in Server – useful when clones are using different settings).
Extensive self-checking regression tests, including over 900 press test cases, which can also be sent to test other clients.
Optional random (junk) press generation for testing self and other bots, including options for most complete/uniform and most plausible.
Inhibition of press that is known to to be unacceptable to specific sets of powers (camps), due to previously received HUH or TRY message (or could be set by AI code upon detection of misinterpretation). Unacceptable press may be a single form, or specific nested pair, such as AND(ORRx)(y))(z) (needed for press levels 30 and 40, but is generalized in case, say, SUG(PCE(x)) were rejected, even though SUG and PCE were allowed in other contexts), or where FOR is accepted but not a FOR(x)(FOR(y)(z)).
Rigorous memory management, avoiding any memory leaks (so any new leaks can readily be detected).
Framework for modifying expected future orders due to observed press, and improving future such modifications, later in this game and/or future games.
Logging facilities now thread-safe; nameable log files (allowing for multiple clones); time-stamped entries; keys to indicate more kinds of record.
Extensive error handling to aid diagnosis and recovery, including attempted access violations, trapped so that the call stack is available to Debugger.
Choice between halting to diagnose a detected error (during development) or trying to tidy up and limp on (during a tournament).
Diagnostic dumping facilities for all main data classes, including bulk dumps of all press sub-expressions observed, views expressed and agreed.
Re-entrancy controlled to enable modal (waiting) dialog boxes (e.g. AfxMessageBox) to be used while processing DAIDE messages and timer events. (Useful during debugging.)
Hash tables.
Improved random number generator (by Takuji Nishimura and Makoto Matsumoto) with supplementary facilities.
Extended string, vector and other utility classes.
BlabBot 4 is partially documented outline concept and plan. Estimated release: end 4Q2009.
Planned to include the following within the BBB part (no changes are proposed to the bot-specific part):
A basic DEMO system for testing and comparing bots. Initially based on a tidy-up of DTDT. Bespoke code, where needed, for running known bots. An initial comparison of known bots will be summarized, with raw data available in an Access database; periodically updated.
DeepLoamSea (DLS) has some outline design and experimental code fragments (see Cogitations). Estimated release date: end 3Q2010.
DeepLoamSea is planned to include:
A total rebuild, based on BBB, exploiting all its main facilities (since I have gone to the trouble of implementing them!).
make some practical use of all forms of press, both generating and responding in a practical way to at least some usage of each kind (the unreleased version 1 being little more than a ConsBot, and does not use press).
Implement agents that can exploit multiple CPUs.
Implement Monte Carlo simulations of play and game-theory.
Implement heuristic measures to evaluate as many aspects of Diplomacy play as practicable, as described (informally) in the the literature.
Implement manual and automated optimization of heuristics (advising/learning/evolution).
Try to give it good advice on initial settings for high level aspects, to give it a good start (expend little effort on low level aspects).
Extensive extensive automatic optimization against known bots, using DEMO.
BlabBot 5 is partially documented outline concept and plan. Work will now only begin after release of a reasonable (even if not world-shattering) version of DeepLoamSea. Estimated release: end 4Q2010.
Mapper-like interactive interface to BBB (Viewer), but with better integration with its extra facilities, and new facilities, such as:
functional equivalents to all Mapper facilities;
dynamically change command-line options where appropriate;
save/load options to/from file(s);
save/load facility (for continued play or post game analysis) of all essentials, and framework for including heuristic analysis where convenient to do so;
dynamic interface: normally as automatically generated dropdown menus (to facilitate easy change during development); options moved to the top when used (for faster access); unusable options greyed out (such as when not allowed at current level or not understood by intended recipient);
easier means for humans to express a change to their own view on any declaration, e.g., to cancel a proposal (avoiding an awkward workaround with Mapper, which does not allow full range of legal (or at least otherwise usable) DAIDE, such as sending a reply to your own press, i.e., an unsolicited reply);
ability to switch between, or have a combined, human and bot player, with human giving hints (on orders and/or press) to the bot and vice versa;
display currently declared opinions and agreements with each group of powers (camps);
display broken agreements;
display the logs during play;
real-time time-stamps displayed on press and turn ends;
scroll the map when too small to view properly – by scroll bars and/or drag;
display estimated of scores for each player;
toggle between display of formal DAIDE syntax and a natural language interpretation;
structured layout of complex press (natural and formal), when received and during preparation;
editing and merging facilities to easily and accurately derive new press from old, without always composing from scratch;
templates for translating DAIDE to and from natural language as a text file, so other languages could be implemented (using a simplified internationalization facility for strings in general);
roll units, orders and press back and forward to view different turns;
filtering and ordering options when displaying press, orders and logs;
optional auto submit when near deadline;
optional auto FWD and/or BCC of sent/received press;
optional infill of provinces and/or larger and/or power-specific symbols to aid colour-blind users;
optional bleep and/or flashing when a message arrives;
A framework/demonstration implementation of all remaining proposed DEMO facilities.
Optional natural language translation of DAIDE also in logs.
Optional assignment of players to teams (for live use, or to simplify certain testing, e.g. by allowing reruns with the same set of "friends"). BB would prefer team members, if any are specified and remain, to those with peace agreements.
Framework for representing beliefs.
Automatically identify and log broken agreements.
A command-line argument to specify groups and/or teams. If teams then the bot is allowed to use the information to improve it play (e.g., -SG"ENG,FRA;AUS;TUR,RUS,ITA", no spaces); if groups then the information is only allowed to be used for such things as logging. Each element can be a name; must be unique for its type; that is, each type has its own namespace. Any unspecified powers are in Group0 (default). Any order of groups (but number from 1 if not specified) and any order within a group. Named groups have prefix; for example, '-SG"Fred:ENG,FRA,Joe:AUS;TUR,RUS,ITA"'. (No spaces, -ST if a team; one of each kind or argument may be specified.) A bot knows its power, and hence the group or team it is in. Each character also owns its own one-member team. Empty groups are allowed in a game, but invalid (considered to be Group0) if not matching number requested in the group (or no such group).
Per-camp concept activation stacks to help press generators maintain coherence in discussions for better agreement of differences of opinion. (A CONSIDER(x) exotic press form could use this tool in a minimalist way merely to hint to the recipients to discuss concept(s) x; IGNORE(x) could do the converse – but may be difficult, like being told not to think about elephants!)