Page 13 - Krész, Miklós, and Andrej Brodnik (eds.). MATCOS-13. Proceedings of the 2013 Mini-Conference on Applied Theoretical Computer Science. Koper: University of Primorska Press, 2016.
P. 13
Algortihm for Recognition of Position Repetition in
Chess
Nándor Németh
Eötvös Loránd University
Department of Software Technology and Methodology
nem.nandor@gmail.com
ABSTRACT enormous mistakes, roughly in every second game. Nowa-
days we can find several solutions for the problem in sophis-
A chess game ends in draw if the same position appears for ticated chess programs[2]. Some of the programs use correct
the third time. In a chess program, we need to implement algorithms for the problem. Others use statistically correct
this rule to avoid losing some winning positions, and not methods which run faster, and rarely make mistakes. In
to lose positions, where we have the possibility to make the this paper, the author demonstrates a new correct method
match a draw. Recognizing position repetitions is not trivial for the problem.
problem. The algorithm must run in most of the positions
we reach in the game tree, so it must run quickly. We can 2. DEFINITIONS
read about a lot of algorithms which recognize the repeti-
tions. There are two groups of these algorithms: correct To understand this paper more easily, let us describe some
ones, and statistically correct algorithms having faster so- definitions:
lutions. This paper demonstrates a correct solution which
is simpler and faster than any other correct algorithm, and Two positions are identical if each square of the board con-
it can work with any board representation. We can check tains the same piece, the same player has to move, and the
some statistically correct algorithms quickly with a correct move sentences, the payers can make, are identical, too.
method. Therefore we can get a more faster correct algo-
rithm for the problem. The normal search tree is a graph. The root vertex is the
position we can see on the chessboard. The other vertices are
Categories and Subject Descriptors the positions the program reaches during the search. The
edges represent the moves. Let us extend this tree with all
I.2.1 [Artificial Intelligence]: Applications and Expert the positions which have appeared on the chessboard during
Systems—games the chess game. So, the root vertex of the new graph is
the initial position. In this paper, let us name this graph
General Terms extended search tree.
Algorithms There are moves, such as pawn moves or captures, when
the position before the move can not be created after the
Keywords move. Let us say them boundary moves in the extended
search tree. Let us name the position after a boundary move
chess programming, position repetition, move sequences boundary position. To use the definitions more easily, name
the initial position boundary, too. Therefore, all positions
1. INTRODUCTION are boundary or have a boundary position created previously
in the extended search tree.
Among the laws of chess, we can find rules which guaran-
tee that games must end in finite moves. One of them is the The examined position is the position which is just examined
rule of the position repetition. When the same repetition ap- by the chess program.
pears at the third time on the board, any of the players can
ask for a draw. Although the fifty-move rule is easily imple- 3. ALGORITHMS REALIZED IN
mentable in chess programs, the algorithms for recognizing WELL-KNOWN PROGRAMS
position repetitions are very complex and slow. Therefore,
some chess programs omit this rule. This can cause some There are some solutions for recognizing position repeti-
tions[2]. The programs usually recognize the first repetition.
It is enough for the correct control. If one of the players can
make a better move than making a repetition, then the rep-
etition will not appear on the board. If one player can make
a repetition independently from the opponent, then he can
produce easily the position at the third time, too. There-
fore, it is enough to find the first repetition, and it is not
neccessary to wait for the second one. In such a way, the
m a t c o s -1 3 Proceedings of the 2013 Mini-Conference on Applied Theoretical Computer Science 13
Koper, Slovenia, 10-11 October
Chess
Nándor Németh
Eötvös Loránd University
Department of Software Technology and Methodology
nem.nandor@gmail.com
ABSTRACT enormous mistakes, roughly in every second game. Nowa-
days we can find several solutions for the problem in sophis-
A chess game ends in draw if the same position appears for ticated chess programs[2]. Some of the programs use correct
the third time. In a chess program, we need to implement algorithms for the problem. Others use statistically correct
this rule to avoid losing some winning positions, and not methods which run faster, and rarely make mistakes. In
to lose positions, where we have the possibility to make the this paper, the author demonstrates a new correct method
match a draw. Recognizing position repetitions is not trivial for the problem.
problem. The algorithm must run in most of the positions
we reach in the game tree, so it must run quickly. We can 2. DEFINITIONS
read about a lot of algorithms which recognize the repeti-
tions. There are two groups of these algorithms: correct To understand this paper more easily, let us describe some
ones, and statistically correct algorithms having faster so- definitions:
lutions. This paper demonstrates a correct solution which
is simpler and faster than any other correct algorithm, and Two positions are identical if each square of the board con-
it can work with any board representation. We can check tains the same piece, the same player has to move, and the
some statistically correct algorithms quickly with a correct move sentences, the payers can make, are identical, too.
method. Therefore we can get a more faster correct algo-
rithm for the problem. The normal search tree is a graph. The root vertex is the
position we can see on the chessboard. The other vertices are
Categories and Subject Descriptors the positions the program reaches during the search. The
edges represent the moves. Let us extend this tree with all
I.2.1 [Artificial Intelligence]: Applications and Expert the positions which have appeared on the chessboard during
Systems—games the chess game. So, the root vertex of the new graph is
the initial position. In this paper, let us name this graph
General Terms extended search tree.
Algorithms There are moves, such as pawn moves or captures, when
the position before the move can not be created after the
Keywords move. Let us say them boundary moves in the extended
search tree. Let us name the position after a boundary move
chess programming, position repetition, move sequences boundary position. To use the definitions more easily, name
the initial position boundary, too. Therefore, all positions
1. INTRODUCTION are boundary or have a boundary position created previously
in the extended search tree.
Among the laws of chess, we can find rules which guaran-
tee that games must end in finite moves. One of them is the The examined position is the position which is just examined
rule of the position repetition. When the same repetition ap- by the chess program.
pears at the third time on the board, any of the players can
ask for a draw. Although the fifty-move rule is easily imple- 3. ALGORITHMS REALIZED IN
mentable in chess programs, the algorithms for recognizing WELL-KNOWN PROGRAMS
position repetitions are very complex and slow. Therefore,
some chess programs omit this rule. This can cause some There are some solutions for recognizing position repeti-
tions[2]. The programs usually recognize the first repetition.
It is enough for the correct control. If one of the players can
make a better move than making a repetition, then the rep-
etition will not appear on the board. If one player can make
a repetition independently from the opponent, then he can
produce easily the position at the third time, too. There-
fore, it is enough to find the first repetition, and it is not
neccessary to wait for the second one. In such a way, the
m a t c o s -1 3 Proceedings of the 2013 Mini-Conference on Applied Theoretical Computer Science 13
Koper, Slovenia, 10-11 October
