Hacker News Reader

Comment by derbOac | Hacker News Reader

I was interested in this game quite a bit for awhile when I was much younger, but then read an article or something stating that the first player has a strong advantage and that they have a guaranteed route to win simply by virtue of playing first. I'm not sure if this is correct or not but it was my understanding at the time, and it kinda dampened my enthusiasm.

View on HN

That's only true for very small board sizes where the game can be "solved". Play on a standard 11x11 or 13x13 and even AI has a hard time.

It's true in a technical sense for any size board. But the proof that the first winner has a winning strategy can't easily be put into a practical winning strategy. In rough outline, the proof goes as follows: First, note that the game cannot end in a tie. Next, use standard game theory to conclude that one of the players has a winning strategy (proof by labeling the game tree, starting with the leaf nodes, and working up towards the root). Finally, assume for contradiction that the second player has a winning strategy. If so, deduce the absurd result that the first player has a winning strategy: Place your first piece at a random location, then ignore that piece and follow the second player's winning strategy. If that means placing a piece where your initial piece is already, place a piece in a different random location, and continue. This works because having an extra piece on the board can never hurt you.

That’s why there’s the “swap” rule.

Yeah we were aware of the swap rule, but it didn't really help our enthusiasm at the time because (1) it seemed then the second player would gain the same advantage, and (2) it seemed to theoretically turn the whole game into one of knowing which opening moves would lead to a guaranteed win, like knowing when to swap, which isn't as interesting.

This was awhile ago though, long before AI solutions to Go and Chess, and what we were reading wasn't that detailed. It seems like the game trees are much harder to know a priori than was our impression at the time, at least for sufficiently large boards. It still makes me wonder but maybe is more complex than I thought.

Seeing it here on HN has kinda rekindled my interest in it.

I will admit in general, these AI approaches to boardgames has kinda changed the way I think about them, from puzzles to think about with a companion to a giant math problem to solve once or so forever for all humankind. It's kinda shifted my interest to the possibility of games where it's harder to develop an AI that could "solve" the game in an algorithmic sense (I was going to say in the sense that there is a program whose probability of winning is equal to or exceeds any other player, but I'm not sure if that's right, because if AI had a 0.5 probability that would be more interesting).

After which the second player has a guaranteed route to win, but it's much harder to find! Last I checked the game tree was computed up to a 6x7 board, players usually use 13x13

I used to play it quite a bit with a friend back in my student days, on a 12×12 board. We were aware, in principle, that the first player had a winning strategy, but in practice, the advantage to the first player was small enough to hardly be detectable (though we did not compile any statistics on it). Perhaps this only serves to reveal that we weren't terribly good at it, though. We weren't aware of the swap rule at the time.

That's slightly surprising since playing in the middle of the board on your first move is such a large advantage.

Beginner players do seem to think that playing near a black side is a good opening, but it's actually one of the weakest, but playing it "quite a bit" I would suspect you would stumble on playing near the middle by accident if nothing else?

Oh, it took us very little time to figure out to start in the middle. It took us more time to figure out what was the most effective response to that. It is hard to remember now, as I haven’t played the game in decades. But most likely, both of us made just enough mistakes, which the other then exploited, that the initial advantaged drowned in the noise of what followed, if you get my drift.

Reply on news.ycombinator.com