Diplomacy
|
Home > Diplomacy > Cogitations > Transformation
Cogitations on AI in the Game of Diplomacy: Transformation
Here is a brain dump of full details my current Cogitations about Transformation of DAIDE expressions and their internal representations. (Later Cogitations override earlier ones if contradictory.)
Canonicalization is useful to help avoid processing more than once what is effectively (semantically) the same thing, just because it appears to be different (in DAIDE language, or as represented internally). An obvious example is NOT(NOT(x)) ==> x. No point in analysing and using RHS, and later maybe doing the same with LHS. E.g., suppose RHS is transferred as a FCT or THK, then if LHS is later transferred in a similar context, no further information is transferred; if RHS is proposed or replied to, doing the same with LHS is redundant. (Repeated information is not defined to have more emphasis, say. BlabBot notes it as "nagging" presumed antisocial behaviour and traps any such attempted behaviour in itself.)
Until today I (in BlabBot we are one!) had been canonicalizing NOT(AND(x)...(NOT(y))) ==> ORR(NOT(x))...(y) and NOT(ORR(x)...(NOT(y))) ==> AND(NOT(x))...(y). I.e., moving NOTs inward until they only contain "predicate" formulae, such as PCE(x) or XDO(y). Note that this tends to reduce the number of NOTs by one, assuming they are randomly distributed (as illustrated above), and can eliminate them, as in NOT(AND(NOT(x))...(NOT(y))) ==> ORR(x)...(y)), but can increase them, as in NOT(AND(x)...(y)) ==> ORR(NOT(x))...(NOT(y)).
It is a useful fact (e.g., allows common code) that AND and ORR are "duals" ("isomorphs") of one another, in that any rule that applies to one applies to the other if AND and ORR are interchanged everywhere.
In a similar vein, I had converted NOT(FOR(p)(x)) ==> SOME(p)(NOT(x)), albeit I have to do the reverse to produce standard DAIDE syntax before transmission. [In DipAi I have referred to "SOME" as "FORSOME".] As with AND/ORR, this allows NOTs to move inward until they only contain predicate formulae; it may reduce or increase the number of NOTs, but should tend to remove one on average. Note that FOR and SOME are also duals of one another, so NOT(SOME(p)(x)) ==> FOR(p)(NOT(x)).
Like SOME, ORR is clearly redundant, but both are useful conceptually at least for humans! But see below.
----------------------
I have been irked for a long time that, like FOR, CHO did not have a similar dual form that would allow an outer NOT to be moved inward. (CHO is not a predicate, like PCE or XDO, but a "constructor", more like AND and ORR. Indeed, CHO can be canonicalized to combinations of AND/ORR, and in simple cases I do so. Recently, I decided to invent such a dual, AVOID, such that NOT(CHO(r)(x)...(NOT(y))) ==> AVOID(s)(NOT(x))...(y), where s is the "complement" of r, i.e., the same offset from 0 as originally from n, the number of terms. I.e., whereas CHO requires the number of true terms to be within a specified range, AVOID forbids the number of false terms being in a (different) specified range. This maintains the potentially useful analogy with AND/ORR regarding negating inner terms, e.g., NOT(CHO(n n)(x)...(NOT(y)) == NOT(AND(x)...(NOT(y)) == ORR(NOT(x))...(y) == CHO(1 n)(NOT(x))...(y) == AVOID(0 0)(NOT(x))...(y). (Unlike SOME, I do not currently find AVOID an obviously helpful concept myself but felt that a bot probably might, i.e. that it might be useful in programming!)
An alternative, simpler but less symmetrical or analogous dual would merely forbid the number of true terms [the same terms as before] being in a [the same] specified range. It is not obvious whether such a transformation would really have weaker properties than my AVOID, above. This would also reduce the number of NOTs by one (always, in this case, rather than just on average). (Just like "opposite", "dual" can have more than one interpretation!)
----------------------
Taken to its logical conclusion, maybe there should be a negative version (at least internally) of every kind of premise, i.e., including predicates, such as PCE and XDO, too. That would eliminate all NOTs!
However, that would add a lot of complexity, nearly doubling the number of classes of premise. Indeed, often the positive and negative versions can use a lot of common code, with negation, where necessary, done separately, using code common to all premises. An example is AND/ORR and FOR/SOME, which share a lot of code in BlabBot, taking advantage of their being duals in future, potentially CHO/AVOID too. Recently, coding "expectations" (of future order-sets) due to (crisp) XDO and even (fuzzy) PCE, I found that I could use common code for positive and negative cases positive versus negative senses being dealt with by common code for all premises.
Consequently, generalizing, for consistency, I have now decided to take a radical approach and go in the opposite [sic] direction. Not only not implementing negative versions of any predicates, and scrapping AVOID and SOME, but also avoiding use of ORR! Of course, I need to keep ORR to understand all input press and, indeed, I would transmit it (as now) when it is simplest for expressing a premise, i.e. to minimize number of NOTs, e.g. ORR(x)...(NOT(y)) rather than NOT(AND(NOT(x))...(y)), and NOT(ORR(x)...(y)) rather than AND(NOT(x))...(NOT(y)). But I now think it would be simpler not to use ORR at all, except during i/o. (SOME and/or AVOID could be added to the language if helpful to human players, but like ORR, I now do not think they are of real value to bots so they are, therefore, an undesirable complication for them! Perhaps, instead, Mapper and/or my proposed Viewer should do such translations for humans, if helpful to them.)
To avoid redundant processing of semantically equivalent forms, and multiple near-clone functions or more complex code, canonical forms are used, except just before or just after transmission. ORR would then not appear in any canonical form (except as a "literal" press message in a SND), and so would never be used in any code, except for i/o! As a human, I would miss ORR (and SOME, but maybe not AVOID) in my thought processes, but maybe the same would not apply to a bot. On reflection, BlabBot code would be simplified without these other forms. (If ORR really were useful for constructing some premise, this could still be done, then canonicalized but easy enough to use just AND and NOT explicitly. Equally, SOME or AVOID could be re-implemented, but for now I will remove them.)
So in future, I will canonicalize ORR(x)...(NOT(y)) ==> NOT(AND(NOT(x)...(y)). This will, on average, increase the number of NOTs by one, but each only incurs one indirection, and saves having any code for ORR (except for i/o).
----------------------
BlabBot currently canonicalizes multi-term predicates, such as DMZ, to simpler, single-term forms. E.g., it translates a DMZ to a (sorted) AND of DMZs for each single power/province combination; similarly for an OCC, but if it contains an UNT, then it also uses a (sorted) ORR of each combination of specific unit. The rationale is that, since other code needs to deal with AND and ORR anyway, these complex forms do not then incur further complication (after canonicalization). Actually, although the result is then easy for a bot to process, it is then often hopelessly indigestible to humans, and even some simple bots (e.g. ones that cannot handle AND or ORR, or maybe ORRs within an AND or the game-level may forbid such forms). So just before transmitting, premises are "clumped" into compact, multi-term forms of DMZ, etc. This also compacts premises that never were compact in the first place (before canonicalization).
However, for some reason, I had not done some other plausible expansions during canonicalization, such as expanding PCE to an AND of PCE between each combination of pairs from the specified powers. I think this was partly to retain the sets of constrained powers, which would be less obvious when expanded into pairs; conceptual chunking would be lost. But surely, the same logic applies when expanding DMZ, etc. Indeed, it may be useful to retain an explicit list of powers so that it can be readily seen that the same set applies to given PCE, ALY (friends or enemies), DMZ, SCD, SND, FWD, BCC, or parties to any given message; it is obscured when expanded. (Regrettably, the set of powers involved in an OCC would still not be quite explicit.)
Consequently, generalizing, for consistency, I have now decided not to expand any multi-term predicates during canonicalization! This would better retain the conceptual chunking, albeit incurring some extra complication when processing. In any case, I have found, e.g. when calculating expectation (see above), that often premise-class-specific functions are needed anyway. Although these then need to loop over multiple terms, there are sometimes savings or simplifications when doing many of the same class in a batch. Much of the need for clumping would then also be removed, since expanded forms would be rarer. In fact, I will put clumping in into canonicalization instead, in case unanticipated clumping is possible (albeit more difficult to clump when not fully expanded).
----------------------
Note that a SOME, i.e., NOT(FOR), and an ORR, i.e., NOT(AND), are relatively weak compared to a similar (positive) FOR and AND, especially if many turns or terms, respectively, are specified. Such premises tend to be poor in a FCT, THK, PRP or INS, or an agreement, as they tend not to so tightly constrain what can be expected. I.e., they do not strongly restrict the number of possible "worlds". Better than nothing though and may be all that can be said about what third parties are likely to do! However, these weaker forms would probably be especially useful when trying to narrow down common agreement about what the parties will do, or what third parties probably will do which would normally be finalized in a strong form. I.e., specify a set of desired premises (especially in a SUG, but could be in a PRP) or expected premises, allowing the other parties to narrow it down.
Note that negating a predicate that has an unlimited period, e.g., NOT(PCE(x)), says only that the predicate will not be done this turn or some unspecified later one, which is no constraint at all! I.e., NOT(PCE(x)) == SOME(p)(NOT(PCE(x))) == TRUE, where p approaches an infinitely long period.
----------------------
All the above illustrates some of the many ways of saying the same thing, thereby also illustrating the difficulty of describing (especially to human players, but also to programmers) what is and is not allowed, if we start on the slippery slope of banning redundant alternative forms. It also illustrates a little of how language can affect ability to conceptualize, or process such conceptualizations unless clearly separated, as is conventional in translating between internal forms, optimized for ease of computation, and external forms, optimized for communication, or as specified by the client (albeit usually only being simple transliterations). Also compare Chomsky's "surface" and "deep" structure.
On reflection, BlabBot's clumped forms already happen to form a canonical set, i.e., no two clumped forms represent the semantically identical concept. There is also already rapid conversion between the normal (expanded) and clumped (compacted) canonical forms (using memo functions that cache results if non-trivial to compute). So BlabBot already has the best of both worlds: expanded, which simplifies iteration in low-level functions, and compacted, which simplifies high-level functions that need an overview, or for transmission/human consumption. Also, this avoids significant recoding that I was considering yesterday! (Moral: Always sleep before implementing big decisions! Maρana!) I may, however, now refer to the sets as expanded and compacted (canonical) forms, rather than canonical and clumped. I had been thinking that compacted (clumped) forms would not be used, except for transmission, but this might not always be so.
It is not essential to do every possible canonicalization, especially if obscure, difficult to compute, or impracticable to store any that are missed may simply incur more complex coding elsewhere, and possible duplication of equivalent computations. But I may explicitly expand PCE(x) to a (sorted) AND of every pairing of powers in x. (This is what, otherwise, every low-level function of PCE effectively has to do, such as the PCE version of BlabBot's Expectation functions.)
Likewise, I may expand ALY(x)VSS(y). This would comprise a (sorted) AND of a PCE for each pairing of powers in x, and an ALY of each pairing of a power in x against a power in y. (This is what the logic in the ALY version of BlabBot's Expectation function boils down to.)
The above analysis of ALY (as used internally) allows each set of powers to comprise a single power, meaning the first power acts against the second power. This seems to me to be a natural extension, and, as such, I would recommend that it be allowed (not banned, as recently proposed) in the (external) DAIDE language.