Author |
Topic: 8x8 Draughts/Checkers: solved! (Read 1479 times) |
|
IdahoEv
Forum Guru
Arimaa player #1753
Gender: 
Posts: 405
|
 |
8x8 Draughts/Checkers: solved!
« on: Jul 20th, 2007, 12:38pm » |
 Quote  Modify
|
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?
|
|
 IP Logged |
|
|
|
DorianGaray
Forum Guru
Arimaa player #1210
Gender:
Posts: 55
|
|
Re: 8x8 Draughts/Checkers: solved!
« Reply #1 on: Jul 23rd, 2007, 1:40am » |
Quote Modify
|
on Jul 20th, 2007, 12:38pm, 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.
|
|
IP Logged |
|
|
|
UruramTururam
Forum Guru
Arimaa player #2537
Gender:
Posts: 319
|
|
Re: 8x8 Draughts/Checkers: solved!
« Reply #2 on: Jul 23rd, 2007, 2:21am » |
Quote Modify
|
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.
|
|
IP Logged |
Caffa et bucella per attactionem corporum venit ad stomachum meum.
BGG Arimaa badges - get your own one!
|
|
|
JacquesB
Forum Senior Member
Arimaa player #2380
Gender:
Posts: 26
|
|
Re: 8x8 Draughts/Checkers: solved!
« Reply #3 on: Jul 23rd, 2007, 5:31am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
woh
Forum Guru
Arimaa player #2128
Gender:
Posts: 254
|
|
Re: 8x8 Draughts/Checkers: solved!
« Reply #4 on: Jul 23rd, 2007, 6:20am » |
Quote Modify
|
on Jul 23rd, 2007, 1:40am, 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.
|
|
IP Logged |
|
|
|
IdahoEv
Forum Guru
Arimaa player #1753
Gender:
Posts: 405
|
|
Re: 8x8 Draughts/Checkers: solved!
« Reply #5 on: Jul 23rd, 2007, 5:47pm » |
Quote Modify
|
Yes, chess is definitely not 10^120. Even go is "only" 10^100.
|
|
IP Logged |
|
|
|
IdahoEv
Forum Guru
Arimaa player #1753
Gender:
Posts: 405
|
|
Re: 8x8 Draughts/Checkers: solved!
« Reply #6 on: Jul 23rd, 2007, 5:48pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: 8x8 Draughts/Checkers: solved!
« Reply #7 on: Jul 23rd, 2007, 6:01pm » |
Quote Modify
|
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.
|
| « Last Edit: Jul 23rd, 2007, 6:04pm by Fritzlein » |
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: 8x8 Draughts/Checkers: solved!
« Reply #8 on: Jul 23rd, 2007, 6:17pm » |
Quote Modify
|
on Jul 23rd, 2007, 1:40am, 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.
|
|
IP Logged |
|
|
|
RonWeasley
Forum Guru
Harry's friend (Arimaa player #441)
Gender:
Posts: 882
|
|
Re: 8x8 Draughts/Checkers: solved!
« Reply #9 on: Jul 23rd, 2007, 8:00pm » |
Quote Modify
|
zzzzzz...(*) Ow!
*Sound of Snape hitting the back of my head with a book.
|
|
IP Logged |
|
|
|
The_Jeh
Forum Guru
Arimaa player #634
Gender:
Posts: 460
|
|
Re: 8x8 Draughts/Checkers: solved!
« Reply #10 on: Jul 24th, 2007, 12:10am » |
Quote Modify
|
In standard checkers, jumps are forced. But in another popular variation (which I prefer), jumps are not obligatory. Have both variations been solved, then?
|
|
IP Logged |
|
|
|
99of9
Forum Guru
Gnobby's creator (player #314)
 
Gender:
Posts: 1413
|
|
Re: 8x8 Draughts/Checkers: solved!
« Reply #12 on: Jul 24th, 2007, 3:53am » |
Quote Modify
|
on Jul 24th, 2007, 12:10am, 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.
|
|
IP Logged |
|
|
|
|
Home
Help
Search
Members
Login
Register
Reply
Notify of replies
Send Topic
Print