It is thus possible to do a complete one-ply analysis of these phases of the game. That is, we can consider every possible combination of retreats.
Given enough search time, we will include Spring retreats in our search for Spring moves, and the Autumn retreats and Winter builds in our search for Fall moves. This is feasible since the number of possible retreats and builds is usually quite limited; we are not facing the same sort of combinatorial explosion described earlier.
One such look-ahead strategy is called the offensive retreat, which takes advantage of the fact that a unit can often retreat "forward." For example, if England attacks the French F Bel with support from Holland while the North Sea is open, France can retreat there and menace the entire East coast of England as well as Scandinavia and the Lowlands. It is equally important to look ahead at the builds. If Austria-Hungary is at war with Turkey and wants to build a fleet, then he should take care during the Fall movement that Trieste is left open for such a build. Similarly, a player who needs a unit back home may chose to disband one of his farflung units rather than retreating it.
Even if anticipating retreats and builds were not needed for strategic reasons, they are clearly needed on a diplomatic level. In face-to-face play and use of the Bordeaux diplomat, the conduct of diplomacy is not allowed before retreat and build season. Thus, any message concerning those seasons should be anticipated and sent to allies before the preceding movement season.
However, looking ahead to future movement seasons will often be futile, because the computer is likely to be wrong about the opponents' moves and the mistakes will get compounded for each turn looked ahead.
The initial strategy finder written by Constantin Staykov ([email protected]) considered all possible combinations of retreats. However, when we introduced the notion of a multi-ply search, we chose to use search techniques in build or retreat phases that are less complete. With their increased efficiency, they can anticipate the following phase via a recursive call to the strategic module of the program. This enables efficient prediction of the results for retreats while planning the strategy of a movement phase.
To implement this technique, the retreat generator was rewritten by Gilles Schaeffer ([email protected]). Groups of related retreats are studied simultaneously (using an evolutionary search, optimizing in turn for each involved country).
Let the terminology uAv refer to u and v which are 2 retreating units which have a common possible retreat or even adjacent possible retreats. Let B be the transitive closure of this function A. (That is, B = I u A u A^2 u ...) Then two units u and v are considered related if uBv. (In the vast majority of circumstances, a retreating unit will only be related to itself.
Among related retreats, all combinations will be studied, and each alliance will move to maximize its minimum possible return.
Remember also that only a maximum of 11 units can retreat at one time (and usually many fewer). This search is much more rapid (and thus much more useful as the second ply of a two-ply search), and yields more significant results than the original program.