I finally overcame several weeks of programmer’s block on the train this evening, by writing the AI for the bridges game.
The game is solved by building bridges between nodes until all nodes have the correct number of bridges coming out of them. (There are some other conditions such as connectedness and acyclicity (is that a new word?), but the AI conservatively ignores those and cannot use them to infer anything as yet.) In each iteration, the AI finds a node and attempts to make progress in solving that node locally.
The AI has only one rule: the pigeonhole principle. Each bridge slot around a node has a certain maximum additional value, which is the least of:
- The remaining charge on the target node in that direction.
- The maximum bridge thickness (i.e. 2) minus the current bridge thickness.
- 0, if no bridge can be built there due to obstruction by other bridges, or absence of a target node in that direction.
If, for any slot, the sum of the other slots’ values is not enough to satisfy the remaining charge on the node, then this slot must have a bridge built (or thickened).
Using this rule, the AI will not itself built erroneous bridges. But it is also possible for the human to work in concert with (or maliciously against) the AI. If erroneous bridges are built then the AI will attempt to use that incorrect information in inferring additional bridges, so it can all go spectacularly wrong.
If a depth-first ability is implemented, as was done for the network game, it will be necessary to detect such inconsistencies. Again, there are three sources of them:
- Incorrect guesses by the AI, from which it can backtrack.
- Human interference.
- Bugs in the AI.
Assuming that only the first case occurs, and that the AI can eventually detect such a mistake, it will eventually solve the board. Detecting the mistake can be done by examining the victory conditions, which are: no trolls (i.e. no excess bridges round a node), no cycles, and a single connected component.
Having written these two games, I’m starting to notice reusable parts common to both, in both the GUI/controller and the AI. The next step might be to factor them out into a general simple-pygame-logic-game framework to be used by both.
EJRH 