Chinook proof

[MostFamousDane]

I was going through the Chinook proof - just going through a random pp line:

1. 9-13 22-17 2. 13-22 25-18 3. 11-15 18-11 4. 8-15 21-17 5. 4-8 23-19 6. 5-9 17-13 7. 9-14 29-25 8. 8-11 27-23 9. 15-18 19-15 10. 18-27 15-8 11. 12-16 32-23 12. 3-12

Ok this node is marked with D for white. Now there are two moves 24-20 and 24-19 marked as drawn the rest of the moves are marked with not in tree. The site says that means that "The prover did not have to analyze this position". I don't undestand this we are not in the end game yet its 8 pieces each. It is white 's turn to move why doesn't it need to analyse all the moves. I mean 25-22 might win for white (it wont but lets just say for argument sake) which would mean the parent position is not drawn but a win for white invalidating potetially all the way to the root. I don't undestand how the solver can avoid evaluating these moves - does it make sense to anybody ?

Sune

[Alex_Moiseyev]

I don't undestand this we are not in the end game yet its 8 pieces each. It is white 's turn to move why doesn't it need to analyse all the moves.

Sune, Chinook play in proof is not perfect and not necessary win winning positions - at least it is not a part of proof.

If, from 10 possible moves, the first one is drawn - they disnt look for another 9 to the rest and didn't need it for clearancy of proof.

The main idea of Chinook proof was - drawn status of game for white and black pieces.

In example which you provided thet porved a draw for white. For red proof they used other openings and moves.

Regards,

Alex

[MostFamousDane]

Hi Alex

I undestand that if it is white's turn and white has 10 moves and you find a draw for one move that makes the position at least a draw for white. But that is not the case in the example - I assume that would be marked D or win for white. But its not - it is marked as drawn for white and drawn for black in the parent position is deduced on that drawn conclusion. This makes no sense to me ????

[Alex_Moiseyev]

Sune, I am in intensive email conversation with Dr. Schaeffer in the past several days I am going to pass your question to him. I will keep you inform.

Sincerely,

Alex

[Jay H]

[liam stephens]

Confusing! - ain’t it.

Under this Forum I have seen the following statements:

The game of Checkers is solved.

Go As You Please Checkers is solved.

The game of Checkers is 99.9 recurring per cent solved.

And now I read in other sources that Chinook has only weakly solved the game of Checkers (whatever that might mean - enough to make one go weak at the knees)

Several recent postings here by Sune Thrane cast some doubt on the extent of the validity of the Chinook “Proofs”.


Surely the Chinook Proofs should be independenly verified by qualified experts before their claim to have solved the game can be finally accepted.

[Alex_Moiseyev]

Sune, Liam and other !

I just recieved minutes ago email from Dr. Schaeffer. See full text below. My English is a little bit light to understand this correctly. But in other email Dr. Schaeffer mentioned that Chinook play is not perfect in all cases, and it is only enough to secure a draw, not necessary win winning positions.

Perhaps correct statement would be: "Chinook proved a drawn status of GAYP" I don't like to use the word "solve", because there are many different interpretations of this word.

Here is email from Dr. Schaeffer to answer on Sune question.

=====================================================================

This is an excellent question! Please post my response.

We looked at this position. The information being conveyed by the interface is confusing. I am not sure how to best show it. Perhaps you have an idea.

The position after 12-16 has been proven to be a draw. In this position, the program can search to the end of the game and prove the result.

However, there are other lines of play that have been analyzed by the program. They have completely different move sequences, but ended up transposing into the line given. The 24-20 and 24-19 lines were analyzed as part of that line of play and shown to be a draw.

When we display information, we look a position and all its children up in our database. Lo-and-behold, we found the 24-20 and 24-19 positions and displayed them. It does look confusing since, as pointed out, it looks like we have missed looking for a win.

=================================================================

Regards, Alex

[Palomino]

From [b:2de74d2ed4]The New York Times[/b:2de74d2ed4] article.
[quote:2de74d2ed4]“From my point of view, thank God it’s over,” Dr. Schaeffer said.

Even with the advances in computers over the past two decades, it is still impossible, in practical terms, to compute moves for all 500 billion billion board positions. Instead, the researchers took the usual starting position and then looked only at the positions that would occur during the normal course of play.

“It’s a computational proof,” Dr. Schaeffer said. “It’s certainly not a formal mathematical proof. ......

............”The new research proves that Chinook is invincible in the traditional game of checkers (Go as You Please). But in most tournament play, a match starts with three moves chosen at random. In solving the traditional game (GAYP), the researchers have also solved 21 of the 156 three-move openings, leaving a crack of hope for humans, at least for now.[/quote:2de74d2ed4]
Regards, "Pal"

[Palomino]

This is copied from: CNN.com

