"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
solving our game.....how much would it take
-
Patrick Parker
- Posts: 959
- Joined: Tue Nov 15, 2005 11:32 pm
- What do you like about checkers?: history of it
the players - Location: amite, louisiana
- Contact:
Re: solving our game.....how much would it take
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.
-
Patrick Parker
- Posts: 959
- Joined: Tue Nov 15, 2005 11:32 pm
- What do you like about checkers?: history of it
the players - Location: amite, louisiana
- Contact:
Re: solving our game.....how much would it take
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
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
-
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
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?
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?
Re: solving our game.....how much would it take
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.
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