Examining Champion Tinsley's Moves

[mschribr]

Many have claimed former world champion Marion Tinsley played nearly perfect 8x8 checkers. Today's programs do play nearly perfect 8x8 checkers. Has anyone compared Tinsley's moves to today's computer's moves? Would he have won all those games if he had played against today's computers?
Mark Schreiber

[Ed Gilbert]

Mark, in order to win at checkers your opponent has to make a mistake, because it is a drawn game. The strongest 8x8 programs now do not make mistakes in tournament play, so Tinsley would have no chance to win, and as good as he was, he would eventually make a mistake and lose a game.

-- Ed

[mschribr]

Ed, you are right Tinsley could not have won those games. But Tinsley was such a great player maybe in some of his games he played perfectly. So he would still have drawn the games. It would be interesting to see what percentage of Tinsley’s moves was perfect? Or did Tinsley play any games where he played perfectly? Mark Schreiber

[steenslag]

This is from a translated review on "One jump ahead" by Jonathan Schaeffer - the Chinook guy. The source is a German chess magazine. Apparently, the translator wrote the chess program Hydra .

(...)The dominating person in checkers was Dr. M. Tinsley. The mathematician and laymen-pastor [Prediger] had an unbelievable match record. In 40 years, from 1951 to 1991, he lost out of about 1000 tournament games a total of three. Until 95 2 more against Chinook would be added. In comparison, Capablanca had lost in 30 years out of 571 tournament games 43. Even with checkers being much closer to draw then chess, this is an unbelievable performance. On top of that, in the most widespread form, the three move ballot, the first three half moves are are drawn. Each player is then playing white and black in this "random" position. Even with openings analogous to 1.a4 d5 2.h4 - Tinsley could not be bent. In preparation for the first orld championship match in 1992 Schaeffer analyzed with Chinook more than 700 Tinsley-games for tactical mistakes. Chinook found within search depths of 17-20 no even a single tactical error.(...)

source: http://www.cs.ualberta.ca/~jonathan/OJA/donninger.html

(slightly off topic) The review mentions an interesting phenomenon: with larger endgame databases the program lost less games (perfectly understandable); the wins also diminished (huh?).

[mschribr]

Review of One jump ahead by Jonathan Schaeffer
(...) In preparation for the first orld championship match in 1992 Schaeffer analyzed with Chinook more than 700 Tinsley-games for tactical mistakes. Chinook found within search depths of 17-20 no even a single tactical error.(...)

Schaeffer used Chinook’s own evaluation not an endgame database to decide if Tinsley made a mistake. He used the 1990 Chinook to do deep searchs. He found Tinsley made only 1 mistake in 732 games, not counting losing games. In 1990 Schaeffer was too optimistic about Chinook performance. The 1990 Chinook was not good enough to tell us if Tinsley made a mistake. Today’s faster computers play perfectly because they could look all the way till they reach the bigger endgame databases. I think today’s computers and bigger endgame databases could tell us conclusively how many mistakes Tinsley made.

[TAILLE]

Schaeffer used Chinook’s own evaluation not an endgame database to decide if Tinsley made a mistake. He used the 1990 Chinook to do deep searchs. He found Tinsley made only 1 mistake in 732 games, not counting losing games. In 1990 Schaeffer was too optimistic about Chinook performance. The 1990 Chinook was not good enough to tell us if Tinsley made a mistake. Today’s faster computers play perfectly because they could look all the way till they reach the bigger endgame databases. I think today’s computers and bigger endgame databases could tell us conclusively how many mistakes Tinsley made.

I know what you mean when you say that a computer plays "perfectly" but it is only a theoretical point of view. In draughts game (and I guess it is the same in checkers game) the best players begin classicaly by accumulating very small advantages that put their opponents in positions more and more difficult. The "fatal" error itself may happen by example at the 40th move or latter but it is the result of all the previous moves. In this exemple everybody will recognise that the first 40 moves of the weaker player where not perfect although the reached position is still a draw !
In this sense, do you really think Chinook plays perfectly ? Of course it will never lost the game but does it play that good ?
Gérard

[mschribr]

I know what you mean when you say that a computer plays "perfectly" but it is only a theoretical point of view. In draughts game (and I guess it is the same in checkers game) the best players begin classicaly by accumulating very small advantages that put their opponents in positions more and more difficult. The "fatal" error itself may happen by example at the 40th move or latter but it is the result of all the previous moves. In this exemple everybody will recognise that the first 40 moves of the weaker player where not perfect although the reached position is still a draw !
In this sense, do you really think Chinook plays perfectly ? Of course it will never lost the game but does it play that good ?
Gérard

