Solving techniques, and 8 solved positions.

Recently, I found a document that explain how the team of University of Alberta manage to solve Checkers.

They use a proof procedure that had 4 different algorithm/data components:
1-Endgame Database
2-Proof tree manager
3-Proof solver
4-Expert Seeding.

I was happy to see that we use all these components and even more, let explain this.

1-Endgame Database, currently all Azor use at minimum the 3 pieces EGTB, and some use the 4 pieces EGTB. All 4 pieces positions are directly send to Azor who have the 4 pieces EGTB. It sure that I need to reduce EGTB size to be able to send all 4 pieces EGTB to all Azor, and to be able to generate the 5 pieces EGTB. So at least we use this components for solving, but need improvements.

2-Proof tree manager, it’s the name give from University of Alberta, to something like the opening book. This permit to see the progress of the solving tree. Recently we start to use symmetry in the opening book to reduce the search tree. It’s useful in near end game. Like for the checker , here on suicidechess, we use this tree as a transposition table, to avoid recalculate the same positions many times, and to reduce the search tree again. The proof tree manager it’s the visible part of the project.

3- Proof solver. On suicidechess we call it Azor. Currently Azor use only one algorithm , the Proof-Number Search. This algorithm have been great for any Suicide chess engine. To quote Stanisvla Goldovski: « To restrict your opponent, you will not only need material advantage, but also advantage in mobility and space. » That exactly the purpose of Proof-Number Search. In a unclear position, the Proof-Number Search will give advantage to the player who have more mobility. The Azor is made to be able to install on most computer, to increase the speed of solving.

4-Expert Seeding. Even with a good algorithm, and a lot of CPU power, nothing can beat the knowledge of human. Human can give advice, that it will be prove as right after a lot of cpu cycle. That’s why on suicidechess, users can choose what will be next position to be calculate. Some suicide expert said that giving your b-pawn at the start of the game is dangerous, current analyses like the opening 1.b4 or 1.e3 b5 tend to prove it.

Solving suicide chess, is a long task to do. For checker which is a simpler game in term of complexity, it took 18 years. So even with better CPU power, I think we won’t be able to do it in less time. Suicidechess project had start in June 2007 , even if we took the same amount of time to solve it, that lead use to 2025. But even checker are solve, there still exist world championship of checker, because human can memorize all positions, and in these competition, the first three move are random ( up to 174 different position). In chess, you can use the 960 different starting position also known as Fisher chess. I don’t know if I’ll be alive to see all 960 positions solved, but at least I already saw 8 of these positions solved. Yep you read it right, 8 starting positions are solved are the list:
bbnrkqnr/pppppppp/8/8/8/8/PPPPPPPP/BBNRKQNR
bbrnkqnr/pppppppp/8/8/8/8/PPPPPPPP/BBRNKQNR
brnbkqnr/pppppppp/8/8/8/8/PPPPPPPP/BRNBKQNR
brnkqbnr/pppppppp/8/8/8/8/PPPPPPPP/BRNKQBNR
rnqkrnbb/pppppppp/8/8/8/8/PPPPPPPP/RNQKRNBB
rnqknrbb/pppppppp/8/8/8/8/PPPPPPPP/RNQKNRBB
rnqkbnrb/pppppppp/8/8/8/8/PPPPPPPP/RNQKBNRB
rnbqknrb/pppppppp/8/8/8/8/PPPPPPPP/RNBQKNRB

As you may saw 4 last one are symmetry of the 4 first one. A other proof that symmetry is important.

Laisser un commentaire

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l'aide de votre compte WordPress.com. Déconnexion / Changer )

Image Twitter

Vous commentez à l'aide de votre compte Twitter. Déconnexion / Changer )

Photo Facebook

Vous commentez à l'aide de votre compte Facebook. Déconnexion / Changer )

Photo Google+

Vous commentez à l'aide de votre compte Google+. Déconnexion / Changer )

Connexion à %s