EndGame Databases

[Ed Gilbert]

Hi Bert,

I wish I had known about your interface last year when I was designing my own. I might have chosen to try yours, because it was a lot of work to do this and I am more interested in working on the engine. Please email me your interface doc, I would like to read it. You can sent it to "eyg at prodigy dot net". Thanks.

-- Ed

[rusms]

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.

Dr. Schaeffer, an author of Chinook, told me that they solved GAYP (GO-AS-YOU-PLEASE) - major 3-move 20 openings of game. This is less than 13% of the whole game - 156 3-move sound openings.

However, GAYP is classic freestyle form of game which is played professionally more than 200 years, including more than 150 years of human fighting for title.

I think it was a great accomplishment for Chinook team to solve GAYP, but there is long way to go [img]images/smilies/icon_lol.gif[/img]

Respectfully,

Alex Moiseyev
3-move Checkers World Champion

[rusms]

Sorry guys if my "intervention" [img]images/smilies/icon_lol.gif[/img] terminate your very interesting and important dispute about programming issues.

Respectfully,

Alex Moiseyev

[Rein Halbersma]

Sorry guys if my "intervention" [img]images/smilies/icon_lol.gif[/img] terminate your very interesting and important dispute about programming issues.

Respectfully,

Alex Moiseyev

So there is no complete proof yet?
I guess profing the remaining variations is a lot less work, since some of them are quickly losing?

[Ed Gilbert]

So there is no complete proof yet?
I guess profing the remaining variations is a lot less work, since some of them are quickly losing?

Schaeffer has proved that the GAYP game is a draw. In doing this he had to solve about 20 of the 3-move openings. There are no proofs yet for the remaining 136 3-move openings that are played in tournaments, or for another 18 additional that are considered lost.

-- Ed

[steenslag]

Chinook made slashdot: http://games.slashdot.org/games/07/07/19/1952211.shtml

Links from the article:
article in Nature: http://www.nature.com/news/2007/070716/ ... 16-13.html
Very professional website from Chinook:
http://www.cs.ualberta.ca/~chinook/solution/

[TAILLE]

Hi,

Do you think Chinook is the best player (computer or human) of the world ?
My point is the following. Chinook cannot lose a game but in a major tournament it is far from suffisant in order to win this tournament.
For me the major difficulty for a program is not to assure the draw but to create startegic and tactical difficulties in order to win suffisant games to win the tournament. A very strong human player is always very clever to create such difficulties against a weaker player.
In that sense it may happen that it is easier for a weaker player to obtain a draw against Chinook that to obtain the draw against a very strong player. Of course if the weaker player makes a mistake Chonook will not miss the win but do you think Chinook is more efficiant than a very strong player to provoque mistakes ?
What is your feeiling ?

In any case the resolution of the checkers game is a remarkable result !

Gérard

[BertTuyt]

Gerard,
i tend to agree with you.
Basically i see the same in computer draughts tournaments.
In the end mid-game where most programs use 6-piece databases, their play is sometimes quite weird. As they already know ( for example) that the final outcome is a draw , every move which leads towards this draw will be played, independent whether the draw is an easy one or a narrow escape. They will also do the same against human opponents as there is not yet (at least not in my program), a difference between a solid and narrow escape draw.
I think we discussed this already in this forum that we must add something towards normal databases values to create more difficult play for human players.
Also in computer-computer play we need to work on this, as in the next years several programs will still work with 6-piece databases, and don't see as far as their counterparts with 7-pieces.

Bert

[TAILLE]

Gerard,
i tend to agree with you.
Basically i see the same in computer draughts tournaments.
In the end mid-game where most programs use 6-piece databases, their play is sometimes quite weird. As they already know ( for example) that the final outcome is a draw , every move which leads towards this draw will be played, independent whether the draw is an easy one or a narrow escape. They will also do the same against human opponents as there is not yet (at least not in my program), a difference between a solid and narrow escape draw.
I think we discussed this already in this forum that we must add something towards normal databases values to create more difficult play for human players.
Also in computer-computer play we need to work on this, as in the next years several programs will still work with 6-piece databases, and don't see as far as their counterparts with 7-pieces.

Bert

Hi Bert,

For your information, in order to solve a part of this difficulty I am building a new endgame database taking into account the draw+ approach as it is defined for the worldchampionship. For the time being I built the complete 5 pieces db with the 5 results (win, draw+, draw, draw-, lost) and with the asociated DTC db.

As an exemple of the results of the db see the following position :


White to play - draw+
The DTC for this this apparently very simple position is 16 plies !
I guess that even strong players might not find this draw+ in a live game.

Gérard

[Ed Gilbert]

Of course if the weaker player makes a mistake Chonook will not miss the win but do you think Chinook is more efficiant than a very strong player to provoque mistakes ?
What is your feeiling ?

Gerard, I don't think it is true that the Chinook solver can always win if the opponent makes a mistake. The solver has many positions resolved to an upper and lower bound, like {win or draw}, or {draw or loss}. If the opponent moves to a position that is {draw or loss}, the actual value of the position may be {loss} but Chinook does not know that and may not know the path to win.