Gérard,
Maybe I used the words perfect play incorrectly. There should be only 1 level of perfect play. Perfect play for checkers is a 24 piece endgame database. To have the best move for every position that will force the win in the fewest moves. Or if winning is not possible then the move that forces the draw or loss in the most moves. Hoping the opponent will make a mistake when he has to make more moves. Chinook does not play at this level.

The next highest level of play is when you never allow the game score to get worse. So if the position is a win then your move will keep you winning. The move will not force the shortest win. Or if the position is a draw then your move will not allow you to lose. More than 1 move can be found to qualify for this level of play. Chinook will use the first 1 found. This I believe is the level of play Chinook has found for GAYP Checkers.

I would like to know when Tinsey was winning did he frequently make moves that allowed a draw or a loss. But his opponents made even worse moves allowing Tinsey to win. What percentage of moves gave the opponent an opportunity to win. I don’t think Chinook plays at the level good enough to find tinsey’s mistakes. But I think we can do an exhaustive search on everyone of tinsey’s moves till we reach the endgame databases. It should not take too long to do a search for each move.
Mark

[TAILLE]

Gérard,
Maybe I used the words perfect play incorrectly. There should be only 1 level of perfect play. Perfect play for checkers is a 24 piece endgame database. To have the best move for every position that will force the win in the fewest moves. Or if winning is not possible then the move that forces the draw or loss in the most moves. Hoping the opponent will make a mistake when he has to make more moves. Chinook does not play at this level.

The next highest level of play is when you never allow the game score to get worse. So if the position is a win then your move will keep you winning. The move will not force the shortest win. Or if the position is a draw then your move will not allow you to lose. More than 1 move can be found to qualify for this level of play. Chinook will use the first 1 found. This I believe is the level of play Chinook has found for GAYP Checkers.

I would like to know when Tinsey was winning did he frequently make moves that allowed a draw or a loss. But his opponents made even worse moves allowing Tinsey to win. What percentage of moves gave the opponent an opportunity to win. I don’t think Chinook plays at the level good enough to find tinsey’s mistakes. But I think we can do an exhaustive search on everyone of tinsey’s moves till we reach the endgame databases. It should not take too long to do a search for each move.
Mark

Mark
Concerning a winning position I agree that the perfect play if the move that force the win in the fewest move.
Concerning a draw or losing position the definition of a perfect play is far more difficult for me.
In my opinion, the best suite of moves in a losing position is not the moves that garantee the most moves before the loss, but the moves that cause the most difficulties for the opponent. In a losing position I think we have to look for moves where the "normal" answer will not win and where the winning answer is not so obvious. A very long suite of moves where the winning answer is very easy to find is certainly not a perfect way to play.
Concerning a draw position I do not understand your criteria for a perfect move. You intend to force the draw in the most moves but basically there is no real end for the game (except some rules limiting the number of move without any conversion). Here again the best moves for me are those creating the maximum difficulties for your opponent.
You can see clearly the issue : how can you decide that a move cause difficulties for the opponent ? I intend to test new algorithms in Damy in order to take into account this issue.
May be I am wrong but I think that Tinsey will have better results than Chinnook when playing against strong players. The reason is that, in draw positions, Tinsey will be able to create difficulties for the opponent where Chinook will not have this ability (at least for the moment).
Gérard

[mschribr]

Gérard
I think the longest series of moves is hardest because of time pressure. There is less time per move. Also the short series of moves are easier to visualize for humans than long series of moves. So the long series of moves will not be as obvious. Draws must end when there is no conversion.

How does the computer find positions where the "normal" answer will not win and where the winning answer is not so obvious? Maybe positions with the most pieces under attack to create more complexity. It would be interesting to compare which strategy beats more people.
Mark

[TAILLE]

Gérard
I think the longest series of moves is hardest because of time pressure. There is less time per move. Also the short series of moves are easier to visualize for humans than long series of moves. So the long series of moves will not be as obvious. Draws must end when there is no conversion.

How does the computer find positions where the "normal" answer will not win and where the winning answer is not so obvious? Maybe positions with the most pieces under attack to create more complexity. It would be interesting to compare which strategy beats more people.
Mark

Hi Mark,

It is not that difficult to build difficult traps in order to improve the probability to win when the position is a draw or the probability to obtain a draw when the position is a loss.
Let’s take the following example I discussed on the French draughts forum


White to move.

