Perfect Play

[BertTuyt]

At 1 hour/game, the programs are probably only 100-200 elo points away from perfect play anyway.

I tend to agree with Michel that we might be close to perfect play from an ELO point of view.
As we already discussed in the past, the expected score P ( 1 = win, 0.5 = draw, and 0.0 is lost) of a very good program against a perfect program , can (may be) approximated by:

Code: Select all

P = 0.5* (1- N*Error), with N : the Number of moves where the program can make an error, and Error the error rate/move

When the program enters the late middle game / endgame phase and all probes are into the Endgame Databases, than from that point onwards the program plays perfect. As a perfect program (by definition) will also play perfect, the expected outcome from that point onwards does not change. A conservative estimation is N = 50 (so excluding a well tested opening book).

The recent 158 games match between Scan and Kingsrow, but also between Dragon and Kingsrow suggest that the error rate might be close to 10E-3 (0.001), so 1 fatal/lethal mistake every 1000 moves or every 20 games (which yield around 8 losses in a 158 games match).

With an error rate of 0.001, the P (with N = 50) becomes P = 0.475

The expected outcome of a match where the Elo difference is DElo, can be expressed (here Im not sure if I picked the right formula):

Code: Select all

P = 1 / ( 1 + 10^DElo/400)

With P = 0.475 this yields DElo = 17, remarkably small, so this approximation might be oversimplified, but nevertheless we migh have seen more ELO gain in the past, than ahead.

Bert

[BertTuyt]

Is there some information related to the error rate of Grandmasters.
And with error I mean not a (small) positional error but decisive errors which create a loss, or an error which does not convert a win game, but yielding a draw?

I expect that for players like Sybrands this is close to 0.0001 ( 10E-4), so every 200 games (calculating with 50 moves/game), they make a real error (or blunder).
Think with Computer Draughts we are not yet there...

Bert

[Rein Halbersma]

Is there some information related to the error rate of Grandmasters.
And with error I mean not a (small) positional error but decisive errors which create a loss, or an error which does not convert a win game, but yielding a draw?

I expect that for players like Sybrands this is close to 0.0001 ( 10E-4), so every 200 games (calculating with 50 moves/game), they make a real error (or blunder).
Think with Computer Draughts we are not yet there...

Bert

Hi Bert,

see my post in the Matches thread. I don't think programs are near perfect play because the drawing margin (438 ELO points!) is too high and shields a lot of subtle positional errors. All the high drawing rates proves is that most programs have similar knowledge and search and are more or less equally efficient. But a new breakthrough piece of knowledge or search technique could still give a lot of improvement.

Rein

[Fabien Letouzey]

see my post in the Matches thread. I don't think programs are near perfect play because the drawing margin (438 ELO points!) is too high and shields a lot of subtle positional errors. All the high drawing rates proves is that most programs have similar knowledge and search and are more or less equally efficient. But a new breakthrough piece of knowledge or search technique could still give a lot of improvement.

I agree with you that match results don't prove by themselves that perfect play is near. It reminds me of the Awari situation in the early 00's. Below is an extract from "Awari Is Solved". However I assume that Bert is using additional knowledge (such as "XXX goes deep" experiments) to estimate the error rate.

---
Although the programs made more errors than expected, they did not play badly. MARVIN did the right move in 82% of the cases, and SOFTWARI in 87% of the cases. On average, MARVIN lost 0.27 points per move, and SOFTWARI 0.25 points (losing a point means: giving the opponent the opportunity to capture one stone more). At this rate, we estimate that the programs would lose with about 27–21 when playing against our database.
---

I'm not sure that top draughts programs have similar knowledge and, compared to other games, most of search either.

[Rein Halbersma]

I'm not sure that top draughts programs have similar knowledge and, compared to other games, most of search either.

I compared the sources for Scan and Senpai a bit. Obviously there is quite a bit of overlap. Can you tell us something how the search and tree shape for chess differs from draughts? E.g., which enhancements from chess were hard to translate (or hard to tune) to draughts?

[MichelG]

see my post in the Matches thread. I don't think programs are near perfect play because the drawing margin (438 ELO points!) is too high and shields a lot of subtle positional errors. All the high drawing rates proves is that most programs have similar knowledge and search and are more or less equally efficient. But a new breakthrough piece of knowledge or search technique could still give a lot of improvement.

I agree with you that match results don't prove by themselves that perfect play is near. It reminds me of the Awari situation in the early 00's. Below is an extract from "Awari Is Solved". However I assume that Bert is using additional knowledge (such as "XXX goes deep" experiments) to estimate the error rate.
...
I'm not sure that top draughts programs have similar knowledge and, compared to other games, most of search either.

I think that Bert's and mine opinion on near perfect play are just gut feelings. We see that when the search-depth increase, more and more draws occur. I think it is a possibility that we are nearing perfection, but i am not sure about it.

