Min/Max Tic Tac Toe

1
votes

I am creating a tic tac toe with min/max so I can expand it to alpha-beta pruning. So during my min/max I find if a path with lead to +1 (X win) -1 (O win) or 0 (Draw) however for a board config such as this:

During 0 turns it picks the bottom left since that move leads to its win. Should I check each table for a block, then it would not run as fast and I don't think thats how min/max should be implemented.

0|x|0
-|x|-
-|-|-

Can someone explain why the min/max is not smart enough to detect that. I though that it looked at the left nodes and return +1/-1/0.

2
javaalgorithmminmax
If you're doing this to learn about min/max, that's great, but if not, there are simpler algorithms for tic-tac-toe. – Pops
My other comment aside, you haven't actually explained how your algorithm works or provided us with any code, so we can't answer this. There's nothing wrong with min/max in theory; it's your implementation that's the problem. – Pops
Agree with Lord: min/max is certainly smart enough to give the right answer and we can only assume that you're implementing it wrong. – Hovercraft Full Of Eels
@Lord: "If you're doing this to learn about min/max, that's great, but if not, there are simpler algorithms for tic-tac-toe" - Unless, of course, we're talking generalized tic-tac-toe (> 3x3x1). – Merlyn Morgan-Graham
@Merlyn, good point! The OP's sample seems to indicate a "standard" 3x3 game, though. – Pops

2 Answers

2
votes

Edit: I've been mixing up "pure" minimax, with minimax + heuristic. I've edited my answer to resolve this.

Maybe it would help to define minmax. From An article by a UC Berkeley student:

minimax(player,board)
    if(game over in current board position)
        return winner
    children = all legal moves for player from this board
    if(max's turn)
        return maximal score of calling minimax on all the children
    else (min's turn)
        return minimal score of calling minimax on all the children

With minimax, you are trying to minimize your losses, not maximize your gains. So, "your" turn is min's turn. With this definition, if you could ever lose by selecting a square, then it will be marked -1. If you could ever tie, but will never lose, it will be marked 0. Only if it is a guaranteed win will it be marked 1.

Should I check each table for a block

If you are defining your score and algorithm correctly (matching the right players to the right logic), you need not "check for a block". Any game sub-tree where the player didn't block should implicitly be evaluated -1, because at some point (probably very quickly) it will evaluate to a loss, and that loss will bubble up.

The real problem with this algorithm (and where you may be getting results that you aren't expecting) is when all sub-trees result in possible losses. At that point, you will need to use a heuristic to get any better information on which move you should take. You will need something better than simply {-1, 0, 1}, because some moves could allow you to win, but you'd block them out because you could also lose.

0
votes

I am not quite sure about your problem. As has been pointed out before, min/max has problems when more than one path leads to a win or all paths lead to a loss. In such a case is mathematically correct to pick any or the winning paths or any path at all for the loss. However if playing with a non perfect adversary it is often more sensible to pick the shortest winning path and the longest loosing path (as to hope the adversary does not play perfect and picks a wrong choice).

This behavior is quite easy to implement in min/max using a decay for each recursion. I.e. whenever you return something from a recursive call multiply the result by 0.9 or something like this. This will lead to higher scores for longer negative paths and smaller scores for longer positive paths.

This does however lead to problems, once you start using a heuristic to break out.