-- Ed

[rusms]

Gerard, I don't think it is true that the Chinook solver can always win if the opponent makes a mistake.

In order to prove Mr. Gilbert statement, I am giving you here an answer of Dr. Schaeffer on my question. Because there is nothing personal in this information, I think this doesn't break any ethics:

===============================================================

> Another important question is: even if Chinook can play it to draw - does it mean it can win winning position if opportunity arise, or it wasn't a part of proof ?

Good question! If you make a mistake, the prover may know it is a miistake and be able to win. We have not identified all mistakes and shown how to win them.

For example, consider a position P with 4 move. We prove that the first move is a draw. We then show that moves 2, 3 and 4 are not wins. Hence, position P is a draw. If you make the first move, we *know* it is a draw and can demonstrate it. If you make moves 2, 3, and 4. We are only guaranteed to know that they do not win. One of them could be a losing move and we may not know this (we might, it depends on what the prover finds). Of course, we could ask Chinook to take over to look for a win. But Chinook is not perfect, so it is not part of the proof.

===============================================================

[MichelG]

Gerard,

I in the past used a complicated function to determine if white could break through the black defence and promote a man to a king.
But this function mostly dealt with testing if 1 man could promote.
A combination of white and black man was to difficult to implement in "if the else" statements.

These days with large memory and faster processors it is possible to store all combinations for white and black man in a file, and for every combination i do a tree-search to see if white can promote.
In these positions white must move and black is allowed to make a NULL-move ( as i assume that there are more man on the board elsewhere).

Im now testing a file with around 60M positions for white to move.
Positions 1 - 5 and 16 - 20 are black or empty.
Positions 6 - 15 are black/empty/white.
This yields a total of ( 2 ^ 10 ) * ( 3 ^ 10 ), is around 60M.

In the database i store a byte for every position to determine static/dynamic, and the nr. ply to get to a promotion.

Compressed this is ca. 1M (zip compression), so if i apply my own compression is will become somewhat larger.

If after testing is works (i normally do extensive tests for months, before i go to a tournament), i will implement larger databases for breakthrough.

In the end i expect to have a file yielding around 15 * 10^9 positions
( 2^10 ) * ( 3 ^15 ) , so positions 1 - 25. Also i will generate a file for black to move and white to move separately.
The black breakthrough is calculated with the same database but with another indexing function.

Dragon uses pretty much the same way of determening breakthrough positions, but it uses only 1 bit for each position. (per side). On fields 1-5 you have empty/black and fields 6-25 empty/black/white.

If i ever get around to it, i will try to include fields 26-30 as well.

If you do the math, that you would get (2^5)*(3^20)/8*2=2.8 GB of data if you use the 25 fields, and 2 TB if you would use 30 fields.

This exceeds my memory budget, so dragon only computes breakthrough for the 400.000.000 or so most common patterns, reducing memory usage to 100 MB for the first 25 fields. No further compression is required, but winzip compresses the file to 25MB.

In practise these 400M patterns cover more than 99% of positions found in the evaluation nodes.

[ildjarn]

For your information, in order to solve a part of this difficulty I am building a new endgame database taking into account the draw+ approach as it is defined for the worldchampionship. For the time being I built the complete 5 pieces db with the 5 results (win, draw+, draw, draw-, lost) and with the asociated DTC db.

Diagram 4 was de stand na 64...42-48. Terug redenerend kunnen we zeggen dat hier al sprake is van een theoretische puntenoverwinning voor zwart.

Gérard,

The above position was reached in the WHDB championship 2006. The conclusion was 'plusdraw for black'. Is it possible to verify this with the 5 piece plusdraw databases that you have?

[TAILLE]

For your information, in order to solve a part of this difficulty I am building a new endgame database taking into account the draw+ approach as it is defined for the worldchampionship. For the time being I built the complete 5 pieces db with the 5 results (win, draw+, draw, draw-, lost) and with the asociated DTC db.

Diagram 4 was de stand na 64...42-48. Terug redenerend kunnen we zeggen dat hier al sprake is van een theoretische puntenoverwinning voor zwart.

Gérard,

The above position was reached in the WHDB championship 2006. The conclusion was 'plusdraw for black'. Is it possible to verify this with the 5 piece plusdraw databases that you have?

Unfortunately I am not able to give you the answer because it is typically a 6 pieces problem. I have no doubt that black can make a third king but it is not obvious to see if black can then force white to sacrifice one of its men. May be the players of the game can help you .
Gérard

[Rein Halbersma]

Chinook made slashdot: http://games.slashdot.org/games/07/07/19/1952211.shtml

Links from the article:
article in Nature: http://www.nature.com/news/2007/070716/ ... 16-13.html
Very professional website from Chinook:
http://www.cs.ualberta.ca/~chinook/solution/

For those who want to kill an hour and a half with something better than Reality TV, the Tour de France, or other trivial activities, here is Jonathan Schaeffer's talk on the Chinook project:

http://www.cs.ualberta.ca/~chinook/news/media.html

Download the PDF and mp3 and play them simultaneously. Greatest respect for this accomplishment.