logo Welcome, Guest. Please Login or Register.
April 24, 2019, 09:49PM
Home Help Search Login Register
News: Visit a member's site: http://electronicchess.free.fr/index-UK.html (bobosse)

  Chess Computer Community
  General Category
  Discussions about Chess Computers
(Moderators: Endspielgott, Overtom, bobosse)
  Checkers solved by a computer! Let's hope this never happens to chess :)
previous next
Pages: [1] Reply Notify of replies Send the topic Print 
   Author  Topic: Checkers solved by a computer! Let's hope this never happens to chess :)  (Read 1990 times)
chubbyupchuck
Global Moderator
*****

Offline

Posts: 36



View Profile
Re:Checkers solved by a computer! Let's hope this never happens to chess :)
« on: October 9, 2009, 11:02AM »
Reply with quote

Alain,

Pleasure, hope you enjoy it.  I'll add Behind Deep Blue to my list to read.

chubby
Report to moderator Logged
Alain Zanchetta
Administrator
*****

Offline

Posts: 818





View Profile WWW E-Mail
Re:Checkers solved by a computer! Let's hope this never happens to chess :)
« Reply #1 on: October 9, 2009, 07:55AM »
Reply with quote

Hi,


Quote from: chubbyupchuck on October  8, 2009, 01:03AM   

