5x5 Tic Tac Toe

This is a discussion on 5x5 Tic Tac Toe within the C++ Programming forums, part of the General Programming Boards category; Originally Posted by tallguy However, for the 5x5 board I just terminate it after awhile because it fails to find ...

  1. #16
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,239
    Quote Originally Posted by tallguy View Post
    However, for the 5x5 board I just terminate it after awhile because it fails to find a move. With alpha beta pruning should it just take this long for a 5x5 board, or am I missing something in my code?
    The exponential branching factor of a 3x3x3 board at the initial move is 27. For a 5x5x5, it is 125. At two ply (4 moves ahead), the prior program will have examined 421,200 states. For the 5x5x5, it is 232,593,000 states.

    So even at two ply search depth, the 5x5x5 program will be 552 times slower than the 3x3x3 program. And that's assuming you have no bugs in your code.

    EDIT: of course, since you are using alpha beta pruning, you're really looking at the square root of that number (sqrt(552) = ~23), but that's assuming the move-ordering is absolutely perfect, which I doubt it is.

    This is just the nature of exponential search spaces.

  2. #17
    Registered User
    Join Date
    Dec 2005
    Location
    Colchester, Essex, United Kingdom.
    Posts
    31
    So the program is now working as expected? Could you post the updated code, then? I'd like to have a look at what can be done to make it faster. It is almost completely pointless to prune the game tree with alphabeta if you're not going to order the movelist, since in the worst case you will be searching a plain minimax tree (i.e. no cut-offs). So that would be a good place to start. One very easy way to get some kind of move ordering is to implement iterative deepening in your search. This is simply the process of starting the search by looking with a maxDepth of 1. Then repeating the search at maxDepth=2 and using the results we found on the previous iteration. Then search at maxDepth=3 using information from the previous iteration, again and again and again. You get it...; then, after each iteration you can order the list of available moves from the root position so the one with the highest score is searched first on the next iteration, saving a lot of time by reaching a cut-off as early as possible. Very nifty!
    Last edited by tomcant; 03-28-2007 at 05:50 PM. Reason: Spelling! Tut!

  3. #18
    Registered User
    Join Date
    Mar 2007
    Posts
    32

  4. #19
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,239
    Quote Originally Posted by tomcant View Post
    It is almost completely pointless to prune the game tree with alphabeta if you're not going to order the movelist, since in the worst case you will be searching a plain minimax tree (i.e. no cut-offs).
    Alpha-beta still does better than minimax even with a random move ordering. You don't get worst case performance until the move ordering is maximally bad (i.e., exactly reverse to the optimal ordering).

    With random move ordering you could still achieve a cutoff just by chance. But yes, to get MAXIMUM benefit from alpha-beta you need a perfect ordering.

Page 2 of 2 FirstFirst 12
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Help me with my simple Tic tac toe prog
    By maybnxtseasn in forum C Programming
    Replies: 2
    Last Post: 04-04-2009, 06:25 PM
  2. Tic Tac Toe... so close...
    By SlayerBlade in forum C Programming
    Replies: 14
    Last Post: 10-10-2005, 08:58 PM
  3. Help with Tic Tac Toe game
    By snef73 in forum C++ Programming
    Replies: 1
    Last Post: 04-25-2003, 08:33 AM
  4. look-ahead, recommend function for tic tac toe 5x5
    By portos69 in forum C Programming
    Replies: 2
    Last Post: 11-21-2002, 06:42 PM
  5. Need some help with a basic tic tac toe game
    By darkshadow in forum C Programming
    Replies: 1
    Last Post: 05-12-2002, 04:21 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21