I have been reading as much about the minimax algorithm as I can. One answer keeps eluding me. When minimax is traversing a tree how does it know the score of a given position? What kind of function does it in turn look at to actually evaluate the position in the tree and return a score? For example, in Tic Tac Toe, let''s say the computer goes first. In minimax it could, with a depth of one, put the X in any square and based on something (the whole question) it makes a decision as to which one in the tree is the best. Perhaps, I don''t understand the code, but there appears to be another function somewhere doing the "real work." Thanks.

That depends on the application. In a simple game it might literally be the score, or some heuristic that hints at the game balance, or whatever. The reason you think there''s another function doing the "real work" is because minimax isn''t about evaluating the quality of a state as such, it''s about evaluating the quality of a series of states where one side is trying to get ''better'' states and the other side wants ''worse'' states.

[ MSVC Fixes | STL | SDL | Game AI | Sockets | C++ Faq Lite | Boost | Asking Questions | Organising code files ]

An ''evaluation'' function can provide any type of board result. For example, in Checkers, you let mini-max evaluate the board (in another function, or in the mini or max function) usually when you''ve searched the max ply board depth.

For example: A simple evaluation function might total max player''s checkers pieces, and mini''s checkers pieces, then subtract Max from Mini, and get a result that is either negative, zero, or positive. A positive result means a gain for Max, a zero value indicates no change in balance of power (although both sides may have lost pieces together). Finally, a negative result is a gain for Mini.

Hope this clears things up.



If all that matters is what you get in the end, why go through life?
~Michael Sikora

The game is tic tac toe. It appears that in a non-pruning min max the score is gotten by the last leaf which shows either a winning position or not. About 590k variations on move one.

A simple evaluation funtion for tic0tactoe would be:
1 point for each possible win (ie. 2 of your peices on the same row, column, diagonal that aren''t blocked) and -1 for each of your opponents possible wins.
In 3*3 tic-tac-toe, it isn''t difficult to search the whole state space, so if you don''t plan on expanding it, you don''t really need to worry about an evaluation function, and just use the goal test at the end to apply 1 for a win, 0 for a draw, -1 for a loss.

ya the evaluation function is never perfect. its not fair to say its doing the "real work".

think of it this way:
if the evaluation function were perfect then you wouldnt need min-max. Min-max presupposes that the evaluation is flawed. it has to. think bout it. if the evaluation isnt flawed all i would have to do is iterate through every possible 1-ply move, evaluate it, and make the move that had the best evaluation. i could get away with that because the evaluation function is perfect.


thats the cool thing bout min-max/ A*/ alphabeta / etc. they presuppose that the estimate from the evaluation function can be flawed and systematically deal with it. also known as a search.

its not so much the "real work" but the work independant of generalization and specific to the domain.