Anyway, in the process of Googling I found that Jonathan Schaeffer, the leader of the Chinook development team, had written a book on his experiences (http://www.amazon.com/One-Jump-Ahead-Computer-Perfection/dp/0387765751).  It peaked my interest and so I picked up a copy.

I can heartily recommend it.  It is a truly fascinating story and to my mind Jonathan's retelling is pitched just right (there is some game theory and some checkers theory but not too much of either to detract from the story).

ok, I ordered mine this morning, I loved "Behind Deep Blue" so I guess this will also be interesting.

thanks for the pointer and best regards,
Alain
Report to moderator Logged
chubbyupchuck
Global Moderator
*****

Offline

Posts: 36



View Profile
Re:Checkers solved by a computer! Let's hope this never happens to chess :)
« Reply #2 on: October 8, 2009, 01:03AM »
Reply with quote

I realize this is a bit off topic, and my apologies for that, but... 

I only came across the fact that checkers is a solved game a couple of weeks ago.  I know, I'm behind the times.  Anyway, in the process of Googling I found that Jonathan Schaeffer, the leader of the Chinook development team, had written a book on his experiences (http://www.amazon.com/One-Jump-Ahead-Computer-Perfection/dp/0387765751).  It peaked my interest and so I picked up a copy.

I can heartily recommend it.  It is a truly fascinating story and to my mind Jonathan's retelling is pitched just right (there is some game theory and some checkers theory but not too much of either to detract from the story).

cheers

chubby
Report to moderator Logged
sderyke2002
Full Member
***

Offline

Posts: 164



I love Boardnation!

View Profile
Re:Checkers solved by a computer! Let's hope this never happens to chess :)
« Reply #3 on: December 23, 2007, 09:38AM »
Reply with quote


Quote from: TurboKing on July 23, 2007, 05:16PM   

Hello Plozikou

Billions of billions of billions possible games can be calculated , it is just that today's computers are not fast enough to do it.
In the future , and probably within this century  , if speed of cpus is billions times faster than today's fastest computers , why not imagine that it will be possible to calculate every position from the beginning to the end of the game ?
Besides , if billions computers make a network ( like an internet network ) to calculate chess ?

Then I guess that this calculation will take only months if not days to solve chess.



Because billions and billions doesn't even start to address the problem.

There are 10 e123 possible games

There are 10 e10 years X 10 e7 seconds per year = 10 e17 seconds in the age of the universe

That means you have to calculate 10 e116  games per second

Assuming there are roughly 10 e1 moves per game...
 
...means the program must calculate 10 e117 moves per second to play out all games to prove the result in each case.

Deep Blue could calculate 10 e8 moves per second so it would take 10 e92 years to calculate all possible games

Now consider there are roughly 10 e82 atoms in the universe

So, if every atom in the universe was a Deep Blue computer it would still take 10 e10 years

That is 10 billions years

Current computers can do 10 e10 moves per second (about 100 times faster than Deep Blue)

This only reduces the time required to 100 million years IF every atom in the universe was capable of such calculations.

For one computer to do this in a reasonable amount of time (roughly 10 e0 = 1 year) it would have to be 10 e90 times faster than modern computers.  That is billions of billions of billions of billions of billions of billions of billions of billions of billions of billions.
« Last Edit: December 23, 2007, 06:53PM by sderyke2002 » Report to moderator Logged
TronTreez
Newbie
*

Offline

Posts: 28

I love Boardnation!

View Profile
Re:Checkers solved by a computer! Let's hope this never happens to chess :)
« Reply #4 on: December 23, 2007, 01:44AM »
Reply with quote


Quote from: TurboKing on July 23, 2007, 04:42PM   

However the result won't be like checkers , that is a perfect play from player A and B will lead to a draw.

A perfect play from the chess computer would be a matter of statistics , that is a move at any position of the game could lead to some % of draws , x % of victories and x % of defeats.
The computer would choose a move according to the % of victories and draws at the end of the game.
Let's imagine 2 different machines that know all the results of every position at any time of the game.
Each computer would move according to the result of each move and they would choose this move according to the % of victories,draws and defeats .
Does it make sense ?



No. Chess must either be a forced win for white, forced draw or forced win for black (unlikely) with best play from both sides. If the game is solved each single position will be known whether or not a side can eventually win from that position. If its a forced draw white will try and force black into one of these position and black try to avoid will them.

I believe that chess engines will become 'unbeatable' in the near future, but they won't necessarily have to 'solve' chess to achieve this.
Report to moderator Logged
marko
Full Member
***

Offline

Posts: 187



How do you make a computer blink?

View Profile
Re:Checkers solved by a computer! Let's hope this never happens to chess :)
« Reply #5 on: December 22, 2007, 11:31AM »
Reply with quote


Quote from: goldorak on July 25, 2007, 05:32AM   

Will Chess be solved completely by computers ?
I think yes, computers will solve Chess, but it won't happen anytime during my lifetime nor most peoples lifetimes.
The only way to resolve chess is by a working quantum computer, so I'm not the least worried. 


The January 2008 issue of Popular Science has an article on page 48 that says that chess will be "solved" (i.e. be unbeatable) in about a hundred years. It gives the number of possible board combinations between 1040 and 1045.

-Marko
Report to moderator Logged
goldorak
Jr. Member
**

Offline

Posts: 52

I love Boardnation!

View Profile
Re:Checkers solved by a computer! Let's hope this never happens to chess :)
« Reply #6 on: July 25, 2007, 05:32AM »
Reply with quote

Will Chess be solved completely by computers ?
I think yes, computers will solve Chess, but it won't happen anytime during my lifetime nor most peoples lifetimes.
The only way to resolve chess is by a working quantum computer, so I'm not the least worried. 
Report to moderator Logged
goldorak
Jr. Member
**

Offline

Posts: 52

I love Boardnation!

View Profile
Re:Checkers solved by a computer! Let's hope this never happens to chess :)
« Reply #7 on: July 25, 2007, 05:27AM »
Reply with quote


Quote from: Meca on July 23, 2007, 07:18AM   

No problem. If in a race of Formula 1 all cars and pilots runs perfect, all arrives at the same time. If all golf players are perfect, the tournament has all players as winners .... and so on. 


Actually no, if all the pilots drive prefectly the winner will be the pilot that was in pole position, the second arrived will be the pilot that was placed in second position on the starting grid and so on.
Report to moderator Logged
TurboKing
Full Member
***

Offline

Posts: 103



I love Boardnation!

View Profile
Re:Checkers solved by a computer! Let's hope this never happens to chess :)
« Reply #8 on: July 23, 2007, 05:16PM »
Reply with quote

Hello Plozikou

Billions of billions of billions possible games can be calculated , it is just that today's computers are not fast enough to do it.
In the future , and probably within this century  , if speed of cpus is billions times faster than today's fastest computers , why not imagine that it will be possible to calculate every position from the beginning to the end of the game ?
Besides , if billions computers make a network ( like an internet network ) to calculate chess ?

Then I guess that this calculation will take only months if not days to solve chess.
Report to moderator Logged
plozikou
Newbie
*

Offline

Posts: 31



Collectionneur de Boris Collector

View Profile WWW E-Mail
Re:Checkers solved by a computer! Let's hope this never happens to chess :)
« Reply #9 on: July 23, 2007, 04:57PM »
Reply with quote

I have a page who talk about that on my web site (the Shannon number): http://www.boris-is-king.com/possibilitsinfinies.htm.

It is in english and french. Just for your information:

The recent estimates give 10123 possible games, knowing that the number of possible legal positions is estimated between 1043 and 1050.

By way of comparison, current physics gives an estimate of the number of atoms in the observable universe ranging between 4×1078 and 6×1079.

I hope that will be interesting for the discussion. Bye

Daniel 
Report to moderator Logged

BORIS IS KING

http://www.boris-is-king.com
TurboKing
Full Member
***

Offline

Posts: 103



I love Boardnation!

View Profile
Re:Checkers solved by a computer! Let's hope this never happens to chess :)
« Reply #10 on: July 23, 2007, 04:42PM »
Reply with quote

Hello

in the article , one scientist says that
Quote:
It's probably impossible. [Chess is] just too complex," Genesereth said. "I don't think it will ever be done."

I don't agree with him.
I guess that it is only a matter of  time to calculate all the combinations of the game.
However the result won't be like checkers , that is a perfect play from player A and B will lead to a draw.

A perfect play from the chess computer would be a matter of statistics , that is a move at any position of the game could lead to some % of draws , x % of victories and x % of defeats.
The computer would choose a move according to the % of victories and draws at the end of the game.
Let's imagine 2 different machines that know all the results of every position at any time of the game.
Each computer would move according to the result of each move and they would choose this move according to the % of victories,draws and defeats .
Does it make sense ?

Regards
Report to moderator Logged
Meca
Full Member
***

Offline

Posts: 156



This is great forum!!

View Profile WWW
Re:Checkers solved by a computer! Let's hope this never happens to chess :)
« Reply #11 on: July 23, 2007, 07:18AM »
Reply with quote

No problem. If in a race of Formula 1 all cars and pilots runs perfect, all arrives at the same time. If all golf players are perfect, the tournament has all players as winners .... and so on. 
Report to moderator Logged
Ismenio
Horsie to pointy guy 6
Administrator
*****

Offline

Posts: 1753





View Profile WWW E-Mail
Checkers solved by a computer! Let's hope this never happens to chess :)
« Reply #12 on: July 23, 2007, 05:38AM »
Reply with quote

http://www.cs.ualberta.ca/~chinook/index.php
They have details and "proof" that the whole game was solved: Checkers is a draw!

From their news page:


April 29, 2007
Checkers is solved. From the starting position, black to play can only draw against a perfect opponent. This is the largest non-trivial game of skill to be solved -- it is more than one million times bigger than Connect Four and Awari (the previously biggest games that have been solved).

To achieve this results, we had to solve 19 of the 3-move openings. We will continue our computations to eventually solve all the 3-move openings.



More here:

http://www.chicagotribune.com/news/nationworld/chi-checkersjul20,1,1923884.story

Ismenio
Report to moderator Logged

Map of chess computer friends: http://www.frappr.com/chesscomputers
Pages: [1] Reply Notify of replies Send the topic Print 
previous next
Jump to:  

Login with username, password and session length

Chess Computer Community
Get your Ad Free Message Board at Boardnation!   © 2013 Boardnation  Web hosting by Nubis