EGTB value

[bob]

Hi,

I am really upset by this discussion because I cannot imagine having a large EGTB without being able to improve my program. You cannot accept such failure.
In my draughts program I effectively use a large EGTB but I had to work hard in order to use it efficiently. Several conditions seem necessary to reach an improvement of your program:
1) The first one was already mentioned : you have to analyze when it could be useful to accept an I/O and when you have to avoid it
2) The second and major point is to keep in your hash table the information relating to the draw result of a position
This second point is the most important and need some more explanations. Suppose for example that the tree root position is an advantageous position for white. As a consequence, black would be happy to find a draw. Now take node1 of the tree where it is black to play and where it exists a black move assuring a draw according to the EGTB. You can and you must keep in your hastable that node1 is “at least a draw” for black. That way, when you will reach again node1 (typically with a higher remaining depth) you will be able to stop the search without generating the subtree and without using again the time consuming EGTB.
Without this mechanism you can hardly improve your program by using an EGTB.
Has somebody try to use this approach?

I store EGTB position hit results in the hash table, always have. The problem is, in checkers you can hit egtbs from the starting position. In chess, no chance.

[Gerard Taille]

I store EGTB position hit results in the hash table, always have.

Very good indeed because it is not that usual. The point is that the two following statements are very different :
1) With a remaining depth of D the node 1 is at least a draw
2) With whatever remaining depth the node 1 is at least a draw
The second statement is very strong and can be obtain only by EGTB hits and by handling specifically the propagation of this information towars the upper levels of the tree.

The problem is, in checkers you can hit egtbs from the starting position. In chess, no chance.

I am not a checkers player but a 10x10 international draughts game player. Like chess there are no chance to hit egtbs in the beginning of the game

[wgarvin]

Since there are fewer piece types than Chess, the EGTBs are considerably more powerful for checkers/draughts. You don't need as many different databases to cover all the piece combinations up to N pieces, and the total size of the databases doesn't increase as much as you increase N.

I think the checkers program Chinook by Schaeffer et al. is considered the world champion at 8x8 checkers, since the early 90's. It had EGTBs for all positions with 8 or fewer pieces on the board, and if you asked it to search the initial position, its search was deep enough that it would already be probing those databases. (On modern hardware I bet it can search deep enough from the initial position to see a large number of EGTB positions.) A few years ago they actually managed, with the aid of those databases, to prove that with perfect play by both sides, the game-theoretic value of 8x8 checkers is a draw--neither player is able to force a win from the initial position.


Anyway, for 10x10 draughts, the databases might be a little less powerful than the 8x8 ones, because of the larger board. But probably still more useful than in Chess.

[Gerard Taille]

Since there are fewer piece types than Chess, the EGTBs are considerably more powerful for checkers/draughts. You don't need as many different databases to cover all the piece combinations up to N pieces, and the total size of the databases doesn't increase as much as you increase N.

I think the checkers program Chinook by Schaeffer et al. is considered the world champion at 8x8 checkers, since the early 90's. It had EGTBs for all positions with 8 or fewer pieces on the board, and if you asked it to search the initial position, its search was deep enough that it would already be probing those databases. (On modern hardware I bet it can search deep enough from the initial position to see a large number of EGTB positions.) A few years ago they actually managed, with the aid of those databases, to prove that with perfect play by both sides, the game-theoretic value of 8x8 checkers is a draw--neither player is able to force a win from the initial position.


Anyway, for 10x10 draughts, the databases might be a little less powerful than the 8x8 ones, because of the larger board. But probably still more useful than in Chess.

Yes, I agree that 10x10 draughts EGTB are certainly more powerful for draughts than for chess for at least two major reasons :
1) As you noticed there are fewer pieces type in draughts. As a consequence, in 10x10 international draughts, the EGTB can be build with about 2 more pieces. For your information the 7 pieces EGTB needs about 20Gb and the 8 pieces EGTB needs about 350Gb.
2) It seems that a draughts 7 or 8 pieces endgame is far more difficult to play than a 5 or 6 pieces endgame in chess (I mean only in practice because I perfectly know that some very improbable endgame positions are extremely complex in chess)

