Arimaa Forum
        (http://arimaa.com/arimaa/forum/cgi/YaBB.cgi)
      

        Arimaa >> Off Topic Discussion >> 8x8 Draughts/Checkers: solved!
        
(Message started by: IdahoEv on Jul 20th, 2007, 12:38pm)
Title: 8x8 Draughts/Checkers: solved!
Post by IdahoEv on Jul 20th, 2007, 12:38pm
The game of 8x8 Draughts (i.e. Checkers) was announced weakly solved yesterday: with perfect play either player can force a draw from the starting position.

The team even has a website online where you can play against a database of perfect replies!  It's built on Chinook, which was already the world champion AI.

http://www.cs.ualberta.ca/~chinook/

Here's the story at Nature.com:

http://www.nature.com/news/2007/070716/full/070716-13.html

Checkers has a statespace of 5*10^20 positions.   Anyone know how many Arimaa has?
Title: Re: 8x8 Draughts/Checkers: solved!
Post by DorianGaray on Jul 23rd, 2007, 1:40am

on 07/20/07 at 12:38:19, IdahoEv wrote:
The game of 8x8 Draughts (i.e. Checkers) was announced weakly solved yesterday: with perfect play either player can force a draw from the starting position.

The team even has a website online where you can play against a database of perfect replies!  It's built on Chinook, which was already the world champion AI.

http://www.cs.ualberta.ca/~chinook/

Here's the story at Nature.com:

http://www.nature.com/news/2007/070716/full/070716-13.html

Checkers has a statespace of 5*10^20 positions.   Anyone know how many Arimaa has?

My guess would be very close to how many Chess has.

I hear it's about 1*10^120.
Title: Re: 8x8 Draughts/Checkers: solved!
Post by UruramTururam on Jul 23rd, 2007, 2:21am
Arimaa position space is surely lower than the space of Chess - because of pawn promotions. Yet I think that the number of positions that could appear in really played games is bigger in Arimaa.
Title: Re: 8x8 Draughts/Checkers: solved!
Post by JacquesB on Jul 23rd, 2007, 5:31am
The search space in checkers is 10^20 not 120!

This is taken form:

http://www.cs.ualberta.ca/~jonathan/Grad/Papers/ijcai05checkers.pdf

The paper expains how to solve checkers and was written by the team who solved checkers, but before their last achievement. I guess there will be a new paper soon.
Title: Re: 8x8 Draughts/Checkers: solved!
Post by woh on Jul 23rd, 2007, 6:20am

on 07/23/07 at 01:40:39, DorianGaray wrote:
My guess would be very close to how many Chess has.

I hear it's about 1*10^120.


At Nature.com (see 2nd link posted by IdahoEv) they claim that the statespace of chess is 10^46.
Title: Re: 8x8 Draughts/Checkers: solved!
Post by IdahoEv on Jul 23rd, 2007, 5:47pm
Yes, chess is definitely not 10^120.    Even go is "only" 10^100.
Title: Re: 8x8 Draughts/Checkers: solved!
Post by IdahoEv on Jul 23rd, 2007, 5:48pm
The pawn promotion argument is good - Chess probably has a larger statespace than Arimaa.  So Arimaa's difficulty for AI comes primarily from the branch factor, not the statespace.
Title: Re: 8x8 Draughts/Checkers: solved!
Post by Fritzlein on Jul 23rd, 2007, 6:01pm
I am skeptical of the small (!) number 10^46 for the state space of chess.  The state of a game of chess (or Arimaa) includes not only the board position, but also the list of moves that led up to the position.  Without the past move list you can't know what future moves will create draw (or loss) by repetition.  In Arimaa one could theoretically have goal in two on the board, but actually be forced to lose in five because the only winning move would lead to three-fold repetition.

Well, OK, I guess you only need to remember the positions since the last capture/promotion/pawn advance, and their order doesn't matter.  Even so, to get the true number of states, it seems one must multiply the number of board positions by a large factor representing possible previous board positions that could have led up to it, sort of like a reverse game tree.
Title: Re: 8x8 Draughts/Checkers: solved!
Post by Fritzlein on Jul 23rd, 2007, 6:17pm

on 07/23/07 at 01:40:39, DorianGaray wrote:
My guess would be very close to how many Chess has.

I hear it's about 1*10^120.

10^120 is actually an estimate for the game-tree size of chess, not the number of possible states.  If you take a branching factor of 30, and say a game of chess lasts about 40 moves (i.e. 80 half-moves), you can calculate 30^80 = 1.478 * 10^118.

Now, many positions in that tree will be repeats of each other.  But some of the "repeats" will be distinct states in my book due to having different histories, and therefore different repetition possibilities.
Title: Re: 8x8 Draughts/Checkers: solved!
Post by RonWeasley on Jul 23rd, 2007, 8:00pm
zzzzzz...(*) Ow!


*Sound of Snape hitting the back of my head with a book.
Title: Re: 8x8 Draughts/Checkers: solved!
Post by The_Jeh on Jul 24th, 2007, 12:10am
In standard checkers, jumps are forced. But in another popular variation (which I prefer), jumps are not obligatory. Have both variations been solved, then?
Title: Re: 8x8 Draughts/Checkers: solved!
Post by arimaa_master on Jul 24th, 2007, 2:16am

on 07/23/07 at 05:31:10, JacquesB wrote:
I guess there will be a new paper soon.



New paper is here: http://www.sciencemag.org/cgi/rapidpdf/1144079v1.pdf?ijkey=jVmVcXy2/NTnY&keytype=ref&siteid=sci
Title: Re: 8x8 Draughts/Checkers: solved!
Post by 99of9 on Jul 24th, 2007, 3:53am

on 07/24/07 at 00:10:01, The_Jeh wrote:
In standard checkers, jumps are forced. But in another popular variation (which I prefer), jumps are not obligatory. Have both variations been solved, then?

No, only the obligatory jump game has been solved.


Arimaa Forum » Powered by YaBB 1 Gold - SP 1.3.1!
YaBB © 2000-2003. All Rights Reserved.