As a lot of programs Damy explore the tree of possibilities by increasing the depth of the exploration.
In the above position, at level 14, Damy find 7 moves which are somewhat equivalent :
38-32 : +0,07
41-36 : +0,05
47-42 : +0,00
44-40 : -0,01
43-39 : -0,01
44-39 : -0,04
41-37 : -0,05

What is the best move to try to win when the position seems really a draw ?

For me the key point is the possibility to set a difficult trap for the opponent.

After 38-32 there is the trap 23-29?? but it is too obvious (level 1 for Damy)
After 44-40 there is the trap 23-29 ?? but this trap is not too difficult to avoid (level 4 for Damy)
After 43-39 there is the trap corresponding to the combination 26-21, 38-32 (level 1 for Damy)
After 44-39 there is the trap corresponding to the combination 26-21, 38-32 (level 1 for Damy) but also the trap 17-22?? (level 9 for Damy), the trap 09-13?? (level 9 for Damy) and the trap 23-29?? (level 4 for Damy)
After 41-37 there is the trap 23-29?? (level 5 for Damy)

Seeing this analysis the move 44-39 seems a good tricky move but we have to verify a last point. If after 44-39 I put Damy on level 8 (that way Damy cannot find the level 9 traps) then the best move for Damy is 17-22??
We are in ideal situation. The best play to try to win is 44-39!! with a good chance that the opponent plays 17-22 or 09-13.

For the time being I did not program this kind of algorithm in Damy. Knowing that such algorithm may be very CPU consuming I think it is not a good idea when the opponent is another computer. If the opponent is a human I guess it is a very interesting idea to test !

Of course there are some very interesting work to do. First of all the alpha-beta procedure must be modified. An idea also might be to take the multi-processor opportunity to look for traps etc.

Gérard

[MichelG]

For me the key point is the possibility to set a difficult trap for the opponent.

After 38-32 there is the trap 23-29?? but it is too obvious (level 1 for Damy)
After 44-40 there is the trap 23-29 ?? but this trap is not too difficult to avoid (level 4 for Damy)
After 43-39 there is the trap corresponding to the combination 26-21, 38-32 (level 1 for Damy)
After 44-39 there is the trap corresponding to the combination 26-21, 38-32 (level 1 for Damy) but also the trap 17-22?? (level 9 for Damy), the trap 09-13?? (level 9 for Damy) and the trap 23-29?? (level 4 for Damy)
After 41-37 there is the trap 23-29?? (level 5 for Damy)

Seeing this analysis the move 44-39 seems a good tricky move but we have to verify a last point. If after 44-39 I put Damy on level 8 (that way Damy cannot find the level 9 traps) then the best move for Damy is 17-22??
We are in ideal situation. The best play to try to win is 44-39!! with a good chance that the opponent plays 17-22 or 09-13.

For the time being I did not program this kind of algorithm in Damy. Knowing that such algorithm may be very CPU consuming I think it is not a good idea when the opponent is another computer. If the opponent is a human I guess it is a very interesting idea to test !

Gérard

I believe opponent modelling can be build into existing programs fairly easy and without sacrificing to much computing time.

Before you start the normal alfabeta-search, you play each move and check for traps. 44-40 gives the level 4 trap 23-29.

You can award extra scores for each trap. Lets say a level 4 trap awards +0.05 score, a level 6 trap +0.08 score and a level 8 trap +0.10 score. If there are multiple traps, just add up the scores for that move. Scores depend on your opponent. If you play the world champion, a 6 ply trap has no value because he will always see the trap. He might however miss a 12 ply trap.

Computing traps can be done fast because you only need to consider material traps, and you don't need to do lots of positional evaluation. Further more, there is a class of traps that can be computed extremely quickly: only consider positions where you give away a checker, and the opponent is forced to capture. You need at most a 15 ply search, as there exists no deeper traps than this, and it can be done in milliseconds.

After computing the value for 44-40, you add the trap-score to the normal AB-score.

Note however that on the second and other moves you have to examine, you need to do this with an alfa-bound lowered by its trap-score, and this will slow down the program.

Example ab-search:

Code: Select all

move (alfa,beta) : ab-result  trapscore   overall score
38-32 (-inf,inf)   +0.07      0.00           +0.07
44-40 (-0.03,inf)  -0.01      0.10           +0.09
41-36 (0.09,inf)   <0.09      0.00           <0.09

etc

This algorithm results in the program searching to a lower depth overall (maybe 0.2 plies on avarage), but will play a lot stronger against opponents that make tactical mistakes. (aka humans) In any case, the program will play more human-like.

Michel