Although not many people are aware of the fact, but May 2007 was a historical milestone for Computer Checkers (the US 8x8 variant of Draughts).
The Chinook finally solved the game of Checkers, and what everyone already assumed was confirmed, the game is a theoretical draw.
I don't think we will solve the game of Draughts in the next years (> 50 ) .
However it is not unlikely that with larger endgame databases, also computers will become extremely good.
Nowadays only 6 man databases exist, and in some cases already with the limited material on the board, computers come with surprising results.
7-man databases are not yet common. To my knowledge only Dragon (Michael Grimminck) has completed all calculations (which took, i guess, around 200 days). But with present dual-core or quad-core processors and 64bit Windows, this could be done in 2 months max most likely.
I assume that in the cause of 2007 also other programs have all/partly 7-man databases as I (Damage) and Gerard Tailly (Damy) are working on them.
I expect that with 7 man database availability computers will be able to analyse some positions beyond the capabilities of "normal" humans.
In 2008 with Blue-Ray getting available, it will be possible to exchange these databases on DVD, so it will become general available, boosting endgame insights.
8-man databases are for the years to come beyond the capabilities of computers (speed, storage), but i think it is not impossible that around 2009/2010 the first simple 8-man databases could be calculated.
When we really have the availability of these databases, i even think we could finally solve positions like Woldouby.
So keep an eye on computer draughts, we will boldy go where no man has gone before !!
Bert (author Damage)
EndGame Databases
-
Ed Gilbert
- Posts: 860
- Joined: Sat Apr 28, 2007 14:53
- Real name: Ed Gilbert
- Location: Morristown, NJ USA
- Contact:
Hi Bert,
Where did you hear the news about Schaeffer finishing his solutions? I have not seen it yet.
I have been building endgame databases for 10x10 draughts since last year. I have completed all the 2 through 7 piece positions with up to 5 pieces on a side, and I have also built some partial 8-piece and 9-piece subsets. By partial, I mean that I start building slices that are mostly men without having the more king-heavy slices that some of the positions depend on. By skipping the king-heavy slices you can build the most useful ones in much less time. Of course there are some positions that cannot be resolved this way, but it turns out that a very high percentage can be. I have finished all the 4x4 and 5x3 positions with up to one king on each side, and in a day or two I will be done with the 5x4 all checkers slice. I'm not at home at the moment, but if I can remember the sizes correctly, the 2 - 7 pieces is about 30gb, the 8-piece slices are 85gb, and the 9 piece slice is about 11gb. These were all built using 4 rather slow machines that I built in 2004. They could be replaced by one fast dual-core machine.
-- Ed (author of Kingsrow)
Where did you hear the news about Schaeffer finishing his solutions? I have not seen it yet.
I have been building endgame databases for 10x10 draughts since last year. I have completed all the 2 through 7 piece positions with up to 5 pieces on a side, and I have also built some partial 8-piece and 9-piece subsets. By partial, I mean that I start building slices that are mostly men without having the more king-heavy slices that some of the positions depend on. By skipping the king-heavy slices you can build the most useful ones in much less time. Of course there are some positions that cannot be resolved this way, but it turns out that a very high percentage can be. I have finished all the 4x4 and 5x3 positions with up to one king on each side, and in a day or two I will be done with the 5x4 all checkers slice. I'm not at home at the moment, but if I can remember the sizes correctly, the 2 - 7 pieces is about 30gb, the 8-piece slices are 85gb, and the 9 piece slice is about 11gb. These were all built using 4 rather slow machines that I built in 2004. They could be replaced by one fast dual-core machine.
-- Ed (author of Kingsrow)
Ed, you can find the Chinook message here.
"The Chinook project began in 1989 with the goal of developing a program capable of defeating the human World Checkers Champion. In 1990, Chinook became the first program in any game to win the right to play for a human World Championship. The program lost the Championship match in 1992, but became Champion in 1994. By 1996, it became clear that the program was much stronger than any human, and Chinook was retired.
Checkers has a search space of 5x1020, a daunting number. Almost continuously since 1989 (with a gap in the 1997 to 2001 period), dozens of computers have been working around the clock to solve the game. On May 8, 2007, we were pleased to announce that checkers is now solved. From the standard starting position, Black (who moves first) is guaranteed a draw with perfect play. White (moving second) is also guaranteed a draw, regardless of what Black plays as the opening move. Checkers is the largest game that has been solved to date, more than one million times larger than Connect Four and 100 million times larger than Awari."
http://www.ualberta.ca/~kulchits/project/
But the strange thing is that when i tried to find the side this morning I got an error.
Bert
"The Chinook project began in 1989 with the goal of developing a program capable of defeating the human World Checkers Champion. In 1990, Chinook became the first program in any game to win the right to play for a human World Championship. The program lost the Championship match in 1992, but became Champion in 1994. By 1996, it became clear that the program was much stronger than any human, and Chinook was retired.
Checkers has a search space of 5x1020, a daunting number. Almost continuously since 1989 (with a gap in the 1997 to 2001 period), dozens of computers have been working around the clock to solve the game. On May 8, 2007, we were pleased to announce that checkers is now solved. From the standard starting position, Black (who moves first) is guaranteed a draw with perfect play. White (moving second) is also guaranteed a draw, regardless of what Black plays as the opening move. Checkers is the largest game that has been solved to date, more than one million times larger than Connect Four and 100 million times larger than Awari."
http://www.ualberta.ca/~kulchits/project/
But the strange thing is that when i tried to find the side this morning I got an error.
Bert
Ed, i do not completely understand the claims you made.
Do you say you compiled all 2 - 7 man databases for 10x10 International draughts?
You also stated that you have built some 4x4 and 5x3 positions with up to one king on each side. Is this also for 10x10 International Draughts?
What I don't understand, is that you can generate these databases without having compiled first the ones with many kings , as the algorithm we use (made by Michael Grimminck) for generating the files, start first with the king only databases and then move over to databases with also man.
But maybe I missed something?
Bert
Do you say you compiled all 2 - 7 man databases for 10x10 International draughts?
You also stated that you have built some 4x4 and 5x3 positions with up to one king on each side. Is this also for 10x10 International Draughts?
What I don't understand, is that you can generate these databases without having compiled first the ones with many kings , as the algorithm we use (made by Michael Grimminck) for generating the files, start first with the king only databases and then move over to databases with also man.
But maybe I missed something?
Bert
Guess the all 7-man databases together in the end consume between 30G-50G.
So far I only compiled the 5K x 2K (77M) and 2K x 5K (122M) database.
I assume Michael Grimminck can provide the right answer as he has generated all databases.
I don't know the exact capacity of Blue Ray Disk but assuming it is between 15G-20G, and if above mentioned numbers are ok, you "only" need 2 - 3 HD DVD disks to store all.
Bert
So far I only compiled the 5K x 2K (77M) and 2K x 5K (122M) database.
I assume Michael Grimminck can provide the right answer as he has generated all databases.
I don't know the exact capacity of Blue Ray Disk but assuming it is between 15G-20G, and if above mentioned numbers are ok, you "only" need 2 - 3 HD DVD disks to store all.
Bert
-
Ed Gilbert
- Posts: 860
- Joined: Sat Apr 28, 2007 14:53
- Real name: Ed Gilbert
- Location: Morristown, NJ USA
- Contact:
Bert, thanks for the info on Schaeffer. I tried the link but it did not work for me either. I will email him later and ask about it.
> Do you say you compiled all 2 - 7 man databases for 10x10
> International draughts?
Yes. Everything that I mentioned is for 10x10 international draughts.
> What I don't understand, is that you can generate these databases
> without having compiled first the ones with many kings
I generate almost the same way as a complete db, except that some positions are are left as unresolved, and some are only partially resolved. Many positions are resolved through captures into a smaller db for which all the positions are known. Partially resolved positions will assume the value of 'draw or loss', or 'win or draw'. If you are looking at successor positions and you find one win (for the parent), then you know parent position is a win even if the other successors are unknown. If you find one draw, then you know the parent is at least a draw. During the build you have to keep track of 6 possible values instead of just the 3 w/l/d that you do for a complete build.
You might think that you could not resolve a very high percentage of positions doing this, but in fact you can and it works extremely well. I have the exact numbers at home, but if you want to get an rough idea you can see the percentages for the partial 10-piece database that I built for Italian checkers. There is a link to it at the Kingsrow web site.
I first heard about this idea from a Russian checkers programmer named Anton Shevchenko, and I was skeptical but I tried it and it was very successful. I later learned that Schaeffer is using the same technique to build 11-piece and 12-piece subsets for English checkers.
-- Ed
> Do you say you compiled all 2 - 7 man databases for 10x10
> International draughts?
Yes. Everything that I mentioned is for 10x10 international draughts.
> What I don't understand, is that you can generate these databases
> without having compiled first the ones with many kings
I generate almost the same way as a complete db, except that some positions are are left as unresolved, and some are only partially resolved. Many positions are resolved through captures into a smaller db for which all the positions are known. Partially resolved positions will assume the value of 'draw or loss', or 'win or draw'. If you are looking at successor positions and you find one win (for the parent), then you know parent position is a win even if the other successors are unknown. If you find one draw, then you know the parent is at least a draw. During the build you have to keep track of 6 possible values instead of just the 3 w/l/d that you do for a complete build.
You might think that you could not resolve a very high percentage of positions doing this, but in fact you can and it works extremely well. I have the exact numbers at home, but if you want to get an rough idea you can see the percentages for the partial 10-piece database that I built for Italian checkers. There is a link to it at the Kingsrow web site.
I first heard about this idea from a Russian checkers programmer named Anton Shevchenko, and I was skeptical but I tried it and it was very successful. I later learned that Schaeffer is using the same technique to build 11-piece and 12-piece subsets for English checkers.
-- Ed
-
Ed Gilbert
- Posts: 860
- Joined: Sat Apr 28, 2007 14:53
- Real name: Ed Gilbert
- Location: Morristown, NJ USA
- Contact:
> Could you share the code for generating the 10x10 Draughts
> databases, then I could also give it a try?
Bert, if someone asked you to share your souce code for Damage, I think I know what the answer would be :-)
But I am happy to explain how it works, and I think you already know how to do it. You have already written a program for building endgame databases, and this is not a very big addition to be able to build partial databases. You would not want to do it exactly as I did anyway, because I wrote the program several years ago for computers that had limited RAM. My indexing functions are very complicated in order to subdivide the work into small enough pieces to fit in my older machines. Today building databases is much easier. You can get a fast dual or quad core machine with 64-bit windows and lots of RAM, and the program can be much simpler because you can allocate huge buffers to cache the subdivisions that you are building.
-- Ed
> databases, then I could also give it a try?
Bert, if someone asked you to share your souce code for Damage, I think I know what the answer would be :-)
But I am happy to explain how it works, and I think you already know how to do it. You have already written a program for building endgame databases, and this is not a very big addition to be able to build partial databases. You would not want to do it exactly as I did anyway, because I wrote the program several years ago for computers that had limited RAM. My indexing functions are very complicated in order to subdivide the work into small enough pieces to fit in my older machines. Today building databases is much easier. You can get a fast dual or quad core machine with 64-bit windows and lots of RAM, and the program can be much simpler because you can allocate huge buffers to cache the subdivisions that you are building.
-- Ed
Apparantly Checkers is not yet solved, see next message.
May 8, 2007 was the announcement on the new Chinook site that checkers was solved as well as the wiki sites. Martin and Ed should have known this as they are the most active checkers authors (aside from Aurora Borealis Software team with the strong Kallisto engine by Igor Korshunov of Wildcat). There wasn't any comments regarding this on their respective sites as well. Now all information was erased on this site: http://www.ualberta.ca/~kulchits/
The "project" folder containing Chinook team developments was removed, though Google cache still saved the pages. It's pretty rare that the news was released almost a month ago yet Jonathan wasn't aware of this.
This document probably made one of games group member set-up a fast announcement that "checkers is solved".
http://www.cs.potsdam.edu/sigcse07/schaefferTalk.pdf
Bert
May 8, 2007 was the announcement on the new Chinook site that checkers was solved as well as the wiki sites. Martin and Ed should have known this as they are the most active checkers authors (aside from Aurora Borealis Software team with the strong Kallisto engine by Igor Korshunov of Wildcat). There wasn't any comments regarding this on their respective sites as well. Now all information was erased on this site: http://www.ualberta.ca/~kulchits/
The "project" folder containing Chinook team developments was removed, though Google cache still saved the pages. It's pretty rare that the news was released almost a month ago yet Jonathan wasn't aware of this.
This document probably made one of games group member set-up a fast announcement that "checkers is solved".
http://www.cs.potsdam.edu/sigcse07/schaefferTalk.pdf
Bert
-
Ed Gilbert
- Posts: 860
- Joined: Sat Apr 28, 2007 14:53
- Real name: Ed Gilbert
- Location: Morristown, NJ USA
- Contact:
-
Rein Halbersma
- Posts: 1722
- Joined: Wed Apr 14, 2004 16:04
- Contact:
partial information datbases are nicely explained in this paper by the Chinook team:BertTuyt wrote:Ed, i do not completely understand the claims you made.
Do you say you compiled all 2 - 7 man databases for 10x10 International draughts?
You also stated that you have built some 4x4 and 5x3 positions with up to one king on each side. Is this also for 10x10 International Draughts?
What I don't understand, is that you can generate these databases without having compiled first the ones with many kings , as the algorithm we use (made by Michael Grimminck) for generating the files, start first with the king only databases and then move over to databases with also man.
But maybe I missed something?
Bert
http://www.cs.ualberta.ca/~nathanst/pap ... abases.pdf
