Checkers Solved - Chess around year 2060-2070!

[Terry McCracken]

Sorry, but you can't _prove_ until you do search all pathways. That's the very definition of proof. "we think" does not mean "it is".

Funny Jonathan found a better way!

What other way?

He pruned out the BS, concentrated on wins and draws etc. He reduced the problem by a huge number of useless positions, otherwise he would have never demonstrated with the technology at his disposal that checkers is a draw if played perfectly.

We are in our infancy as far as technology is concerned.

He didn't "prune" a thing. He uses a best first search that simply searches and stores the tree as it is built. Once a node hits the endgame databases, it is "closed" and never used again. This slowly reduces the number of "open" nodes until each and every one has reached the endgame databases where you are done.

This is not a game-playing strategy that works anywhere near as well as alpha/beta, unless you can search deeply enough to reach the endgame tables eventually. Which we can't and never will be able to do in chess.

Right....Sure Robert..

Fortunately, _one_ of knows what he is talking about here. Do some reading and you will too. best first has been around forever.

Robert, I do know what I'm talking about...and you fail to realize this.

No more personal remarks!

[Dirt]

I don't follow your math. 10^50 bits requires at least 10^50 atoms, although in your case this appears to average 12.5 atoms per bit if I understand your measure correctly. You are way beyond the number of atoms in planet earth at that number.

The issue would become one of size. No way to run at sub-picosecond clock speeds with a storage device far larger than planet earth. just using 8K miles is daunting, as 8K miles = 8,000 * 5280, which if my math works turns into 40 million feet. Or 40 million nanoseconds to propagate any sort of energy. That is 40 thousand microseconds, or 40 milliseconds. Not very fast. that's one of the limiting issues when we start down the slippery slope of such a large storage device... If it is big enough, it will be too slow. If it is fast enough, it will be too small.

I'm actually assuming eight atoms per bit. Eight 12.5 dalton atoms or 100 daltons per bit. Estimates for the number of atoms in the Earth I've found are very close to 10^50. Incidentally, you were a bit unfair in saying 2^160 is about 10^50, it's actually 1.46x10^48. This brings the required mass down to only a few times that of the moon.

It was my concern over the slowness caused by the physical size of the table that led to my final mention of the life span of the Universe. Its hard for me to estimate how much multiple copies and local caches would help, or indeed how long the Universe will last, so I'm not certain of the computability. My guess is it's possible, but that's only a guess.

Based on sensible math, this simply won't ever be feasible.

Oh my, I never meant to suggest it was feasible, merely technically possible. Even if someone were insane enough to start such a project, after a few million years they'd probably lose interest.

[Mark]

Sorry, but you can't _prove_ until you do search all pathways. That's the very definition of proof. "we think" does not mean "it is".

Funny Jonathan found a better way!

What other way?

He pruned out the BS, concentrated on wins and draws etc. He reduced the problem by a huge number of useless positions, otherwise he would have never demonstrated with the technology at his disposal that checkers is a draw if played perfectly.

We are in our infancy as far as technology is concerned.

He didn't "prune" a thing. He uses a best first search that simply searches and stores the tree as it is built. Once a node hits the endgame databases, it is "closed" and never used again. This slowly reduces the number of "open" nodes until each and every one has reached the endgame databases where you are done.

This is not a game-playing strategy that works anywhere near as well as alpha/beta, unless you can search deeply enough to reach the endgame tables eventually. Which we can't and never will be able to do in chess.

The same technique can work in chess if you have enough memory.
We do not know how much memory is enough and it is possible that 10^30 bits are enough.

It doesn't work in chess for the simple reason it searches x^2 the nodes that alpha-beta searches. That's the reason for depth-first, to avoid storing the tree, and then alpha/beta reduces the search space by sqrt(n).

10^30 bits are more than all the memory ever made added together. If you figure one billion computers with one gigabyte of memory each, that is 1 x 10^18. You still need 1024 times that many machines to get there. And I personally do not believe 10^30 will scratch the surface...

Just curious, why wasn't alpha-beta used?

Mark

[bob]

I don't follow your math. 10^50 bits requires at least 10^50 atoms, although in your case this appears to average 12.5 atoms per bit if I understand your measure correctly. You are way beyond the number of atoms in planet earth at that number.

