Page 15 - 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. 15
ces during the reverse moves reach a square which con- pieces swap their positions. In the example, only the white
tains the same type of piece in the examined position, then moves are shown. The coloumn ”Cases” shows which of the
the position is repeated. Let us name the pieces which are four cases is applied.
standing on a square which doesn’t contain the same type
of piece in the examined position as moved pieces. In the Figure 3: Swap of two knights
examined position the number of the moved pieces is zero. The reverse move sequence is:
When it will be zero again, the algorithm finds a repetition. N C5-E6, N E6-F4, N D3-C5, K F4-C5, (...)
Sometimes it can happen that two identical pieces swap their
position. In this case there can be repetition. Therefore, if Table 2: The modifying of the number of the moving
a piece reaches a square which contains a same-type piece
in the examined position, the algorithm considers it as the pieces
end of its journey.
Reverse move Moving pieces Case
This number is similar to the number of the records in the
Axon. The great observation is that we need no data struc- -0 -
tures, only this number, to recognize repetitions.
N C5-E6 0 + (1 + 0) = 1 1
4.1 The basis of the algorithm
N E6-F4 1 + (0 + 0) = 1 3
The algorithm modifies the number of the moved pieces in
every reverse move. When the algorithm starts to make a N D3-C5 1 + (1 − 1) = 1 4
move, it investigates the from-square of the move. If the N F4-C5 1 + (0 − 1) = 0 2
square in the examined position contains a piece which has
the same type as the moving piece, then a piece starts a new 4.2 Optimizing the algorithm in array-based
journey, so the number of moved pieces increases by one. In
other cases, its value doesn’t change. board representation
The algorithm then investigates the to-square. If it contains The algorithm is good, but we can do some optimizations.
a same-type piece in the examined position, a piece ends its The program must stop the reverse moves at the point,
journey. Therefore, the number of moved pieces decreases where the algorithm recognized the repetition, or where there
by one. In other cases, its value doesn’t change. can’t be any repetitions. When there are less than four plies
distance from the last boundary position to the examined
So, we have 2 · 2 = 4 cases. In the first case, the moving one, then players can’t make repetitions. Sometimes a lot of
piece starts a new journey, and it doesn’t finish the journey pieces move. If there isn’t the neccessary number of moves
at the end of the move. Then, the algorithm increases the to end all of the moved pieces’ journey, then the algorithm
number of the moving pieces by one. stops the search for repetitions. Considering the fact that
only every second position can be identical with the exam-
In the second case, when a piece ends its journey. Of course, ined position, it is better if the algorithm investigates two
the algorithm decreases the number by one. plies during one running of the body of the loop.
In the third case, when a piece continues its journey. So, 4.3 The method with bitboard representations
it has some moves, but it may make a big tour before it
finishes its journey. In this case the number of the moving We can define a condition(piece,square) boolean function
pieces doesn’t change. which gives true if the square contains piece-type piece in
the examined position, and gives false in other cases. With
The fourth case can happen very rarely. In this situation, a this function, we can generalize the algorithm for any type
piece starts its journey, and ends it at the end of the move. of board representation[1].
In this case, the number of the moving pieces increases and
decreases at the same time, so its value doesn’t change. If a program uses bitboard representation, the function can
be seen as follows: Let us consider the bitboard which stores
This algorithm is enough for managing the number of the the position of the piece-type pieces. Let us make an other
moving pieces. Its great advantage is that it needs no extra bitboard which has only one non-zero bit. This bit is the bit
data structure. It can manage the swapping of the pieces of the square. If the algorithm uses the xor binary operator
similarly with a piece which reaches its starting square dur-
ing the reverse moves. In the Axon chess program the pro-
grammers had to implement two different algorithms for the
problem. The running time of the algorithm is stable. In
the Axon, the running time depends on the number of the
moved pieces.
The running of the algorithm is usually similar to the run-
ning of the algorithm of the Axon. In Figure 2, the two
algorithms are similar, but the new one uses only one num-
ber. Let us see, how the algorithm works, when two identical
m a t c o s -1 3 Proceedings of the 2013 Mini-Conference on Applied Theoretical Computer Science 15
Koper, Slovenia, 10-11 October
tains the same type of piece in the examined position, then moves are shown. The coloumn ”Cases” shows which of the
the position is repeated. Let us name the pieces which are four cases is applied.
standing on a square which doesn’t contain the same type
of piece in the examined position as moved pieces. In the Figure 3: Swap of two knights
examined position the number of the moved pieces is zero. The reverse move sequence is:
When it will be zero again, the algorithm finds a repetition. N C5-E6, N E6-F4, N D3-C5, K F4-C5, (...)
Sometimes it can happen that two identical pieces swap their
position. In this case there can be repetition. Therefore, if Table 2: The modifying of the number of the moving
a piece reaches a square which contains a same-type piece
in the examined position, the algorithm considers it as the pieces
end of its journey.
Reverse move Moving pieces Case
This number is similar to the number of the records in the
Axon. The great observation is that we need no data struc- -0 -
tures, only this number, to recognize repetitions.
N C5-E6 0 + (1 + 0) = 1 1
4.1 The basis of the algorithm
N E6-F4 1 + (0 + 0) = 1 3
The algorithm modifies the number of the moved pieces in
every reverse move. When the algorithm starts to make a N D3-C5 1 + (1 − 1) = 1 4
move, it investigates the from-square of the move. If the N F4-C5 1 + (0 − 1) = 0 2
square in the examined position contains a piece which has
the same type as the moving piece, then a piece starts a new 4.2 Optimizing the algorithm in array-based
journey, so the number of moved pieces increases by one. In
other cases, its value doesn’t change. board representation
The algorithm then investigates the to-square. If it contains The algorithm is good, but we can do some optimizations.
a same-type piece in the examined position, a piece ends its The program must stop the reverse moves at the point,
journey. Therefore, the number of moved pieces decreases where the algorithm recognized the repetition, or where there
by one. In other cases, its value doesn’t change. can’t be any repetitions. When there are less than four plies
distance from the last boundary position to the examined
So, we have 2 · 2 = 4 cases. In the first case, the moving one, then players can’t make repetitions. Sometimes a lot of
piece starts a new journey, and it doesn’t finish the journey pieces move. If there isn’t the neccessary number of moves
at the end of the move. Then, the algorithm increases the to end all of the moved pieces’ journey, then the algorithm
number of the moving pieces by one. stops the search for repetitions. Considering the fact that
only every second position can be identical with the exam-
In the second case, when a piece ends its journey. Of course, ined position, it is better if the algorithm investigates two
the algorithm decreases the number by one. plies during one running of the body of the loop.
In the third case, when a piece continues its journey. So, 4.3 The method with bitboard representations
it has some moves, but it may make a big tour before it
finishes its journey. In this case the number of the moving We can define a condition(piece,square) boolean function
pieces doesn’t change. which gives true if the square contains piece-type piece in
the examined position, and gives false in other cases. With
The fourth case can happen very rarely. In this situation, a this function, we can generalize the algorithm for any type
piece starts its journey, and ends it at the end of the move. of board representation[1].
In this case, the number of the moving pieces increases and
decreases at the same time, so its value doesn’t change. If a program uses bitboard representation, the function can
be seen as follows: Let us consider the bitboard which stores
This algorithm is enough for managing the number of the the position of the piece-type pieces. Let us make an other
moving pieces. Its great advantage is that it needs no extra bitboard which has only one non-zero bit. This bit is the bit
data structure. It can manage the swapping of the pieces of the square. If the algorithm uses the xor binary operator
similarly with a piece which reaches its starting square dur-
ing the reverse moves. In the Axon chess program the pro-
grammers had to implement two different algorithms for the
problem. The running time of the algorithm is stable. In
the Axon, the running time depends on the number of the
moved pieces.
The running of the algorithm is usually similar to the run-
ning of the algorithm of the Axon. In Figure 2, the two
algorithms are similar, but the new one uses only one num-
ber. Let us see, how the algorithm works, when two identical
m a t c o s -1 3 Proceedings of the 2013 Mini-Conference on Applied Theoretical Computer Science 15
Koper, Slovenia, 10-11 October
