Tic Tac Toe: Understanding The Minimax Algorithm (2013)

by madflame991 • 11 years ago

94 13 11 years ago

chaosfox• 11 years ago

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.

zck• 11 years ago

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.

leetrout• 11 years ago

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

xiaoma• 11 years ago

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.

jrobertfox• 11 years ago

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

im3w1l• 11 years ago

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.

sparaker• 11 years ago

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."

kkl• 11 years ago

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.

nemesisrobot• 11 years ago

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...

geon• 11 years ago

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

arianvanp• 11 years ago

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

Tosgin• 11 years ago

And indeed it does:

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

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

abecedarius• 11 years ago

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.)

Tic Tac Toe: Understanding The Minimax Algorithm (2013)

Related Stories