The issue would become one of size. No way to run at sub-picosecond clock speeds with a storage device far larger than planet earth. just using 8K miles is daunting, as 8K miles = 8,000 * 5280, which if my math works turns into 40 million feet. Or 40 million nanoseconds to propagate any sort of energy. That is 40 thousand microseconds, or 40 milliseconds. Not very fast. that's one of the limiting issues when we start down the slippery slope of such a large storage device... If it is big enough, it will be too slow. If it is fast enough, it will be too small.

I'm actually assuming eight atoms per bit. Eight 12.5 dalton atoms or 100 daltons per bit. Estimates for the number of atoms in the
Earth I've found are very close to 10^50. Incidentally, you were a bit unfair in saying 2^160 is about 10^50, it's actually 1.46x10^48. This brings the required mass down to only a few times that of the moon.

It was my concern over the slowness caused by the physical size of the table that led to my final mention of the life span of the Universe. Its hard for me to estimate how much multiple copies and local caches would help, or indeed how long the Universe will last, so I'm not certain of the computability. My guess is it's possible, but that's only a guess.

Based on sensible math, this simply won't ever be feasible.

Oh my, I never meant to suggest it was feasible, merely technically possible. Even if someone were insane enough to start such a project, after a few million years they'd probably lose interest.

I didn't think you were suggesting it was feasible. That was Terry's world. I just wanted to make sure that thought wasn't left hanging.

the 10^50 came from 2^160 (actually the best to date is 2^168) but it requires more than one bit per position. At least 1.5 assuming all you want to do is prove the opening move is won/lost/drawn. If you want to actually play the position and eventually force a mate (actually win the winnable positions) you need more bits.

[bob]

Sorry, but you can't _prove_ until you do search all pathways. That's the very definition of proof. "we think" does not mean "it is".

Funny Jonathan found a better way!

What other way?

He pruned out the BS, concentrated on wins and draws etc. He reduced the problem by a huge number of useless positions, otherwise he would have never demonstrated with the technology at his disposal that checkers is a draw if played perfectly.

We are in our infancy as far as technology is concerned.

He didn't "prune" a thing. He uses a best first search that simply searches and stores the tree as it is built. Once a node hits the endgame databases, it is "closed" and never used again. This slowly reduces the number of "open" nodes until each and every one has reached the endgame databases where you are done.

This is not a game-playing strategy that works anywhere near as well as alpha/beta, unless you can search deeply enough to reach the endgame tables eventually. Which we can't and never will be able to do in chess.

Right....Sure Robert..

Fortunately, _one_ of knows what he is talking about here. Do some reading and you will too. best first has been around forever.

Robert, I do know what I'm talking about...and you fail to realize this.

No more personal remarks!

then why the lack of knowledge about what "best-first search" is all about and why it is the obvious solution to the checkers database access problem and why it doesn't work for chess? In addition to supporting your argument that chess will be solved by requiring technological advances that have absolutely _zero_ basis in fact? We have no evidence of parallel universes that can be interconnected, we have no way to circumvent the speed of light which limits hardware speeds. Etc. If you actually know what you are talking about, what are you basing your "knowledge" on? It isn't of _this_ universe...

[bob]

Sorry, but you can't _prove_ until you do search all pathways. That's the very definition of proof. "we think" does not mean "it is".

Funny Jonathan found a better way!

What other way?

He pruned out the BS, concentrated on wins and draws etc. He reduced the problem by a huge number of useless positions, otherwise he would have never demonstrated with the technology at his disposal that checkers is a draw if played perfectly.

We are in our infancy as far as technology is concerned.

He didn't "prune" a thing. He uses a best first search that simply searches and stores the tree as it is built. Once a node hits the endgame databases, it is "closed" and never used again. This slowly reduces the number of "open" nodes until each and every one has reached the endgame databases where you are done.

This is not a game-playing strategy that works anywhere near as well as alpha/beta, unless you can search deeply enough to reach the endgame tables eventually. Which we can't and never will be able to do in chess.

The same technique can work in chess if you have enough memory.
We do not know how much memory is enough and it is possible that 10^30 bits are enough.

It doesn't work in chess for the simple reason it searches x^2 the nodes that alpha-beta searches. That's the reason for depth-first, to avoid storing the tree, and then alpha/beta reduces the search space by sqrt(n).

10^30 bits are more than all the memory ever made added together. If you figure one billion computers with one gigabyte of memory each, that is 1 x 10^18. You still need 1024 times that many machines to get there. And I personally do not believe 10^30 will scratch the surface...

Just curious, why wasn't alpha-beta used?

Mark

