An Example of Positions Computers Cannot Play Optimally

Discussion and analysis about certain positions.

An Example of Positions Computers Cannot Play Optimally

Postby EdTrice on Thu Mar 22, 2007 8:23 pm

More than one reader of Bob Newell's website has sent me emails regarding the "Perfect Play" databases, and why I think probing them in RAM (rather than just reading them off of disk as WCC Platinum III does now) is so important.

I have found a recent example from an over-the-board game that should demonstrate the power of Perfect Play databases over other databases, if you would probe them in RAM.

Image

The above position is a 7x7 where red to move can win. The question is: what is the best move?

I have found that computers make a variety of mistakes in handling the position, although surely they all win, they take a very long time to complete the win.

An 8-piece database program will play the odd-looking convoluted in-and-out shot:

3-7?! 12x3, 14-18 22x15[1] 10x19x26, 3x10 6x15 which is now a 4x4 loss for white to move.

[1] Or 23x14 10x17x26 leading to the same position.

This leads to the position shown below:

Image

Even with white to move, red crowns the king far enough ahead of the opponent to eventually get a 1-holding-2 situation and win in a tried and true fashion. The win does take a great many moves, although quite a few of the required moves are straightforward to solve over-the-board.

But is this the best way to win? Not if you use the length of the game as a metric to judge the performance.

How would a 10-piece database play this position? It turns out, since the 5x5 position is close at hand, the weak side will pitch a piece to avoid entering the database, and the strong side will return the piece to get into it! Such "cooperative" play is an undesired effect of probing the win-loss-draw databases: A 5x5 position that might take over 200 moves to win is always given a higher score than a 6x5 that is NOT in an "11-piece database" that could swap all the way down to a 2x1 in short order. The reason, again, is because no "distance to win" information is present in the database.

Here is how a 10-piece database program would proceed:

10-15! 21-17?![2], 14x21 22-17, 15-19?![3] 23x16, 8-11 16x7, 2x11 landing in a 5x5 where it is again white to move and lose.

[2] White pitches a piece to be only "down one piece", typically a -100 score if positive is better, but at least this is better than -2500, a typical database loss score.

[3] Red would rather go for a +2500 database win score in a 5x5 that is forced as opposed to maintaining the +100 score that would inevitably lead to more material being won in the very near future.

Image

Again, it is easy to recognize that white will strand pieces on the side of the board since red has command and control of the center region with both guards intact. But this also results in a very long game.

So, what happens if you turn off the 10-piece database but keep your 9-piece database active? This produces some interesting play from the parent position:

10-15! 22-17, 15-18 17x10, 18x27 20-24![4], 6x15 16-11!, 15-18 11x4, 18-22!! 4-8, 2-7

Image

This is more along the lines that a "human" might play, and it appears to be on target for the shortest win of the solutions so far. While this is a 10-piece position that is white to move and lose, the 9-piece database had no +/-2500 score for the database win/loss, so it had to rely on its evaluation function to guide its play. Since it can see the win of the piece to enter into a 9-piece +2500 score, the program elected to be up one piece in its databases rather than be in a 4x4 with equal material (a general hueristic that may or may not be a part of various programs.)

The point of all of this: All of the above solutions were NOT the best way to play this elementary 7x7 checkers position!

Having a Perfect Play Database probed in RAM during the search allows a program to announce the Distance To Win from the parent position, always allowing it to play optimally along the way, providing faster winning solutions than all of the above play.

Given that there are 210,267,794,000 positions featuring 7 checkers vs. 7 checkers, you can imagine there are many, many ways that a program with a Perfect Play database probed in RAM can cut through all of the clutter and win in very short order.

This is what the Only Perfect Checkers program will be able to do once it is complete.

See http://www.OnlyPerfectCheckers.com in the summer of 2007 for an update. (The site is very much incomplete at this exact moment.)
--Ed
User avatar
EdTrice
 
Posts: 97
Joined: Fri Jul 14, 2006 2:39 am
Location: Philadelphia

Return to Positions

Who is online

Users browsing this forum: Google [Bot] and 2 guests

class=