What we do know for sure, is that the path of increasing search depth and knowledge will not increase winning rate very much. You can test easily what happens if your program is given 2, 100 or 1000 times more search time, while the opponent stays on the same time. The thing is, that if you want one program to be noticeably stronger than another, you need an incredible number of improvements in your program. Making a program running at twice the nodes/second would maybe give you a 51-49 advantage, which is a bit frustrating as a programmer; if you play a too short (eg. 100 game) match, you would not even be able to statistically show that the faster program is better.

There may be other algorithms that could yield high win rates against the current top programs. For example, if you could fully solve the game, and use opponent modeling against the searching programs. And there may be new algorithms to be discovered, like MCTS did in many games.

[BertTuyt]

In the past I have done some Damage selfplay tests to see what the error rate is as a function of depth. I agree with Rein that the actual error might be higher, as programs sometimes (even at higher search depths) can not capitalize on a huge advantage. For a perfect program however, I dont think there is a valid concept for weak or strong position (or positional error) as the program only recognizes a win - draw or lost position. As we discussed during the Olympics, a perfect program could sacrisfice a man in the opening if the database says that the resulting 19-20 position is a draw.

Also when you read Sybrands analysis on a regular basis, you read often 'in this position white or black made the final positional mistake, and move xx (although hard to find) is a draw, but was not find due to stress and time constraints'. From a computer perspective one can state that apparently so far in the game non of the moves was a decisive error.

Below the test I have done (and I recognize that one need to play more games (and go much deeper) for statistic sound results

Code: Select all

Depth    Draw%
4          46
5          50
6          52
7          71
8          68
9          75
10         83
11         79
12         83

I tried to find an optimal curve and apparently Pdraw = ( 1 - exp(-C*depth)) worked well.
See below picture ( ln(1-Pdraw) versus depth).

If you assume that Pdraw = (1 - 100 *ErrorRate), see previous discussion, than the ErrorRate is around 1E-3 at ply 15 ( 1E-4 at ply 30)
There is however no further mathematics to support the formula, but at least it provides some ballpark figures.

Bert

[BertTuyt]

In the game Damage - Scan, Damage sacrified 2 man as according to the search/evaluation the postion was anyway a draw. Im sure no normal being would have done this, as the resulting position was a (difficult) 2P - 5P position, but for the computer all draws are equal. So from the computer perspective this was a sound move, altough humans would/could consider this as a positional mistake.

I guess that all (top) programs might start playing perfect from move 40 - 50 onwards, perfect in this context implies no moves are made which alter the game state (win, draw,lost).

I also recognize that it might be easier to optimize a program for non-loosing, and that optimization for winning is more difficult and requires concepts like opponent modellling (as also Michel pointed out).

Bert

[Fabien Letouzey]

I compared the sources for Scan and Senpai a bit. Obviously there is quite a bit of overlap. Can you tell us something how the search and tree shape for chess differs from draughts? E.g., which enhancements from chess were hard to translate (or hard to tune) to draughts?

I think that the resemblance is mostly superficial and probably in big part due to the SMP implementation. I view Scan as an Othello program (patterns + ProbCut) with a draughts move generator.

I haven't had the time to get familiar with draughts search. Chess is 95% tactics so anything you do in search has to address that.

Compared to chess I am missing low-depth pruning, like FP and LMP. It's possible that the tactical blindness of ProbCut (deadly in chess) makes this more difficult. Or maybe I should reconsider my usual separation at depth 3 for draughts ...

[TAILLE]

In the game Damage - Scan, Damage sacrified 2 man as according to the search/evaluation the postion was anyway a draw. Im sure no normal being would have done this, as the resulting position was a (difficult) 2P - 5P position, but for the computer all draws are equal. So from the computer perspective this was a sound move, altough humans would/could consider this as a positional mistake.

I guess that all (top) programs might start playing perfect from move 40 - 50 onwards, perfect in this context implies no moves are made which alter the game state (win, draw,lost).

I also recognize that it might be easier to optimize a program for non-loosing, and that optimization for winning is more difficult and requires concepts like opponent modellling (as also Michel pointed out).

Bert

Hi,

I agree with you Bert : we have to distinguish a program optimized for non-loosing and a program optimised for winning.
BTW what is perfect play? Suppose a program having the 40 pieces db and suppose the initial position lead to a draw according to this theoritical egdb. Suppose 1.31-27 garanties the draw and suppose that the db tells you that after the sacrifice 1...16-21 Black can still get a draw!! Do you conclude 1.31-27 16-21 is perfect play? For a non-loosing program IT IS a perfect play but for winning program it is certainely not, is it?

I agree also that opponent modelling is a good concept and in the past I developed a program made to provoque errors when you have the 8 pieces db and you play against a 7 pieces db.

Gérard