Alpha/beta is a depth-first approach. You search all moves to approximately the same depth (exactly the same depth except for extensions and reductions). This means that _all_ moves have to be searched to the depth required to reach the endgame database on every position. With best-first, once you reach an endgame table for a given position, it is retired and never searched again. So instead of an ever-increasing search space, the search space shrinks as fewer and fewer moves remain "unknown". Until eventually the last move is retired and the thing is solved. Best-first therefore eliminates passing over the same position over and over and over, which takes a lot of extra time. A lot...

[Terry McCracken]

Sorry, but you can't _prove_ until you do search all pathways. That's the very definition of proof. "we think" does not mean "it is".

Funny Jonathan found a better way!

What other way?

He pruned out the BS, concentrated on wins and draws etc. He reduced the problem by a huge number of useless positions, otherwise he would have never demonstrated with the technology at his disposal that checkers is a draw if played perfectly.

We are in our infancy as far as technology is concerned.

He didn't "prune" a thing. He uses a best first search that simply searches and stores the tree as it is built. Once a node hits the endgame databases, it is "closed" and never used again. This slowly reduces the number of "open" nodes until each and every one has reached the endgame databases where you are done.

This is not a game-playing strategy that works anywhere near as well as alpha/beta, unless you can search deeply enough to reach the endgame tables eventually. Which we can't and never will be able to do in chess.

Right....Sure Robert..

Fortunately, _one_ of knows what he is talking about here. Do some reading and you will too. best first has been around forever.

Robert, I do know what I'm talking about...and you fail to realize this.

No more personal remarks!

then why the lack of knowledge about what "best-first search" is all about and why it is the obvious solution to the checkers database access problem and why it doesn't work for chess? In addition to supporting your argument that chess will be solved by requiring technological advances that have absolutely _zero_ basis in fact? We have no evidence of parallel universes that can be interconnected, we have no way to circumvent the speed of light which limits hardware speeds. Etc. If you actually know what you are talking about, what are you basing your "knowledge" on? It isn't of _this_ universe...

I never said anything about beta-first search. I didn't argue about that.

You say the things I mention have _zero_ basis in fact. Why don't you argue this with some top physicists or QC with Waterloo's best?

Yes information is lost if light exceeds 300,000km per sec. However I could send a message by a QT and it could reach you in a Plank second!

[Terry McCracken]

I don't follow your math. 10^50 bits requires at least 10^50 atoms, although in your case this appears to average 12.5 atoms per bit if I understand your measure correctly. You are way beyond the number of atoms in planet earth at that number.

The issue would become one of size. No way to run at sub-picosecond clock speeds with a storage device far larger than planet earth. just using 8K miles is daunting, as 8K miles = 8,000 * 5280, which if my math works turns into 40 million feet. Or 40 million nanoseconds to propagate any sort of energy. That is 40 thousand microseconds, or 40 milliseconds. Not very fast. that's one of the limiting issues when we start down the slippery slope of such a large storage device... If it is big enough, it will be too slow. If it is fast enough, it will be too small.

I'm actually assuming eight atoms per bit. Eight 12.5 dalton atoms or 100 daltons per bit. Estimates for the number of atoms in the
Earth I've found are very close to 10^50. Incidentally, you were a bit unfair in saying 2^160 is about 10^50, it's actually 1.46x10^48. This brings the required mass down to only a few times that of the moon.

It was my concern over the slowness caused by the physical size of the table that led to my final mention of the life span of the Universe. Its hard for me to estimate how much multiple copies and local caches would help, or indeed how long the Universe will last, so I'm not certain of the computability. My guess is it's possible, but that's only a guess.

Based on sensible math, this simply won't ever be feasible.

Oh my, I never meant to suggest it was feasible, merely technically possible. Even if someone were insane enough to start such a project, after a few million years they'd probably lose interest.

I didn't think you were suggesting it was feasible. That was Terry's world. I just wanted to make sure that thought wasn't left hanging.

I said no more personal remarks...I meant in any form Bob!Keep it up and you're Fair Game!

the 10^50 came from 2^160 (actually the best to date is 2^168) but it requires more than one bit per position. At least 1.5 assuming all you want to do is prove the opening move is won/lost/drawn. If you want to actually play the position and eventually force a mate (actually win the winnable positions) you need more bits.

[bob]

I don't follow your math. 10^50 bits requires at least 10^50 atoms, although in your case this appears to average 12.5 atoms per bit if I understand your measure correctly. You are way beyond the number of atoms in planet earth at that number.

