Chess Stack Exchange is a question and answer site for serious players and enthusiasts of chess. It only takes a minute to sign up.
Sign up to join this community
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).
How do I eliminate this scenario?
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!
You may want to consider third-repetition in your search. Stockfish does that:
// 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
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).
