solving our game.....how much would it take

Discussion about all things non-checkers.

solving our game.....how much would it take

Postby Patrick Parker on Tue Jun 06, 2006 4:28 am

"theunites" aka Ryan Pronk called me a ''stupid idiot'' and an '':!:'' continuelly at kurnik today. Then Patrick Parker had some nice follow ups to continue to harass me - This was over some silly debate over "chinook solving checkers" - They were way off with every argument they had when i proved them wrong, so they continued to harass me


i brought this topic which down here where it might be better

the person that posted this is 0652
he believes a computer would have to be the size of pluto to solve
checkers ...i do not agree with this

i would like to know others opinions
User avatar
Patrick Parker
 
Posts: 901
Joined: Tue Nov 15, 2005 11:32 pm
Location: amite, louisiana

Re: solving our game.....how much would it take

Postby steve on Fri Jun 09, 2006 5:50 pm

you might say checkers for all practical purposes has been solve now.i am not a computer person but i believe the chinook people have prove it can be solve and it not worth the time and money to take it to the last possible move.
steve
 
Posts: 108
Joined: Sat Nov 26, 2005 6:14 am
Location: bay village,ohio

Re: solving our game.....how much would it take

Postby Patrick Parker on Sat Jun 10, 2006 9:10 am

however i am sure they will take it to the last move
or someone will

i am just asking how much resources would it take ....
personally i think a few super computers and 4 months later and its over with....not having to create the software from scratch of course
User avatar
Patrick Parker
 
Posts: 901
Joined: Tue Nov 15, 2005 11:32 pm
Location: amite, louisiana

Re: solving our game.....how much would it take

Postby Jason Solan on Sat Jun 10, 2006 10:37 am

i don't think it would be quite that quick patrick.....
I believe Ed Gilbert said it took over a year to complete the 10 piece database using 4 PC's....

A 24 pc database would have exponentially more moves, so my guess is that even using a couple supercomputers it would take at least a year, probably several.
It would also require a tremendous amount of storage space that would need to be shared among all the systems working on it.

However if we keep moving in small increments with the endgame databases, that helps as they can be used a reference point.... i.e. when computing a 12 piece database, as soon as 2 pieces are removed from the board the position is solved because its already in a 10 pc database.

Speaking of which, is anyone working on a 12 pc database right now?
Jason Solan
Site Admin
 
Posts: 294
Joined: Sat Jul 16, 2005 4:50 pm
Location: Pennsylvania

Re: solving our game.....how much would it take

Postby EdTrice on Sat Jul 22, 2006 10:36 am

I think I know the source of both sets of comments. Some time ago, someone in the chess world estimated that a computer the size of our existing universe would be need to "solve" chess, since it was estimated that the number of possible positions in the game of chess was greater than the estimated number of atoms in the universe.

Now the "size of checkers" is roughly the square root of the "size of chess" in terms of the order of magnitude.

The question is, what is the definition of "solving the game?"

Dr. Schaeffer outlined a few definitions in a paper he published in 2004, and again in 2005.

Ultra-weakly solving - A program will just know the "theoretical value" of the starting position, through computer analysis. I think most can agree this is a draw, but a computer proof is deceptively more difficult. You see, there are 500,995,484,682,338,672,639 unique checkers positions. By comparison, there are "only" 8,586,481,972,128 positions in the 5x5 subset of the 10-piece database.

Weakly solving - A computer will always win from a winning position, never drawing from a won position, never losing from a drawn position, and always at least drawing from a drawn position (and winning when an opponent would misplay.)

Again, this is harder than it sounds. In 2004 I proved that some programs could not win a won position with only 7 pieces on the board, 4 against 3, in a win that required a total of 253 perfect moves to complete optimally. This was my paper on the so called "7-piece perfect play database" where I solved distance-to-win information for all 21 billion positions with 7 or fewer pieces. Two well-known programs struggled and could not win against the database which played the losing side, always selecting the most-distant loss in response to every move played by the other side.

So, if state-of-the-art programs could not weakly solve a 7-piece position in 2004, how far were we really from weakly solving the whole game? Even as of today on the Chinook website at:

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

...you can see only 5 openings have been weakly solved.

Strongly solving - This is what most people think of, I think, when they mention the computer that is the size of the universe. For every win, the move leading to the quickest termination of the game is played. For every loss, the one to lose most slowly is played. This would be the so-called 24-piece Perfect Play database. Estimating that the longest possible win was less than 65,000 moves, you could get away with storing 2 bytes for every one of the 500 quintillion checkers positions.

I think we can all agree this would require a computer or tremendous proportions, and leave it at that.
--Ed
User avatar
EdTrice
 
Posts: 97
Joined: Fri Jul 14, 2006 2:39 am
Location: Philadelphia


Return to Broken Boards

Who is online

Users browsing this forum: No registered users and 2 guests

cron
class=