Codecup is a game base artificial intelligence programming contest.
For 2013 the selected game is Symple, a board game by Christian Freeling.
The rules of Symple
The rules are pretty simple.
The game is played on a go board with an odd number of lines (15 lines for codecup), and two players, white and black. White plays first.
Each turn, the players have to play either an exploring move (place a new stone not connected with any of his groups), or an expanding move (place enough stones so that each of his groups grow by one stone if possible). Connections are allowed during expansions.
The game ends when the board is completely full. The score of each players is his number of stones, minus a penalty for each of his groups (6 points for codecup).
The aim of the game is then to have the most possible stones, splitted in the less possible groups.
Since players can’t pass, it can make for some dramatic endgames…
The tournament format
This means that playing safe to ensure the victory is fine in a game, but isn’t a good idea in this tournament.
A game of symple can be cut in several stages :
- The first few moves, when each player tries to explore the most part of the board, and when the special move can be played
- The main part of the game, when we try to expand in the best way possible, and where connecting and cutting happens.
- Early Endgame
- No big area left, but a few shared intersections remains. This stage can be pretty short, even unplayed in a few games.
- Late Endgame
- Most shared liberties are played, this is when we fill the inner eyes.
Let’s see what my engine try to do in each of these stages.
In the Opening
I tried to have an engine playing a nice game, like a go player would do. This means that I try to get the corners first (or the center sometimes, to be less predictable), then the sides. I try to maximize my influence, while taking the potential connections between stones into account.
There’s a big decision in this stage: when to expand ? If I expand too early, this wastes a move, but if I expand too late, the opponent can play the special move (or expand to prevent me to play it). The details are here, but mainly, I expand if i have enough stones, if I’m ahead, or when a contact move was played.
Even if I can still explore here (invasions…), it’s mostly expansions.
An expansion is a sum of several moves (one per group, minus connections), so there can be a huge number of different expansions at each turn. This is why classic methods like alphabeta or even mcts aren’t that useful in this game: the search space is too big.
Therefore, my engine selects only one expansion from all the available ones, then remove disabled expansions. It then loops until no more expansions are left. This can lead to some mistakes, but is fast enough to play with codecup’s time restrictions.
As I said, I can’t take the time to predict the opponent moves and evaluate a game tree. Therefore, I apply every possible expansion for both players at each turns. This looks like every player is playing perfectly, having the best move included in all expansions. This sounds dumb, but works pretty well to find cuts several moves ahead, or to block incursions in my territory like in this case, where E2 is mandatory to be able to play E1 and protect the whole lower left corner.
Basically, this takes this situation (black to play):
and turns it into this simulation, the red dots showing the selected move :
The early endgame is much simpler: play only expansions, shared liberties first, take eye shape into account.
This is a bit more complicated. Sometimes exploring is better than expanding, invasions can be very important.
The search space has reduced a bit, so we can select one expansion, and every exploration, and do a full board evaluation for each of these moves.
The details are here.
I tried to write something simple, but it still ended with too many heuristics. I’m eager to see how other contestants have done!