Page 16 - 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. 16
this bitboards, the result is nonzero if and only if there is recognizing algorithm prunes branches from the search tree.
a piece-type piece in the square at the examined position. If the program uses greater search depth, the algorithm can
prune longer branches.
5. ANOTHER USE OF THE NUMBER OF
THE MOVED PIECES 6.3 Running time with long move sequences
In some situations the programs can evaluate the positions The algorithm’s running time can move up to 15 times longer
better, if it calculates with the measure of the change of than in average cases. The Axon’s algorithm needs time 3
the position. This defines a distance between two positions. times longer than the new algorithm. Therefore the algo-
The number of the moved pieces is one approximation of its rithm used in Axon is not considered as a linear running-
value. time algorithm. This result was expected.
In the opening moves, the players try to move a lot of pieces 6.4 Using the algorithm to control statistically
to make an open position. In this part of the game, there are correct methods
some pawn moves, too. So, we must extend the algorithm.
Some statistically correct methods make mistakes only if the
In the endgame, when there are long move sequences without examined position isn’t repeated. This type of algorithm can
pawn move or captures, the nearly constant position implies be controlled with correct ones. With the new algorithm,
the draw. If a few pieces move within several plies, it seems the slowdown of the control becomes negligible. Because of
none of the players can make a really good attack. In this the rare repetitions and the very few number of mistakes,
case the program does well to use modified distance in some the mixed algorithm must use only 0.4% more time than a
cases. Its reason is that if the original distance is zero, but simple statistically correct method.
not the same player has to move, then at least 5 plies must
be between the two positions. 7. CONCLUSIONS
Such a use of the number of the moved pieces needs further The author made a new position repetition recognizing al-
research. gorithm for chess. The algorithm is demonstrably correct.
Its running time is linear, as the other correct algorithms.
6. THE RESULTS But it is faster than other correct methods. Programs can
6.1 The test program use the algorithm to control some statistically correct algo-
rithms. This mixed algorithm is correct of course, and has
A test program has been written to compare some algo- a running time as fast as simple statistically correct algo-
rithms for recognizing the repetitions. The compare made rithms. So the author could combine the advantages of the
in several search depth, with alpha-beta and simple minimax two type of repetition recognizing algorithms.
methods[3]. The program used all positions which appeared
in 2010 at the Linares International Chess Tournament. It 8. ACKNOWLEDGMENTS
runs the minimax algorithm at all the positions, and mea-
sures the running times. The author is grateful to his supervisor Tibor Gregorics for
the motivation and the continuous guidance. The author
6.2 Comparsions with other algorithms in av- is also thankful to Istva´n Fekete, because of his valuable
erage case suggestions; and to Ga´bor G´evay, who gave a lot of great
ideas about the algorithm.
In an average case, the new algorithm needed almost half the
time comparing to the Axon’s method[4]. The other correct 9. REFERENCES
algorithms had a little bit more longer running time. The
statistically correct methods were a little bit faster. Their [1] Chess programming - board representation.
great advantage is that the hash keys are needed in other http://chessprogramming.wikispaces.com/
algorithms[3], so the slowdown of the program is smaller Board+Representation, 2012. [Online; accessed
than that of the correct methods. 07-Sept-2013].
The type of the pruning also modifies the running time. The [2] Chess programming - repetitions.
minimax method needs relatively the most extra time if the http://chessprogramming.wikispaces.com/Repetitions,
program uses repetition recognizing algorithm. The alpha- 2013. [Online; accessed 07-Sept-2013].
beta method needs less time. Its reason is the following:
when the program uses pruning, the number of investigated [3] T. Marsland. Computer chess and search. Technical
long move sequences without captures and pawn moves is report, Computing Science Department, University of
less. Alberta, 1992.
The author investigated the running time difference between [4] V. Vuckovic and D. Vidanovic. An algorithm for the
a chess program that uses the new repetition recognizing detection of move repetition without the use of
algorithm, and another one that doesn’t use any repetition hash-keys. Yugoslav Journal of Operations Research,
recognizing algorithm. The program runs a little bit slower 17(2):257–274, September 2007.
with the algorithm. The difference reduces by the growing
of the search depth. The reason may be that the repetition [5] A. L. Zobrist. A new hashing method with application
for game playing. Technical report, Computer Sciences
Department, University of Wisconsin, Madison,
Wisconsin, 1969.
m a t c o s -1 3 Proceedings of the 2013 Mini-Conference on Applied Theoretical Computer Science 16
Koper, Slovenia, 10-11 October
a piece-type piece in the square at the examined position. If the program uses greater search depth, the algorithm can
prune longer branches.
5. ANOTHER USE OF THE NUMBER OF
THE MOVED PIECES 6.3 Running time with long move sequences
In some situations the programs can evaluate the positions The algorithm’s running time can move up to 15 times longer
better, if it calculates with the measure of the change of than in average cases. The Axon’s algorithm needs time 3
the position. This defines a distance between two positions. times longer than the new algorithm. Therefore the algo-
The number of the moved pieces is one approximation of its rithm used in Axon is not considered as a linear running-
value. time algorithm. This result was expected.
In the opening moves, the players try to move a lot of pieces 6.4 Using the algorithm to control statistically
to make an open position. In this part of the game, there are correct methods
some pawn moves, too. So, we must extend the algorithm.
Some statistically correct methods make mistakes only if the
In the endgame, when there are long move sequences without examined position isn’t repeated. This type of algorithm can
pawn move or captures, the nearly constant position implies be controlled with correct ones. With the new algorithm,
the draw. If a few pieces move within several plies, it seems the slowdown of the control becomes negligible. Because of
none of the players can make a really good attack. In this the rare repetitions and the very few number of mistakes,
case the program does well to use modified distance in some the mixed algorithm must use only 0.4% more time than a
cases. Its reason is that if the original distance is zero, but simple statistically correct method.
not the same player has to move, then at least 5 plies must
be between the two positions. 7. CONCLUSIONS
Such a use of the number of the moved pieces needs further The author made a new position repetition recognizing al-
research. gorithm for chess. The algorithm is demonstrably correct.
Its running time is linear, as the other correct algorithms.
6. THE RESULTS But it is faster than other correct methods. Programs can
6.1 The test program use the algorithm to control some statistically correct algo-
rithms. This mixed algorithm is correct of course, and has
A test program has been written to compare some algo- a running time as fast as simple statistically correct algo-
rithms for recognizing the repetitions. The compare made rithms. So the author could combine the advantages of the
in several search depth, with alpha-beta and simple minimax two type of repetition recognizing algorithms.
methods[3]. The program used all positions which appeared
in 2010 at the Linares International Chess Tournament. It 8. ACKNOWLEDGMENTS
runs the minimax algorithm at all the positions, and mea-
sures the running times. The author is grateful to his supervisor Tibor Gregorics for
the motivation and the continuous guidance. The author
6.2 Comparsions with other algorithms in av- is also thankful to Istva´n Fekete, because of his valuable
erage case suggestions; and to Ga´bor G´evay, who gave a lot of great
ideas about the algorithm.
In an average case, the new algorithm needed almost half the
time comparing to the Axon’s method[4]. The other correct 9. REFERENCES
algorithms had a little bit more longer running time. The
statistically correct methods were a little bit faster. Their [1] Chess programming - board representation.
great advantage is that the hash keys are needed in other http://chessprogramming.wikispaces.com/
algorithms[3], so the slowdown of the program is smaller Board+Representation, 2012. [Online; accessed
than that of the correct methods. 07-Sept-2013].
The type of the pruning also modifies the running time. The [2] Chess programming - repetitions.
minimax method needs relatively the most extra time if the http://chessprogramming.wikispaces.com/Repetitions,
program uses repetition recognizing algorithm. The alpha- 2013. [Online; accessed 07-Sept-2013].
beta method needs less time. Its reason is the following:
when the program uses pruning, the number of investigated [3] T. Marsland. Computer chess and search. Technical
long move sequences without captures and pawn moves is report, Computing Science Department, University of
less. Alberta, 1992.
The author investigated the running time difference between [4] V. Vuckovic and D. Vidanovic. An algorithm for the
a chess program that uses the new repetition recognizing detection of move repetition without the use of
algorithm, and another one that doesn’t use any repetition hash-keys. Yugoslav Journal of Operations Research,
recognizing algorithm. The program runs a little bit slower 17(2):257–274, September 2007.
with the algorithm. The difference reduces by the growing
of the search depth. The reason may be that the repetition [5] A. L. Zobrist. A new hashing method with application
for game playing. Technical report, Computer Sciences
Department, University of Wisconsin, Madison,
Wisconsin, 1969.
m a t c o s -1 3 Proceedings of the 2013 Mini-Conference on Applied Theoretical Computer Science 16
Koper, Slovenia, 10-11 October