IMO nobody knows what perfect play is.
Let’s assume that the chess EGTB has been built up to 32 pieces i.e. for all possible positions and let’s assume that the initial position is really a draw. Of course a program with such EGTB will never lose but that is not the point. In chess (it is the same in draughts) the goal of a grand master is to complicate the game so has the opponent will eventually make a fatal mistake and lose the game. The chess grandmaster evaluation function is very elaborate because it takes into account some probability for the opponent to make a mistake. When a grandmaster says their opponent has made a mistake (but not a decisive mistake) that only means that the game becomes more difficult for the opponent in the sense that it is easier for the opponent to make a fatal mistake.
With only the 32 pieces EGTB a program will be very poor indeed. In a match in 100 games or more against a very strong player (but not a grandmaster) this program will obtain very few wins indeed and a grandmaster against the same strong player will obtain a far better result even if this grandmaster lose maybe one or two games.
As you see a program with the 32 pieces EGTB need still a heuristic and an evaluation function in order to improve the probability for the opponent to make a mistake.
I am not sure that I am very clear in my explanations but I confess I am unable to define what a perfect play is in draw position.
For a winning position it is more or less obvious : the perfect play is obtained by the distance to mat information.

[Gerard Taille]

Since there are fewer piece types than Chess, the EGTBs are considerably more powerful for checkers/draughts. You don't need as many different databases to cover all the piece combinations up to N pieces, and the total size of the databases doesn't increase as much as you increase N.

I think the checkers program Chinook by Schaeffer et al. is considered the world champion at 8x8 checkers, since the early 90's. It had EGTBs for all positions with 8 or fewer pieces on the board, and if you asked it to search the initial position, its search was deep enough that it would already be probing those databases. (On modern hardware I bet it can search deep enough from the initial position to see a large number of EGTB positions.) A few years ago they actually managed, with the aid of those databases, to prove that with perfect play by both sides, the game-theoretic value of 8x8 checkers is a draw--neither player is able to force a win from the initial position.


Anyway, for 10x10 draughts, the databases might be a little less powerful than the 8x8 ones, because of the larger board. But probably still more useful than in Chess.

Yes, I agree that 10x10 draughts EGTB are certainly more powerful for draughts than for chess for at least two major reasons :
1) As you noticed there are fewer pieces type in draughts. As a consequence, in 10x10 international draughts, the EGTB can be build with about 2 more pieces. For your information the 7 pieces EGTB needs about 20Gb and the 8 pieces EGTB needs about 350Gb.
2) It seems that a draughts 7 or 8 pieces endgame is far more difficult to play than a 5 or 6 pieces endgame in chess (I mean only in practice because I perfectly know that some very improbable endgame positions are extremely complex in chess)

IMO nobody knows what perfect play is.
Let’s assume that the chess EGTB has been built up to 32 pieces i.e. for all possible positions and let’s assume that the initial position is really a draw. Of course a program with such EGTB will never lose but that is not the point. In chess (it is the same in draughts) the goal of a grand master is to complicate the game so has the opponent will eventually make a fatal mistake and lose the game. The chess grandmaster evaluation function is very elaborate because it takes into account some probability for the opponent to make a mistake. When a grandmaster says their opponent has made a mistake (but not a decisive mistake) that only means that the game becomes more difficult for the opponent in the sense that it is easier for the opponent to make a fatal mistake.
With only the 32 pieces EGTB a program will be very poor indeed. In a match in 100 games or more against a very strong player (but not a grandmaster) this program will obtain very few wins indeed and a grandmaster against the same strong player will obtain a far better result even if this grandmaster lose maybe one or two games.
As you see a program with the 32 pieces EGTB need still a heuristic and an evaluation function in order to improve the probability for the opponent to make a mistake.
I am not sure that I am very clear in my explanations but I confess I am unable to define what a perfect play is in draw position.
For a winning position it is more or less obvious : the perfect play is obtained by the distance to mat information.

[rbarreira]

You are definitely right that a 32-piece EGTB may not be enough for playing at the best performance. If the initial position was drawn, there would still be room for improvement by adding opponent modelling (an EGTB assumes the opponent plays perfectly).

[bob]

I store EGTB position hit results in the hash table, always have.

