Posted by: zyxo | May 8, 2009

Game complexity


Just some complexity numbers :

Number of possible combinations for the following games :

four in a row : 10 exp(14)
checkers : 10 exp(23)
chess : 10 exp(50)
game of go : 10 exp(171) The most complexe of all ! That is why computers still cannot beat the human masters !

Enhanced by Zemanta

Responses

  1. Can you post the resource/reference of these estimations?

  2. @breakingkeyboards :
    I had the number for 4 in a row, chess and Go from a recent -paper/hardcopy- issue of http://www.natutech.nl/ (in dutch).
    For checkers I found an answer in http://answers.yahoo.com/question/index?qid=20070807230233AAzv1AP.
    Although, afterwards I also found this paper : http://www.cs.ualberta.ca/~jonathan/Papers/Papers/ijcai05checkers.pdf
    I admit, I did not care very much of the accuracy of the numbers, it was just the idea of the relative magnitudes that I thought was interesting.
    Zyxo

  3. Thinking to the games the estimations seem correct.
    Thank you for the references Zyxo


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Categories

%d bloggers like this: