I have table and some functions like Generate_moves() etc. but for the minmax algorithm to work I need to set a score for tables to make the computer choose the best table.
public int Score()
if (Turn == "X")
if (gameWon("X")) return 100;
if (gameWon("O")) return -100;
if (gameDrawn()) return 0;
return n - canWin("X");
if (Turn == "O")
if (gameWon("O")) return 100;
if (gameWon("X")) return -100;
if (gameDrawn()) return 0;
return n - canWin("O");
canWin(string) returns a number that tells me how many Xs or Os i have in a straight line or column but I doubt it is a great why to set the score for a table.
If I have the table:
X - X
0 X 0
- - 0
the score should be the same as
X - -
0 - X
0 0 X
and should be bigger than
X - X
0 - -
- 0 -
And I don't have any idea how to make the Score function tell me different scores. How can I implement the method Score to tell me this?
if computer is first with X and me with O
X - - X - - X - - X - -
- - - -> 0 - - -> 0 X - -> 0 X -
- - - - - - - - - - - 0
now how can i make the computer choose that the next best option is
X - X
0 X -
- - 0
Tic-Tac-Toe is a relatively easy game for computers - since the branch factor and number of possibilities is relatively small, thus: It'll be best to create the easiest [to calculate] possible heuristic function, and let the minmax reach the deepest level, the leaves of the game tree, which are all a certain win/loss/draw.
If you are still looking for a heuristic, you can use
number of rows/cols/diagonals with exactly 2 "X"s and left square is empty
Nevertheless, I still think [for this specific problem] a minmax algorithm that returns -1 for loss, 1 for win and 0 for all other possibilities will perform better - since it will reach the game's leaves faster, and thus will be more informed then any heuristic.
I think you are overcomplicating things. There are less than 400,000 possible Tic-tac-toe games - in fact, Tic-tac-toe is simple enough that you can write down the best moves for every possible game on a single sheet of paper
Even an algorithm as simple as minmax is overkill - just check all possible moves by brute-force. It should only take a few milliseconds on a modern PC.
One possibility...Score = Number of remaining ways (rows, columns or diagonals which can still be filled to winning state) to win for x - Number of remaining ways to win for 0 for every state which is not a leaf (final state) For the leaf states you only have Score = 1, 0 or -1
To answer your second question:
now how can i make the computer choose that the next best option is...
This is the task of the minimax algorithm. It peeks the best move from the game-tree. For tic-tac-toe you don't need a very sophisticated evaluation function, it's enough to return a positiv or negativ value if a player has won or 0 otherwise. If you like, you can extend it by evaluating if one player can win in the next move. More sophisticated evaluation functions you need in games with a greater branching factor and where the game-tree can get much deeper (not only 9 moves).
My experience* was, that going one ply deeper in game-tree search yields to better results than not reaching this ply (in the same time) because of a smarter evaluation function. It's not so easy to distinguish between deeper searches because of a simple evaluation or not so deep searches because of a sophisticated evaluation. There are a lot of other significant enhancements to the minimax algorithm which are promising, don't get stuck with a complicated evaluation, first think of:
After then you still can improve the evaluation function. Some other thoughts to the evaluation: Maybe it's better to do some work in the function
makeMove, here you only need to check one (instead of all) row, one column and one or two diagonals. Then, beside the current board, keep the information got from this check. This information includes, if this was a winning move (set the score), or if the next move from the other player is forced (remember the move the next player has to make,
getMoves will only return this one). Last but not least, if one column/row and one diagonal includes a forced move, the player wins in two moves (keep the score).
Good luck with your evaluation function!
* Some time ago I worked on the evaluation function of a Connect-Four-Game-Engine. The best approach for evaluating a connect-four board was to analyze the odd and even threats as descibed in the chapter "Threat Analysis" of the articel Expert Play in Connect-Four from James D. Allen. The algorithm analyzed major and minor threats. After removing the minor threat analisis part, the alpha-beta search performed better!
I know what you're talking about. What you need is a good heuristic function. You can find heuristic functions from here (I did not try any of them):
Solve Tic Tac Toe with the MiniMax algorithm