Very good indeed because it is not that usual. The point is that the two following statements are very different :
1) With a remaining depth of D the node 1 is at least a draw
2) With whatever remaining depth the node 1 is at least a draw
The second statement is very strong and can be obtain only by EGTB hits and by handling specifically the propagation of this information towars the upper levels of the tree.

The problem is, in checkers you can hit egtbs from the starting position. In chess, no chance.

I am not a checkers player but a 10x10 international draughts game player. Like chess there are no chance to hit egtbs in the beginning of the game

With 10x10 maybe not from the opening, but I'll bet you get hits _way_ before we do in chess. In chess, _most_ games are resolved before the endgame arrives and hits start to happen... I'll try to gather some ICC game statistics, but I'd bet that 9 of every 10 games is decided before EGTBs have an influence on the game with respect to the information they contain. Yet they always have an effect on endgame play due to the overhead of the probes...

[bob]

Since there are fewer piece types than Chess, the EGTBs are considerably more powerful for checkers/draughts. You don't need as many different databases to cover all the piece combinations up to N pieces, and the total size of the databases doesn't increase as much as you increase N.

I think the checkers program Chinook by Schaeffer et al. is considered the world champion at 8x8 checkers, since the early 90's. It had EGTBs for all positions with 8 or fewer pieces on the board, and if you asked it to search the initial position, its search was deep enough that it would already be probing those databases. (On modern hardware I bet it can search deep enough from the initial position to see a large number of EGTB positions.) A few years ago they actually managed, with the aid of those databases, to prove that with perfect play by both sides, the game-theoretic value of 8x8 checkers is a draw--neither player is able to force a win from the initial position.


Anyway, for 10x10 draughts, the databases might be a little less powerful than the 8x8 ones, because of the larger board. But probably still more useful than in Chess.

Perhaps you missed the announcement, but chinook has _solved_ the 8x8 variant of the game already, and proven that the game is a draw with perfect play unless a lost starting position is reached via imperfect play, of course. They can search from the starting position to reach the endgame tables on every branch... We can't even get EGTB hits from the opening position...

[Gerard Taille]

With 10x10 maybe not from the opening, but I'll bet you get hits _way_ before we do in chess. In chess, _most_ games are resolved before the endgame arrives and hits start to happen... I'll try to gather some ICC game statistics, but I'd bet that 9 of every 10 games is decided before EGTBs have an influence on the game with respect to the information they contain. Yet they always have an effect on endgame play due to the overhead of the probes...

Yes you are completly correct; I will not bet with you on this point. As you know a capture move is a mandatory move in draughts and it is then easy, from a middle game position, to play a very bad combination which reaches the EGTB. In the PV however I think the situation is similar in the two games.
But the point is not here because if you reach the EGTB position from a middle game position, after a bad combination, you will necessarily not satisfy the criteria allowing you to make a too time consuming I/O.
My view is the following :
1) If there are non real uncertainty in the tree root position (quite equal position or obviouly winning or losing position) the use of an EGTB brings probably nothing and costs a lot of time. It is certainly a good idea to avoid allowing an I/O on the disk in this case.
2) If the tree root position is quite uncertain (white or black has a good advantage but it is far for obvious to know if the position is a winning one) then the EGTB may be of great help on condition to use it on purpose i.e. when you are "near" the PV.
In other word : in the first part of the game (typically till a point between the 35th and the 45th of the game) you must avoid losing time by I/O on the disk and you have to concentrate your effort to build advantageous posiiton. As soon as you reach a quite good position but still with a very uncertain result I think you can decide to use the EGTB providing it is made on purpose along the PV or near the PV. In any case you must also avoid using the EGTB for position where the result is quite obvious (significant material advantage or obviously equal position).

[Roger Brown]

Yes you are completly correct; I will not bet with you on this point. As you know a capture move is a mandatory move in draughts....

Hello Gerard,

I was all set to refute this statement abouut the mandatory capture but then I noticed that it seems as if the huffing rule has indeed fallen out of favour.

Sigh.

Wouldn't the retention of that rule (huffing) make the game more interesting? I mean, why shouldn't I be able to sacrifice a piece and move if I deem that the best move as I could (not the move though) in chess?

Later.