Author: Russell Reagan
Date: 21:01:22 05/05/02
Go up one level in this thread
On May 05, 2002 at 06:54:48, Uri Blass wrote: >how many possible positions are in 8*8 checkers? > >I think that there are only 32 squares and 4 kind of pieces and it means that >5^32 is an upper bound for the number of position(a square may be empty) > >5^32 is only an upper bound and the number of practical positions to analyze may >be clearly smaller. > >If you also remember that you probably do not need to search until the end of >the game in order to play the best move then it seems that checkers is a game >that is likely to be solved in the near future if it is not practically solved >today. In addition to that, in draughts they have 8 man endgame tablebases as opposed to the incomplete 6 man tablebases chess has. Since there are fewer pieces on the board in draughts to begin with (24 in draughts, 32 in chess) this is even more significant. In addition to THAT, there are (relative to chess) fewer moves to look at in each position. Since each piece can only move to either 2 or 4 squares, it's less. In addition to that, a lot of the moves are clearly losing after only a few ply of search, so you have a lower branching factor, in addition to faster move generation and search because of the simplicity of the game, you can search deeper in a shorter amount of time (compared to chess). For example, a freeware draughts program searched to 13 ply in 0.86 seconds. Fritz on my same machine takes 1 minute and 20 seconds to reach 13 ply. So, chess's top programs can't search anywhere near as deep as a freeware draughts program, and I imagine that Chinook probably reaches even greater depths than this simple freeware draughts program. Fritz gets around 300 Knps on my machine, and this simple draughts program gets 650 Knps. In a 1 minute search, Fritz reaches ply 12. Freeware draughts program reaches ply 17 at 10 s. I personally don't see how any human could contend with even a simple draughts playing program given it's more tactical nature than chess, but apparently Marion Tinsley was able to contend with Chinook before he died, although I think Chinook won the match. But I think Tinsley had one game where he forfeited or something. I'm not sure what happened really. Russell
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.