Automatically solving chess variants

Internship Motivations

The game of chess has often been presented as "unsolvable" due to the enormous size of the space search. Indeed, it is estimated that the number of legal positions of this game lies around 10^{43} and 10^{50}, and the number of interesting games is roughly 10^{120} (ref. Shannon number). These numbers have to be seen at the light of the number of atoms in the universe which is estimated to 10^{80}.

Nevertheless, using an hybrid human/computer approach, it has been possible to solve a smaller variant of chess on a 5x5 board (see [1]). The space search of this variant is around 10^{20}, roughly equivalent to that of the checkers game on 8x8 board (see [2]). A small web site has been made to gather informations on the solved variants of chess: Mini Chess Resolution.

We have developped some ideas to completely automatize the proof search.

The aim of the internship is to work on them and to extend and ameliorates already implemented ideas and ulitmately to test them on several variants of chess (notably Los Alamos chess and atomic chess).

Internship Objectives

The aim of the internship is to refine the implementation of the oracle finder in a distributed way. More precisely:

Implement an oracle finder that starting from a position builds a formal proof of the theoretical value of the position.
Implement a mate finder based on asymetrical search once an unbalanced position is reached.
Conduct tests to find heuristics in order to downsize the size of the oralces produced. Further researches could investigate machine learning in order to find out those heuristics autmatically.

Location

This intership will be held at the LIG laboratory in Grenoble France in the team CAPP, coached by Frederic Prost.

Requisite skills and abilities

C++ programming
Artificial Intelligence
Ability to modify large programs (typically stockfish)
Curiosity...

References

[1] M. Mahlla and F. Prost. Gardner's minichess is solved. International Computer Games Association Journal, 2013. International Computer Games Association Journal, 36(4), 2013. Article available here.

[2] Jonathan Schaeffer, Neil Burch, Yngvi Bj\"ornsson Akihiro Kishimoto, Martin M\"uller, Robert Lake, Paul Lu and Steve Sutphen. Checkers Is Solved. Science Vol. 317, Issue 5844, pp. 1518-1522, 2007. Article available here.