The issue would become one of size. No way to run at sub-picosecond clock speeds with a storage device far larger than planet earth. just using 8K miles is daunting, as 8K miles = 8,000 * 5280, which if my math works turns into 40 million feet. Or 40 million nanoseconds to propagate any sort of energy. That is 40 thousand microseconds, or 40 milliseconds. Not very fast. that's one of the limiting issues when we start down the slippery slope of such a large storage device... If it is big enough, it will be too slow. If it is fast enough, it will be too small.

I'm actually assuming eight atoms per bit. Eight 12.5 dalton atoms or 100 daltons per bit. Estimates for the number of atoms in the
Earth I've found are very close to 10^50. Incidentally, you were a bit unfair in saying 2^160 is about 10^50, it's actually 1.46x10^48. This brings the required mass down to only a few times that of the moon.

It was my concern over the slowness caused by the physical size of the table that led to my final mention of the life span of the Universe. Its hard for me to estimate how much multiple copies and local caches would help, or indeed how long the Universe will last, so I'm not certain of the computability. My guess is it's possible, but that's only a guess.

Based on sensible math, this simply won't ever be feasible.

Oh my, I never meant to suggest it was feasible, merely technically possible. Even if someone were insane enough to start such a project, after a few million years they'd probably lose interest.

I didn't think you were suggesting it was feasible. That was Terry's world. I just wanted to make sure that thought wasn't left hanging.

I said no more personal remarks...I meant in any form Bob!Keep it up and you're Fair Game!

Personally, I could care less what you do or what you say. Why don't you point out the "personal remarks" in my above statement. I stated _exactly_ what you had been claiming and why you were (and still are) wrong.

just grow up and talk about things you have a good understanding of, and avoid the technical issues you have no idea about (such as search techniques, hardware, etc).

Your _ideas_ are simply wrong. I don't care one scintilla about your personal life...

the 10^50 came from 2^160 (actually the best to date is 2^168) but it requires more than one bit per position. At least 1.5 assuming all you want to do is prove the opening move is won/lost/drawn. If you want to actually play the position and eventually force a mate (actually win the winnable positions) you need more bits.

[bob]

Sorry, but you can't _prove_ until you do search all pathways. That's the very definition of proof. "we think" does not mean "it is".

Funny Jonathan found a better way!

What other way?

He pruned out the BS, concentrated on wins and draws etc. He reduced the problem by a huge number of useless positions, otherwise he would have never demonstrated with the technology at his disposal that checkers is a draw if played perfectly.

We are in our infancy as far as technology is concerned.

He didn't "prune" a thing. He uses a best first search that simply searches and stores the tree as it is built. Once a node hits the endgame databases, it is "closed" and never used again. This slowly reduces the number of "open" nodes until each and every one has reached the endgame databases where you are done.

This is not a game-playing strategy that works anywhere near as well as alpha/beta, unless you can search deeply enough to reach the endgame tables eventually. Which we can't and never will be able to do in chess.

Right....Sure Robert..

Fortunately, _one_ of knows what he is talking about here. Do some reading and you will too. best first has been around forever.

Robert, I do know what I'm talking about...and you fail to realize this.

No more personal remarks!

then why the lack of knowledge about what "best-first search" is all about and why it is the obvious solution to the checkers database access problem and why it doesn't work for chess? In addition to supporting your argument that chess will be solved by requiring technological advances that have absolutely _zero_ basis in fact? We have no evidence of parallel universes that can be interconnected, we have no way to circumvent the speed of light which limits hardware speeds. Etc. If you actually know what you are talking about, what are you basing your "knowledge" on? It isn't of _this_ universe...

I never said anything about beta-first search. I didn't argue about that.

You say the things I mention have _zero_ basis in fact. Why don't you argue this with some top physicists or QC with Waterloo's best?

Yes information is lost if light exceeds 300,000km per sec. However I could send a message by a QT and it could reach you in a Plank second!

All I can say is please stop. this goes nowhere. There is no existing technology that can be extrapolated to be capable of searching the enormous search space of the game of chess, to completion, and solve the game in any time-frame that is of interest. Even 5,000 years would be noteworthy. But that won't even scratch the surface with any potential future technology that has a basis in real science that is available today. No point in dreaming about how a magic silver-bullet might be created in the future. Where's the basis in any available technology of today, whether it is in use, or in the lab?

As far as exceeding C goes, that remains the area of science fiction author exploitation to make the fiction seem plausible.

as far as your "best first" comments go, re-read your posts. You implied it was something new, and then that I didn't know what I was talking about when I explained it. Unfortunately for you, I do understand it, it's only 50+ years old.