-2

I've built a chess game engine using Minimax and when I play AI against the AI, everything goes fine(for sometime) until both the AI players make the same set of moves again and again.

Observe the moves made by the AI players in the move-log(Right panel).AI vs AI repeats moves

How do I eliminate this scenario?

  • If those are the best moves the engine can find, even though the game repeats, what would you do? Find a worse move? I'd have the game terminate after the same position has been reached 3 times. – Tony Ennis Mar 27 '17 at 4:40
  • 1
    First, it looks like you are missing the draw by 3-fold repetition of positions. Does your program have a method to choose from multiple moves that have an equal score, or does it just pick the first one generated? – Herb Wolfe Mar 27 '17 at 4:42
  • @TonyEnnis I am not sure if its correct to terminate the game because there are scenarios where the number of pieces in the board are more (Eg. White player lost only 2 of its pawns and the same scenario happens). So, I'm confused. – Srikara Krishna Kanduri Mar 27 '17 at 5:25
  • @HerbWolfe I pick the first one generated. – Srikara Krishna Kanduri Mar 27 '17 at 5:25
  • @TonyEnnis In this example, the move can't be the best. White is up by a bishop and some pawns!!! – SmallChess Mar 27 '17 at 7:34
3

Unfortunately, the only right answer to "How do I eliminate this scenario" is "fix your algorithm." Yes, you could implement the 3-fold repetition rule, but you should also figure out what it tells you about your algorithm.

This sort of repetition happens when there is an oscillating pattern that arises in your scoring. Think of it like rock paper scissors. White makes move to try to achieve a rock position, so black tries to make a counter-move that turns it into a paper position. Then white tries to create a scissors position and black replies by creating a rock position.

The only way to fix this is to look at your algorithm, and make the algorithm better. My advice is to put your chess program into a debug mode and have it dump out an analysis of what it is "thinking" with each move. Look at the factors which lead up to your final score, and understand how they're acting.

Once you understand why the algorithm is doing what it's doing, you can fix it. Look at the game and decide what move you'd rather see them do, and why you like that move. See if you can add additional scoring which encourages the type of play you want to see.

One thing in particular I've seen that can cause this sort of behavior is a discontinuity on the horizon. If your scoring stops at your ply limit, and that position looks good from black's perspective, looking one ply further may show a good position for white instead! This, of course, will always happen in real life, but you can try to minimize how often it happens by doing a better job of scoring each position.

If all else fails, a little randomness can help nudge the game along. One mode I implemented when I had to write one of these programs was a variable depth algorithm. Sometimes it would look at 100,000 positions before making a decision, other times it might make 200,000. That decreased the probability that I would run into a simple issue just past my horizon, because my horizon kept moving. Instead, I might blunder into the bad move, but at least the game moved forward!

1

You may want to consider third-repetition in your search. Stockfish does that:

https://github.com/official-stockfish/Stockfish/blob/30c583204f97da2c67b5042c30327013e70ae209/src/search.cpp

    // Step 2. Check for aborted search and immediate draw
    if (Signals.stop.load(std::memory_order_relaxed) || pos.is_draw(ss->ply) || ss->ply >= MAX_PLY)
        return ss->ply >= MAX_PLY && !inCheck ? evaluate(pos)
                                              : DrawValue[pos.side_to_move()];

https://github.com/official-stockfish/Stockfish/blob/master/src/position.cpp

/// Position::is_draw() tests whether the position is drawn by 50-move rule
/// or by repetition. It does not detect stalemates.

bool Position::is_draw(int ply) const {

Implementing third-repetition is important, otherwise your engine might waste moves and think it can still keep the advantage after some meaningless checks.

EDITED

You should implement the check, otherwise your engine doesn't know the move it tries to make is just simple repetition draw. You will need to program the knowledge. Someone else had the problem like you:

http://talkchess.com/forum/viewtopic.php?t=59322&highlight=move+repetitions

  • I'm a beginner and can't understand such complex codes. Describing what's necessary theoretically will help me make changes to my code. – Srikara Krishna Kanduri Mar 27 '17 at 7:38
  • @SrikaraKrishnaKanduri The Stockfish code is very simple to follow. Ok, I'll expand my answer later when I have more time (I'll busy now). – SmallChess Mar 27 '17 at 7:39
  • @SrikaraKrishnaKanduri I was about to edit my answer. Since you have posted a new question, I'll switch to the other one. – SmallChess Mar 31 '17 at 9:18
  • The other question is based on "how" to implement rather than "why" to implement. So, answering in this post will be apt. – Srikara Krishna Kanduri Mar 31 '17 at 9:25
  • this is possibly a duplicate of my question: chess.stackexchange.com/questions/16402/…, I solved this problem by implementing an opening book. Unless I am misunderstanding and this is a three-fold repetion problem for which the solution could be a Zobrist key method – nak3c Apr 6 '17 at 19:22
-1

Even top level engines could do this if they evaluate the position to be completely equal. If your AIs evaluate this position to be equal, then there's nothing wrong with a three fold. But in the position you posted it doesn't make much sense for White to go for a three fold, considering the 7 point advantage.

Do your AIs do this in every game, or does it just happen once in a while? What you could try is to build a method in your code called "Evaluate". It finds the rough evaluation of the position, and if one AI is better then it should not repeat moves. You could do this by making it not repeat the move it made two moves ago. So at: Rg7 Ke6 Rg6 Kd7, since the position has repeated itself call the Evaluate method. If the Evaluate method returns that White is ahead, do not let the AI repeat the move it made two moves ago (Rg7).

  • The Algorithm and evaluation function for both the AI players is the same and so, none of the two is better than the other. This scenario happens every time, even for different depths in Minimax and only the pieces may differ. My engine also allows Human vs AI so won't your Evaluate method fail? I mean, a human can confuse the AI to remove its move. – Srikara Krishna Kanduri Mar 27 '17 at 5:33
  • My idea was the evaluate method would be used from an AI's specific side. For example, assume the evaluate method returns "true" if White is better and "false" if black is better. If "true" is returned then the AI playing White should not be allowed to go for the three fold. If "false" is returned then the AI playing Black shouldn't be allowed to go for the three fold. This way you can use the same method for both AIs. – Inertial Ignorance Mar 27 '17 at 5:40
  • "Shouldn't be allowed to go for the three fold" and so, what must the AI do? Play in a loop again? – Srikara Krishna Kanduri Mar 27 '17 at 5:46
  • I would think it should play its second choice. Although I see how that could be an endless loop if it keeps wanting to play its first choice but it's not allowed... This may be a primitive solution but you could run a loop that checks a random move. If that move gives an evaluation similar to the position beforehand, play it. Else, run the loop again. Eventually the random process should give a fairly good move. Just remember to include in the random process that the three fold move isn't allowed. – Inertial Ignorance Mar 27 '17 at 6:01
  • How can I implement this random function for AlphaBeta pruning? – Srikara Krishna Kanduri Mar 27 '17 at 6:38

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.