Tic Tac Toe: Understanding The Minimax Algorithm (2013) | Hacker News Reader

Tic Tac Toe: Understanding The Minimax Algorithm (2013)

neverstopbuilding.com

94 pointsmadflame99113 comments

One of my friends made a strong chess engine in high school: http://www.tckerrigan.com/Chess/TSCP/

It's far, far more sophisticated than this and still only about 2k lines of C. The source is available on the site linked above.

If used for larger games, one cannot afford to examine the whole tree. The solution is to stop at some search depth and then estimate how good the position is with some heuristic.

One common optimization is alpha-beta pruning. It is applicable of you have already found a good move (when we use a heuristic we don't know for sure if it will win or not, only if it is good or not), and consider another candidate move. If the latter move has a strong counter, that means it will for sure be worse than the good move. We can then immediately discard the weak move from consideration, there is no need to find out just how weak it is. To make best use of this, one should check promising moves first, because then the bar for potential moves will be higher and more pruning can be done.

What great timing. I _just_ finished a Minimax algorithm to programmatically play the game of Rota. I did this as fun project to teach myself Golang. If this article seems interesting to you, I would suggest doing something similar.

Cool writeup. I botched an implementation of negamax[0] for a coding interview for CMG a few years back.

Ultimately with algorithms like minimax or negamax if your scoring / winning algorithm is slow this will compound on top of that. I didn't dig in deep to OPs code nor do I "know" ruby but a quick glance at the scoring / checking code and I saw a yield in use so that's good :D

[0] https://en.wikipedia.org/wiki/Negamax

Another way to make play more 'realistic': break ties in the evaluation function according to the expected value for random players: https://github.com/darius/sturm/blob/master/tictactoe.py#L12...

(spock_play is what the OP called fatalistic, max_play is more like a human.)

The Berkeley AI class on edX[0] covers this, and other related algorithms, like alpha-beta pruning. It's a very fun class; recommended for anyone interested in this sort of thing

[0]: https://www.edx.org/course/artificial-intelligence-uc-berkel...

I'm glad this is useful for people. Thanks :)

>Basically the perfect player should play perfectly, but prolong the game as much as possible.

hmm no, "masters" will concede the game when they realize they lost, if conceding isn't an option I believe making a play that will end the game faster is the next best.

Well, that really depends on what your goal is.

One reason for prolonging the game is that it gives your opponent more chances to make mistakes, turning some losses into either ties or victories. This is true for both human or AI opponents.

Another reason to prolong the game against human competitors is if you're playing another game after this one, and you think your opponent will tire before you will. By causing the game to go longer, you gain a mental advantage in the next game.

Now, these may be considered "unfair" or "unsportsmanlike", but explaining that is left as an exercise for the reader.

Reversi in Haskell: https://github.com/geon/Othello-in-Haskell/blob/master/othel...

Bit off topic. But I Wish Github would allow me to set my tab-width so that tab-idented code is actually readable...

And indeed it does:

https://github.com/geon/Othello-in-Haskell/blob/master/othel...

Just add the ts parameter to the query string...

Had fun trying out your example. I really like this "You will note that who the player is doesn't matter. X or O is irrelevant, only who's turn it happens to be."

Reply on news.ycombinator.com