Minimax algorithm: Cost/evaluation function?

Question

A school project has me writing a Date game in C++ (example at http://www.cut-the-knot.org/Curriculum/Games/Date.shtml) where the computer player must implement a Minimax algorithm with alpha-beta pruning. Thus far, I understand what the goal is behind the algorithm in terms of maximizing potential gains while assuming the opponent will minify them.

However, none of the resources I read helped me understand how to design the evaluation function the minimax bases all its decisions on. All the examples have had arbitrary numbers assigned to the leaf nodes, however, I need to actually assign meaningful values to those nodes.

Intuition tells me it'd be something like +1 for a win leaf node, and -1 for a loss, but how do intermediate nodes evaluate?

Any help would be most appreciated.

Answer 1

Most evaluation functions in a minimax search are domain-specific, so finding help for your particular game can be difficult.  Just retain that the evaluation needs to return some kind of percentage expectation of the position being a win for a specific player (typically max, though not when using a negamax implementation). This one ties in very closely with the game pickup sticks.

Start looking for a way to force an outcome by looking at a terminal position and all the moves which can lead to that position. For instance, in the sticks game, a terminal position is with 3 or fewer sticks remaining on the last move.  The position that instantly proceeds that terminal position is, therefore, leaving 4 sticks to your opponent. The goal is now to leave your opponent with 4 sticks no matter what, and that can be done from either 5, 6 or 7 sticks being left to you, and you would like to force your opponent to leave you in one of those positions.  The place your opponent needs to be for you to be in either 5, 6 or 7 is 8. Proceed with this logic on and on and a pattern becomes available very quickly. Always leave your opponent with a number divisible by 4 and you win, anything else, you lose.  

Minimax is a decision rule used in Artificial Intelligence so if you wish to learn more about Minimax Decision Rule then visit this Artificial Intelligence Course.