The size of a regular Go board is 19 by 19. It's well known that the number of possible board states is more than that of atoms in the universe. That's why AlphaGo is hailed as a major breakthrough. But how hard can it be, if we play on a 5x5 board?
Let's do some math. 25 positions on the board, each can be either empty, black, or white.
3**25=847 billion! Surprisingly large.
Okay, not all of them are legal. The more precise number (of legal board configurations) is 414 billions, 414,295,148,741 to be exact.
We can reduce that number using symmetries: rotation, flip. This leads to a total of 8 combinations. But with even a 100-fold reduction, it's still four cool billions.
If you play a couple 5x5 Go games, you will quickly appreciate that C3 opening is likely the winner (indeed it is). Taking into account symmetries, there are really 5 other openings. Since A1/B1/C1 looks odd (to me at least), that leaves us just C2 and B2. We can push the symmetry argument a bit further, but that complicates implementation. We need to jump through quite some hoops. And it's simply not clear how to enforce symmetry with neural networks.
If we restrict ourselves to C3/C2/B2 openings, and some common sense (like not go on 1-line unless necessary), the search tree might be manageable, since the most interesting part of the game is likely within the first 10 moves. By that time the game has taken a certain shape, and it may seem straightforward to solve for the rest of the game.
But is it true? The issue of life and death looms large in endgames. Dead-stone removal is in fact far from trivial. There is only one algorithm to check for pass-alive area, which is used by KataGo and others to speed up end-games.
According to Werf, et al, the best play for C2 opening is: C2 C3 D3 D2 D1 B2 E2 C4. It's shown above. Click the arrow button or use left/right key to step through the game. Black wins by 3 points.
I trained my AlphaZero bot on this particular opening. In the process I learned of the complexity of the game beyond my expectation.
During self-play runs, bot has found this opening instead: C2 C3 D3 D2 D1 E2 (white plays E2 to avoid capture, shown on the right) and strongly likes it. Most of them lead to a black win.
This doesn't make sense at all. The white stone cannot be saved. What's the bot thinking? Is it just one of the intermediate stages (read: suboptimal) before it masters the C2 opening?
Looking at how black would respond to this E2 move, it's actually not straightforward at all.
The best response I think is: E3(threat) B2(threat) E1(take) C4 D4 D5(disallow eye) B4 B5 B3(threat) C5(save) E5(threat) E4(ko) B1(threat) A2(extend) E5(ko). White lost in a ko fight!
As an alternative, if white doesn't go aggressive in D5, it can survive (e.g. A4), but with a loss, as expected.
When I play (black) on this variation against my bot, white aggression at D5 seems to hold. It responds with B3 when I attack at B4. And no matter what I try, white wins!
I tried another black response to white's E2 move: E3 B2 E1 C4 D4 D5(disallow eye) B1(*) B3(protect) A4(fight) which will likely result in black win on territory, but not pass-alive.
Interestingly, when I played this sequence against my AZ bot, it chose a different route: after black B1, bot played white A2, which seems to result in a white win again! E3 B2 E1 C4 D4 D5(disallow eye) B1 A2(*)
For this reason, white move #6 at E2 is not on the optimal path.
There are other interesting scenarios. The nice thing about 5x5 board is that you don't waste too much time :) These mind-boggling puzzles are probably better left for bots to solve.