Computing a normal for proper equilibrium of TicTacToe
This is intended as proof of concept of the algorithm that characterizes the normal form proper equilibria of a perfect information game. A description of the algorithm can be found in the publication, which can be found in my list of publications.The program
The program can be obtained as a jar file here, and can be executed with the following command:
java -jar ProperTicTacToe.jar [inputfiles]
The list of inputfiles can be empty, in which case the input is the default empty board. The code will only execute on a 1.5 VM or newer.
The input format
The input files are interpreted as a TicTacToe board in the following way. All characters that are not "Xx Oo0" are ignored. The first three lines containing at least one of those characters are interpreted as the rows of a board. If there are not enough characters or lines, the remaining are considered to be empty. Any input entered is interpreted as a board, though it may be a somewhat liberal interpretation. To be accepted as input, the position must be reachable though normal play, and no one must already have won. The player to moves is infered by the number of pieces on the board.
Example input file content:
| |O| | | |X| | |X| | |
The output
The program immediately outputs the board as it is interpreted. Then the full game tree from the specified starting position is traversed, which may take several seconds, as no clever optimizations have been made. After the proper equilbria have been computed, the strategy is printed as a game board with probabilities on each square that was empty on the input board. The special symbol * occurs only if no other non-zero probability is displayed, and it means that that any probability distribution over the marked squares are part of some proper equilibrium. This only happens when the value of the position is the best in that subtree.
Output from the example given:
Input: +-+-+-+ | |O| | +-+-+-+ | |X| | +-+-+-+ |X| | | +-+-+-+ Strategy: +------+------+------+ | 1/21 | | 5/21 | +------+------+------+ | 5/21 | | 1/7 | +------+------+------+ | | 2/21 | 5/21 | +------+------+------+
Symmetries
It is well known that proper equilibria are not robust when it comes to strategy duplication, and it therefore matters whether one considers all empty squares as valid moves or whether symmetric moves are considered the same. Luckily, for perfect information extensive form games, this only turns out to be a matter of scaling. So, if you only consider a subset of the moves to be unique, you can simply scale those to a full probability distribution. E.g. in the empty game, the strategy for the full game is: (corners,sides,center)=(19/286,47/286,22/286)=(1/15,47/286,1/13). If you only consider the three strategically distinct openings, you simply scale those to (corner,side,center)=(19/88,47/88,22/88).The source
The code is written is Java 1.5, and is not commented at all and it uses some library code from the gtf -framework.