Schaeffer's team started with the end of a game with just one checker on the board. Then the team looked at every possible position with two checkers, on up to 10 checkers on the board.

Every combination of 10 checkers offers 39 trillion positions for the endgame, he said. Chinook can calculate them all.

It does not matter how the players make it to 10 checkers left because from that point on, the computer cannot lose, Schaeffer said. For two players who never make a mistake, every game would be a draw, he said.

Schaeffer's proof is what is called a "weakly solved" result. It calculates the result from an initial position -- 10 pieces on the board -- rather than from the beginning of the game.

Could Schaeffer's team produce a "strong solution" by calculating every position from the beginning of a game? Maybe, but there is not enough computer power available, he said. It took more than 18 years to get where they are now.

Regards, "Pal"

[liam stephens]

Hi Pal,

A lot of backsliding there, from the original grandiose claims.

Regards - Liam.

[Palomino]

The best information comes from the Dr. Schaeffer quotes, we can only hope he is being quoted accurately. Here's something I found interesting.

The popular game may be simple to play, but it holds a potential 500 billion billion positions. That's one million times more complicated than any other game solved before, says Jonathan Schaeffer, the computer science professor who began the project in 1989.

"In hindsight, it was ludicrous. Why tackle something a million times bigger?'' said the wiry-haired academic. "Maybe there's a little bit of craziness there.''

To conceptualize that number, Schaeffer says to picture one million checkers positions fitting into a footprint. To reach the number of possible positions would take a step on every part of the surface of the world.

"You appreciate how long it would take you to do that -- it's a big task. Well, we had to do that with computers, essentially. So it's huge.''

But they did trim down the number of positions examined. For example, if a move in a certain position would lead to a win, the computer wouldn't look at other possible moves from that position that may lead to a draw or loss. "

Regards, "Pal"

[Palomino]

Along with the good comes the bad!
I think the worst of the reporting comes when reporters draws upon their own conclusions after reading the scientific report or another reporter's article or what? Where do they get this stuff? I don't think they went so far as to interview Dr. Schaeffer or anyone from his team.

".... scientists report that they have rigorously proved that Chinook, in a slightly improved version, cannot ever lose. An opponent, no matter how skilled, practiced or determined, can at best achieve a draw.

In essence, that reduces checkers to the level of tic-tac-toe...."

From an article by Suhas Sreedhar:
[quote]"It took Schaeffer nearly 16 years to complete his checkers odyssey. He began by inventing Chinook, the world

[Palomino]

Some reporters are just making a joke out of it.

Checkers Solved - Public Yawns
by Drunk Monkey
July 19, 2007 05:17 PM EDT

Scientists today announced that after almost two decades of research and hundreds of computers continually running through billions of theoretical permutations, they have finally "solved" the game of checkers, according to the journal Science. The conclusion is that two opponents playing a perfect game of checkers will invariably result in a draw.

In response to the news, 8-year-old Elijah Franks exclaimed, "Checkers is stupid. I like to play WWE Wrestling on XBox 360!"

Emma Thomas, the 10-year-old from Spokane, Washington who reads at a 6th grade level, took a more thoughtful approach to the discovery: "I play checkers online sometimes and I usually beat the computer. I guess my computer isn't as smart as that other one."

When asked if he thought maybe the resources could have been used for something that might actually BENEFIT humankind, Jonathan Schaffer, the lead scientist in the effort who has dedicating the last 18 years of his life to solving this perplexing issue responded by flipping over a checkerboard, scattering the red and black game pieces all over the board. He then announced that he didn't want to play anymore and that he was going home. And that everyone was a poopy-head.

The team next plans to request a $70 million grant to create a computer program to solve the 1981 video game Frogger. That fifth level can be a real !x?x!.

Regards, "Pal"

[liam stephens]

Now, after all the Hoo, Haa Haa, what have we learned?
That the game if played perfectly ends in a draw?

Well proof of that (if any proof were needed) was provided early in the last century by Gonotsky and Lieber,
and was, no doubt, well known, if not proven, since the days of Anderson and Wyllie.

Forgive me, boys and girls, if I say that this saga brings irresistably to mind an old standard from Gershwin’s Porgy and Bess:

“It ain’t necessarily so.”

[Alex_Moiseyev]

We can say that scientifically the fact of drawn status GAYP was known to human at the end of 19th century. If I am not mistaken, the first 2-move restriction match was played in 1896 between R. Jordan and Ferrie. Last GAYP match was played in 1897 (recovered in 1951) between R. Jordan and Stewart and permanently we started to play 2-move restriction World Title Matches in the beginning of 1900's.

In addition, Chinook prover doesn't play it perfectly at all. For instance, the prover choose first move 9-13 for black in order to make a draw ! Of course, Edinburgh is sound drawn opening in GAYP, no problems with this, but certainly this move and debut are not best. Same thing for "white prove".

Respectfully,

Alex