-
5x5 Tic Tac Toe
http://rafb.net/p/N0Q9yA57.html
I created this code, which I modified from the 3x3 version. However, whenever I enter my first move, I sit there and wait for almost 10 minutes while the program processes until I terminate it because the computer has not determined a move yet. The program uses alpha beta pruning, and for the 3x3 board it finds the computers move instantly. 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?
Thanks.
-
Code:
t.chooseMove( TicTacToe::COMPUTER, bestRow, bestCol );
This doesn't match with the function definition
Code:
int TicTacToe::chooseMove( Side s, int & bestRow, int & bestColumn,
int alpha, int beta, int depth )
-
Hmm, I don't get an error anywhere in my program so I'm not sure if it still lets me call this function with the syntax I have?
-
It shouldn't let you compile. You might want to change some settings on your compiler.
-
-Wall and -pedantic come to mind
-
If that still doesn't work, please post your alphabeta function and any related code (i.e. any extra functions you use to generate, do, or undo moves). It will most likely be a very small problem in the way you adapted the 3x3 to work for a 5x5.
-
-
The first problem I can see is that you never call chooseMove() with a specified depth, other than when you call chooseMove() from within itself. When you ask the program for a best move, you need to specify a depth to search until. I would call the chooseMove() function with a depth of 4 or so to begin with. Then, if that works the way it should, increase it.
Another (major) problem is that on each recursive call to chooseMove(), you pass `depth + 1' as the new depth parameter. This should be `depth - 1' if you ever plan for your program to reach a result.
Fix those problems, then post back to let us know how it went.
-
What should I pass in the values of alpha and beta as?
-
When searching for a best move, alpha and beta should take initial values of -(LARGE_NUMBER) and +(LARGE_NUMBER), respectively. I'v written a few alphabeta searches before and what I like to do is define some constant in my code to represent this large number as you'll find that it can crop up in quite a few places. Something like: const int INFINITY = +1000000;, though for Tic-Tac-Toe it really doesn't need to be so big, +100 would do.
The initial call to your alphabeta function should look like this then: (having already defined INFINITY and maxDepth)
Code:
TicTacToe::chooseMove(TicTacToe::COMPUTER, bestRow, bestCol, -INFINITY, +INFINITY, maxDepth);
As I said in my previous post, let maxDepth be something relatively small for the moment, then increase it when you get the searcher working.
That's all for the moment, I think.
-
http://rafb.net/p/33KwCJ45.html
Ok, so I made those changes and this is the code I have now. So I tried running it and it was still taking forever till the point where I decide to terminate the program....
-
Ok, the next thing to do is to take each element of the program (i.e. the isAWin(), playMove(), boardIsFull() and positionValue() functions), and test each of them individually. Having had another look at the code, I see a problem here: (in the isAWin() function)
Code:
for( row = 0; row < 5; row++ )
{
if(board[row][0]==s && board[row][1]==s && board[row][2]==s && board[row][3]==s )
{
return true;
}
else if (board[row][1]==s && board[row][2]==s && board[row][3]==s && board[row][4]==s)
{
return true;
}
return false;
}
After checking the first row (or column, in the second for loop), you are assuming that there cannot be a 4-in-a-row further down the board, and you're returning false. This is surely wrong...?
-
@tallguy: Could you let me know if that worked?
-
Was that supposed to be 's' instead of just plain s?
-
Ok I fixed it and it still takes too long. Maybe it has something to do with the size of the table depth? Possibly making it larger?