Page 14 - 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. 14
blem was simplified greatly. The neccessary search depth piece’s original and actual square. If a piece continues its
for recognizing repetitions is reduced to half of the original journey, then the program modifies its actual square. When
depth. a piece reaches its original position, then the program deletes
its record from the data structure. When all of the pieces
moved reached their own original position, there isn’t any
record in the data structure. So, the program recognizes a
position repetition. Of course, the algorithm can manage
the swap of two identical pieces.
To understand this method, let us see a simple example: an
examined position, and a reverse move sequence. In Table
1 we can see, what is stored in the data structure during the
running of the algorithm.
Figure 1: In the original case there are 8 plies nec- Figure 2: The examined position
cessary, but 4-ply search is sufficient for recognizing The reverse move sequence is:
the first repetition Q H6-G5, K H8-G7, Q G5-H6, K G7-H8, (...)
There are two groups of the algorithms we can find in chess Table 1: The data structure during the reverse
programs[2]. The correct methods recognize the repetitions
exactly. The other methods are only statistically correct moves Numbers
ones. Although they make mistakes, they need shorter run- Reverse move The records
ning time.
Q H6-G5 Q H6-G5 1
3.1 Correct algorithms
K H8-G7 Q H6-G5, K H8-G7 2
All of the correct algorithms are based on two control meth-
ods, the position comparing control or the move control. Q G5-H6 Q H6-H6, K H8-G7 2
Both of them run in linear time. Of course, we must exam-
ine all of the positions or moves after the last boundary posi- - K H8-G7 1
tion in the extended search tree. Therefore, the algorithm’s
running time depends on the number of the moves after the K G7-H8 K H8-H8 1
boundary position, linearly. This type of the algorithms can
result significant slowdowns in some move sequences, when -- 0
there are no pawn moves, or captures.
3.2 Statistically correct algorithms
3.1.1 Board-comparing methods
There are some algorithms which are faster than the cor-
The easiest way for the problem is the comparsion of the rect methods, but they make mistakes occassionally. Most
examined position to the previous ones. The more bits define of them use hash keys, and hash tables[5, 3]. If the algo-
the chess board, the slower the algorithm is. There are some rithm uses hash tables, it can run in constant time[3]. This
methods to optimize the algorithm. Of course, we need to is a great advantage against the correct methods in long
investigate only every second position. We can first check for capture-, and pawn-move-free move sequences. The pro-
example the last move’s target square, and next the whole gram doesn’t make really big mistakes frequently, because
table, if there is a same type of piece on this square. mistakes occur rarely, and only a few mistakes cause bad
move on the board, most of them are disappear because of
3.1.2 Computing repetitions from move sequences the minimax algorithm.
In the Axon chess program there is a very interesting algo- 4. THE NEW ALGORITHM
rithm [4] which uses only the moves for recognizing position
repetitions. Let us see the move sequence from the last The paper shows an algorithm based on the method of the
boundary to the examined position. We can easily reverse Axon chess program[4]. The algorithm uses the reverse move
this sequence. The program investigates this reverse move sequence, and the examined position, too, to recognize the
sequence. repetitions. It investigates every reverse move. If all moved
When the program scans the reverse moves sequentially, it
updates a data structure that stores some information about
the moved pieces. In one reverse move a piece can start a
new journey, continue its journey or reach its original posi-
tion. If a piece starts a new journey, the program stores the
m a t c o s -1 3 Proceedings of the 2013 Mini-Conference on Applied Theoretical Computer Science 14
Koper, Slovenia, 10-11 October
for recognizing repetitions is reduced to half of the original journey, then the program modifies its actual square. When
depth. a piece reaches its original position, then the program deletes
its record from the data structure. When all of the pieces
moved reached their own original position, there isn’t any
record in the data structure. So, the program recognizes a
position repetition. Of course, the algorithm can manage
the swap of two identical pieces.
To understand this method, let us see a simple example: an
examined position, and a reverse move sequence. In Table
1 we can see, what is stored in the data structure during the
running of the algorithm.
Figure 1: In the original case there are 8 plies nec- Figure 2: The examined position
cessary, but 4-ply search is sufficient for recognizing The reverse move sequence is:
the first repetition Q H6-G5, K H8-G7, Q G5-H6, K G7-H8, (...)
There are two groups of the algorithms we can find in chess Table 1: The data structure during the reverse
programs[2]. The correct methods recognize the repetitions
exactly. The other methods are only statistically correct moves Numbers
ones. Although they make mistakes, they need shorter run- Reverse move The records
ning time.
Q H6-G5 Q H6-G5 1
3.1 Correct algorithms
K H8-G7 Q H6-G5, K H8-G7 2
All of the correct algorithms are based on two control meth-
ods, the position comparing control or the move control. Q G5-H6 Q H6-H6, K H8-G7 2
Both of them run in linear time. Of course, we must exam-
ine all of the positions or moves after the last boundary posi- - K H8-G7 1
tion in the extended search tree. Therefore, the algorithm’s
running time depends on the number of the moves after the K G7-H8 K H8-H8 1
boundary position, linearly. This type of the algorithms can
result significant slowdowns in some move sequences, when -- 0
there are no pawn moves, or captures.
3.2 Statistically correct algorithms
3.1.1 Board-comparing methods
There are some algorithms which are faster than the cor-
The easiest way for the problem is the comparsion of the rect methods, but they make mistakes occassionally. Most
examined position to the previous ones. The more bits define of them use hash keys, and hash tables[5, 3]. If the algo-
the chess board, the slower the algorithm is. There are some rithm uses hash tables, it can run in constant time[3]. This
methods to optimize the algorithm. Of course, we need to is a great advantage against the correct methods in long
investigate only every second position. We can first check for capture-, and pawn-move-free move sequences. The pro-
example the last move’s target square, and next the whole gram doesn’t make really big mistakes frequently, because
table, if there is a same type of piece on this square. mistakes occur rarely, and only a few mistakes cause bad
move on the board, most of them are disappear because of
3.1.2 Computing repetitions from move sequences the minimax algorithm.
In the Axon chess program there is a very interesting algo- 4. THE NEW ALGORITHM
rithm [4] which uses only the moves for recognizing position
repetitions. Let us see the move sequence from the last The paper shows an algorithm based on the method of the
boundary to the examined position. We can easily reverse Axon chess program[4]. The algorithm uses the reverse move
this sequence. The program investigates this reverse move sequence, and the examined position, too, to recognize the
sequence. repetitions. It investigates every reverse move. If all moved
When the program scans the reverse moves sequentially, it
updates a data structure that stores some information about
the moved pieces. In one reverse move a piece can start a
new journey, continue its journey or reach its original posi-
tion. If a piece starts a new journey, the program stores the
m a t c o s -1 3 Proceedings of the 2013 Mini-Conference on Applied Theoretical Computer Science 14
Koper, Slovenia, 10-11 October
