World Draughts Forum

It is currently Sun Sep 24, 2017 02:32

All times are UTC+01:00




Post new topic  Reply to topic  [ 290 posts ]  Go to page 1 2 3 4 520 Next
Author Message
 Post subject: EndGame Databases
PostPosted: Fri Jun 08, 2007 11:08 
Offline

Joined: Wed Sep 01, 2004 18:42
Posts: 1294
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)


Top
   
 Post subject:
PostPosted: Fri Jun 08, 2007 12:13 
Offline

Joined: Sun Aug 18, 2002 15:43
Posts: 2020
Real name: Alexander Presman
Location: the Netherlands
Hello Bert,

How big is (will be) the 7-man database?


Top
   
 Post subject:
PostPosted: Fri Jun 08, 2007 12:54 
Offline

Joined: Sat Apr 28, 2007 13:53
Posts: 725
Real name: Ed Gilbert
Location: Morristown, NJ USA
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)


Top
   
 Post subject:
PostPosted: Fri Jun 08, 2007 13:13 
Offline

Joined: Wed Sep 01, 2004 18:42
Posts: 1294
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


Top
   
 Post subject:
PostPosted: Fri Jun 08, 2007 13:16 
Offline

Joined: Sun Aug 18, 2002 15:43
Posts: 2020
Real name: Alexander Presman
Location: the Netherlands
Hello Ed,

Interesting. But how can you build slice 5x4 without having complete 8 man database. And what happens if a man in 5x4 or 4x4 becomes king? Then position belongs already to the absent subset.


Top
   
 Post subject:
PostPosted: Fri Jun 08, 2007 13:23 
Offline

Joined: Wed Sep 01, 2004 18:42
Posts: 1294
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


Top
   
 Post subject:
PostPosted: Fri Jun 08, 2007 13:35 
Offline

Joined: Wed Sep 01, 2004 18:42
Posts: 1294
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


Top
   
 Post subject:
PostPosted: Fri Jun 08, 2007 14:17 
Offline
User avatar

Joined: Tue Aug 22, 2006 14:38
Posts: 1336
Real name: Joost de Heer
Since Stef Keetman wrote a couple of articles about 5x2 endgames in 1999 in Dammen, I assume he has the full set of databases too.

_________________
Lasst die Maschinen verhungern, Ihr Narren...
Lasst sie verrecken!
Schlagt sie tot -- die Maschinen!


Top
   
 Post subject:
PostPosted: Fri Jun 08, 2007 14:17 
Offline

Joined: Sat Apr 28, 2007 13:53
Posts: 725
Real name: Ed Gilbert
Location: Morristown, NJ USA
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


Top
   
 Post subject:
PostPosted: Fri Jun 08, 2007 14:21 
Offline

Joined: Wed Sep 01, 2004 18:42
Posts: 1294
Sounds really interesting Ed.
Could you share the code for generating the 10x10 Draughts databases, then I could also give it a try?

Bert


Top
   
 Post subject:
PostPosted: Fri Jun 08, 2007 22:04 
Offline

Joined: Sat Apr 28, 2007 13:53
Posts: 725
Real name: Ed Gilbert
Location: Morristown, NJ USA
> 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


Top
   
 Post subject:
PostPosted: Fri Jun 08, 2007 22:21 
Offline

Joined: Wed Sep 01, 2004 18:42
Posts: 1294
Ed, if you would ask for code not related to the search or evaluation function i would share it without any problems.

Bert


Top
   
 Post subject:
PostPosted: Fri Jun 08, 2007 23:03 
Offline

Joined: Wed Sep 01, 2004 18:42
Posts: 1294
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


Top
   
 Post subject:
PostPosted: Fri Jun 08, 2007 23:17 
Offline

Joined: Sat Apr 28, 2007 13:53
Posts: 725
Real name: Ed Gilbert
Location: Morristown, NJ USA
Schaeffer said that they were setting up a new web page in anticipation of an annnouncement later this year, and someone stumbled across it.


Top
   
 Post subject:
PostPosted: Sat Jun 09, 2007 09:32 
Offline

Joined: Wed Apr 14, 2004 15:04
Posts: 1550
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


partial information datbases are nicely explained in this paper by the Chinook team:

http://www.cs.ualberta.ca/~nathanst/pap ... abases.pdf


Top
   
Display posts from previous:  Sort by  
Post new topic  Reply to topic  [ 290 posts ]  Go to page 1 2 3 4 520 Next

All times are UTC+01:00


Who is online

Users browsing this forum: No registered users and 3 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
cron
Powered by phpBB® Forum Software © phpBB Limited