1
$\begingroup$

I am trying to have my Minimax AI chess players play against each other.

I was a bit confused about an implementation detail.

Let's call black my first minimax AI chess player that plays first.

white is the other minimax AI that goes second.

My question s about the turn. Should black maximize and white minimize OR should they just try to maximize when at their respective turns, with the evaluation function flipped?

I have thought up of two ways to go about this. I have a feeling that they are doing the same thing, but just wasn't sure whether I am right or the two solutions are in fact doing something different.

First solution:

Instantiate a MinimaxAI object for black and white separately. Make sure that black's evaluation function is the opposite of white. For a simple example, the object black's evaluation function is
number of black pieces on board - number of whites on board.

The white object will have an opposite evaluation function number of white pieces on board - number of blacks on board.

Now, when each object takes turns to call the same get_next_move method, they will both be the maximizing player of the minimax algorithm.

Second solution:

Instantiate one Minimax AI object ai to be used by both the black and the white as they alternate turns. black and white will have the same evaluation function
number of white pieces on board - number of blacks on board

Assuming white always goes first in chess, when white calls ai.get_next_move with an even turn number, it will be given the maximizing player role. On the other hand, when black calls ai.get_next_move with an odd turn number, it will be given the minimizing player role.

(this is what I have so far)

I think both should result in the same behavior, but it is more of a feeling than an educated opinion. Please let me know if my feeling is actually correct or not. A semi-formal reasoning process will be welcome!

$\endgroup$
2
$\begingroup$

First of all, note that in chess, white players plays first and it is a quite complicated game to build a AI for. The fact it exists several "draw" situations makes the evaluation function even more complicated to build. You may consider practice on another strategy game like checkers.

The evaluation function:

Most of IA are indeed based on an evaluation function. Let's talk about 2 opponents strategy games without random like chess. if we neglect "draw" situation, either you have a possible winning strategy, that will make you win whatever plays the opponent, either your opponent has one. When a "draw" situation exists, one player has a possible win strategy or both have a draw strategy.

All possible combinations are nevertheless impossible to explore and finding this strategy is matter of heuristic. The evaluation fuction is an heuristic to judge if a state of the game is likely to lead to a win. It can be a value the player tries to maximize.

Generally symmetric evaluation function like yours (nb white-nb black) works well for 1vs1 games. If the two players are equivalent AI, you will indeed have

eval player 1 = - eval player 2

Your second proposition is indeed the same thing. As maximizing $A$ is like minimizing $-A$. But for a proper simulation, I would rather prefer your first proposition that treat the 2 IA independantly.

Now about the "draw" situations, a player that can hardly win (having negative eval) can decide to look for a draw instead of a win. His evaluation function may therefore not be symmetric anymore. In the same way, a player dominating the game may use an assymetric evaluation to prevent a draw.

Depth/Minimax:

I think you misunderstood what is the minimax strategy. When it is your turn to decide what to play, you will explore some possibilies. You can for instance try all your possible moves and chose the one maximizing the evaluation function. This is a depth 1 exploration.

You may also try all your moves with all the moves the opponent may do on his next turn. This is depth 2 exploration. But in all these combinations, you have no information on what your opponent will play. The minimax strategy is to assume he will play the move maximizing his evaluation function, therefore minimizing yours.

For instance, let say you have 3 possible moves $M_i$ Each leads to several possible subsequent moves $M_{i,j}$ for your opponent. $E_k$ = $evaluation(M_k)$:

  • $M_1$ : $E_1 = 3$, $E_{1,j} = [4, 1]$
  • $M_2$ : $E_2 = 5$, $E_{1,j} = [7, 2, -1]$
  • $M_3$ : $E_3 = -1$, $E_{1,j} = [-3, 0]$

in $depth 1$, you pick $argmax_i(E_i)$, that is to say $M_2$

in $depth 2$, you pick $argmax_i(min_j(E_{i,j}))$, that is to say $M_1$

You can of course go even deeper, applying minimax strategy on each opponent action. The deeper you go, the better is the heuristic approximation to find the best strategy. But the number of states to explore generally grows as a power law of the depth ($O(a^{depth})$). Thus, all the difficulty is to focus computation on interesting branch. You can have a look to some methods:

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.