I'm trying to apply minimax algorithm for the game tictactoe 3D in c++. I'm struggling to find a good evaluation function for it.
Does anybody know where has good resource to find the evaluation function?
Thank you.
A:
Here's what I'd use:
Go over all rows (in all directions). For each row, if it has only one player's marks, award that player points based on how many marks there are. You can have a lookup table mapping number of marks to score, which can be adjusted to get the best results. The final result will be the difference between the two players' scores.
Example (pseudocode):
const int markScore[4+1] = {0, 1, 3, 5, 99999}; //assuming 4x4x4 board
//The above values are arbitrary - adjust to what you think makes sense.
score = 0;
for all rows in all directions:
count Xs and Os
if (xs>0 && os==0)
score += markScore[xs];
else if (os>0 && xs==0)
score -= markScore[os];
return score;
This should work well, because any row with only one player's marks gives that player a chance to win.
interjay
2010-04-14 16:30:25
can you show me an example of how to map number of marks to scores?
tsubasa
2010-04-14 16:41:40
i wonder how much effect does the values in setScore do to the AI? I'm trying to find the best values.
tsubasa
2010-04-14 19:35:12
One method to find good values is to let your AI play a lot of games against itself with different values and see which one comes out the winner. A lot of the best chess engines do something like this to tune their parameters. (To be more accurate, they usually play against other engines rather than themselves).
interjay
2010-04-14 20:48:06
A generalization of the previous idea is to use genetic algorithms to tune the values automatically, but that's probably overkill.
interjay
2010-04-14 20:49:17
A:
Heuristics are unnecessary. There are only 3^27 states, you can enumerate them all and compute optimal play.
Keith Randall
2010-04-14 18:56:23
You should define "3D tic tac toe." I assume Keith assumed that it was a 3x3x3 grid, and not 4x4x4 grid, which is what it seems like you're suggesting. In either case, you're confusing "states" with number of possible games. There should be ~3^64 states. Now this is probably infeasible, but might help you visualize the number of states a little bit.
Larry
2010-04-14 19:44:20
A:
The evaluation function for this game needs only to test for a winning position. The evaluation function should count the empty fields in the board because the more empty fileds the board has, the higher the score should be. To reduce the number of lines, rows and diagonals the evaluation function has to check, you can mirror and rotate the board.
Christian Ammer
2010-04-14 19:36:18