Author: James Swafford
Date: 12:33:36 12/11/02
Go up one level in this thread
On December 11, 2002 at 12:00:12, Edward Seid wrote:
>Please rank the following games in order of mathematical (programming)
>complexity. Also, if you can, provide a degree of magnitude to quantify your
>ranking.
>
>Western Chess
>Shogi
>Go
>Xiangqi (Chinese Chess)
>Othello
>
>Also, feel free to add any other games I didn't include.
I don't quite know what you mean by programming complexity - I don't
think it should be difficult to develop good algorithms (good relative
to others that have done the same) for any of those games.
Solvability is quite another issue. In terms of space complexity,
checkers is by far the smallest, and Go is by far the largest.
Here are some numbers quoted from Schaeffer's "Chips Challenging
Champions" :
game state-space complexity
checkers 10^21
othello 10^28
draughts 10^30
chess 10^46
chinese chess 10^48
shogi 10^71
go (15x15) 10^105
go (19x19) 10^172
I don't have any experience programming any of those other than chess.
I do know that Go is exceptionally difficult, however - even the best
computer Go players are pathetically weak.
Size does matter, afterall. :)
--
James
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.