Minimax algorithm: cost / valuation function?

Question

In a school project, I write the game “Date” in C ++ (an example at http://www.cut-the-knot.org/Curriculum/Games/Date.shtml ), in which a computer player must implement the Minimax algorithm with alpha-beta pruning. Until now, I understand what the purpose of the algorithm is in terms of maximizing potential wins, assuming that the adversary minimizes them.

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

Intuition tells me that it will be something like +1 for a winning end node and -1 for losing, but how do intermediate nodes evaluate?

Any help would be most appreciated.

Answer 1

The most basic minimax evaluates only end nodes, marking wins, losses and draws, and maintains these values ​​up the tree to determine the values ​​of intermediate nodes. In the event that the game tree is difficult to process, you need to use the cutoff depth as an additional parameter for your minimax functions. Once the depth is reached, you need to run some kind of evaluation function for incomplete states.

Most of the evaluation functions in minimax search depend on a specific area, so finding help for a specific game can be difficult. Just remember that the rating should return a certain percentage of the percentage expectation of the position that is the gain for a particular player (usually the maximum, but not when using the Negamax implementation). Any less explored game will be very similar to another, more explored. This one is very closely related to game pickups . Using only minimax and alpha beta, I think the game is changeable.

If you need to create an evaluation function for non-terminal positions, here is a little help with analyzing the stick game, with which you can decide whether it will be useful for playing dates or not.

Start looking for a way to force the outcome by looking at the final position and all the moves that may lead to that position. In a stick game, the final position is 3 or fewer sticks left on the last move. Thus, a position that immediately moves to this final position leaves 4 sticks to the opponent. Now the goal is to leave the opponent 4 sticks, no matter what, and this can be done if you leave 5, 6 or 7 sticks, and you would like to force your opponent to leave you in one of these positions. The place where your opponent should be, so that you are in 5, 6 or 7, is 8. Continue this logic, and the pattern becomes available very quickly. Always leave your opponent with a multiple of 4, and you win, everything else you lose.

This is a pretty trivial game, but the heuristic definition method is important, as it can be directly applied to your assignment. Since the last move is the first, and you can only change 1 date attribute at a time, you know that you need exactly 2 moves to win ... and so on.

Best of luck, let us know what you end up doing.

Answer 2

The simplest case of the valuation function is +1 for winning, -1 for losing, and 0 for any unfinished position. Given that your tree is deep enough, even this simple function will give you a good player. For any non-trivial games with a high branching coefficient, as a rule, you need a better function, with some heuristics (for example, for chess you can assign weights to parts and find the sum, etc.). In the case of a Date game, I would simply use the simplest evaluation function, with 0 for all intermediate nodes.

As a side note, minimax is not the best algorithm for this particular game; but I think you already know that.

Answer 3

From what I understand in the Date game that you contacted, it seems that only possible results for the player win or lose, there are none between them (please correct me if I am wrong).

In this case, it is only a matter of assigning a value of 1 to a winning position (the current player receives until December 31) and a value of -1 for losing positions (another player until December 31).

Your minimax algorithm (without trimming alpha beta) will look something like this:

A_move(day): if day==December 31: return +1 else: outcome=-1 for each day obtained by increasing the day or month in cur_date: outcome=max(outcome,B_move(day)) return outcome B_move(day): if day==December 31: return -1 else: outcome=+1 for each day obtained by increasing the day or month in cur_date: outcome=min(outcome,A_move(day)) return outcome