Pruning Tic Tac Toe Moves

Question

I've written a tic tac toe code that fine to a point. I have Alpha-Beta Pruning working also. I've ran across a problem that I need ideas, NOT CODE. How can I choose a move that will win in 4 moves versus a move that will win in 8 moves. The problem I'm having is the branch that returns a optimal score from minimax/AB prunning will possibly win in 8 moves so it prunes off possibly a branch that will win in 4 moves.

I've ran across a couple ideas such as killer heuristic, transposition tables, and iterative deepening search. Any ideas would be great

Answer 1

A way you can do:

Do your search with a max depth of 2, if no win are find, then increase your depth limit, until you find a win.

For tic-tac-toe, killer heuristic , transposition table , it's maybe bit to much since, you can keep in memory all board possibilities.

In my project I use the Proof-Number Search . But there's so much algorithm that you can use. You can find idea in this site too, but even if it's about chess, most of ideas can be use for your project.

Answer 2

I would look more into iterative deepening. This would help you find the 4 move win before the 8 move win.

Answer 3

Your evaluation should rate winning game states more highly when there are fewer moves taken. This should be pretty easy to implement. Let's say you usually assign all winning game states a value of 100. For a size 9 board, just add the quantity (9 - turns) to this. So a winning board after 8 turns would evaluate to 101 and a winning board after 5 turns would evaluate to 104.

Answer 4

I believe tictactoe has actually been "solved" in the sense that there's an algorithm that will guarantee a win or draw, at least form the initial state so a alpha-beta search seems excessive. (unless you're just learning to implement it on a simpler game than chess or whatever)

Answer 5

(Wanted to include this in a comment, but it became too lengthy)

Iterative deepening would probably be the easiest "fix" for this question. Simply stick the alpha-beta search into a loop that steadily increases the depth that alpha-beta goes to. You can include a couple tests within your loop to get it to terminate early (e.g. a winning move found).

ex:

while (!win_found && depth < 8)
{
    alphaBetaSearch(win_found, depth);
    depth++;
}

Iterative deepening may seem wasteful because states are generated multiple times, but it turns out this is not that costly. The reason for this is that in a search tree with the same (or nearly same branching factor at each level, most of the nodes are in the bottom level so it does not matter much that the upper levels are generated multiple times.

Answer 6

If you write in compiled language you can search the whole tree from 1st move whitout any heuristics in less than second (just alpha beta and eval function which return -1,0,+1), othervise it should not take more than 5 seconds for first move and much less for other moves.

Answer 7

At the beginning of the alpha beta pruning function, I assume you have something like this:

function alphabeta(node, α, β, maximizingPlayer) is
    if node is a terminal node then
        return 100

Instead, if you are in a terminal node, calculate the number of empty squares and add it to the value of the node.

function alphabeta(node, α, β, maximizingPlayer) is
    if node is a terminal node then
        bonus = count_empty_squares(node)
        return 100 + bonus

The alpha beta algorithm will favor the fastest win.