|
Re: on caching
|
Tom Ritchford
|
May 18, 2001 09:40 PDT
|
| | Whether it's <10% or >90%, I think the advice of the "old proverb" still
applies. So for the first pass I would recommend worrying about only the
interface to the cache and implementing a cache that isn't really a cache.
|
That's what I implemented!
BUT I feel that we'll have to turn the cache on before
we really go live to any scale at all. For pass "zero",
where we "prove" that it's correct, we wouldn't want the
cache enabled.
If you don't cache game states, the number of CPU cycles
that it takes to play a game of length n is O(n*n)!
(suppose you get to move 100 and you've cached nothing.
then you need to traverse, again, all the moves from 1 to 99...)
Admittedly, n is bounded but it's still not right.
| | In the specific case of chess, I suppose there are two questions that would
affect the value of a cache:
1. How much disk space will it need, since potentially quite a large number of
positions could be cached;
|
We fix the disk, memory and database sizes according to what we
can afford.
| | 2. How much CPU will it really save. This comes down to how often
positions are
revisited, and directly relates to whether chess is "solvable" (the less often
positions are revisited, the less likely that chess is solvable).
|
Well, no. It's a human thing. The point is that, as always, people
do the same things over and over.
Think about it this way. EVERY game has to visit the single node at the
root of the tree... almost every game has to visit either d4 or e4;
a lot of games will visit e4/e5.
Also, if I'm analyzing some variation of Q gambit declined, say, I'll
be hitting a few positions over and over. Or, if two famous players
are playing live, then those few positions are going to be hit over
and over.
In fact, I'd go so far as to say that MOST positions that are hit once,
are hit twice, in a game... because only the LAST position in the game
is computed only once.
| | So once you're at move 20, what is the probability that you're in a position
that is already stored in the cache? It must be a very small number.
|
NO! It must be a very HIGH number!
I am approaching this from a totally different viewpoint -- I assume
that most of the time, most of the people are actually trying to
play chess as opposed to randomly moving pieces around.
| | I am not a
student of chess. But I wonder if it's ever happened at the grandmaster level,
that someone was analyzing a game and at move 20 noticed that the players were
in exactly the same position as had been reached at move 23 in some
other game?
|
Sure, that happens quite often. Not that there's a transposition, but
that the players have played exactly the same game. There's a famous
story about this, Alekhine (I think?) or someone of that level plays
a duffer and isn't paying too much attention but then finds him unbelievably
strong and finally fights him to a draw -- it turns out that said duffer
had just studied a game that grandmaster had played in a tournament the
previous year and it was the same game.
| | This pessimistic analysis is quite simplistic, I know. I'd be happy
to have the
flaws explained. After all, having a shot at "solving" chess would be very
exciting,
|
Well, we can certainly "solve" chess. I mean, suppose we had an
infinitely better, up-to-the-second version of Modern Chess Openings.
That "solves" chess in some sense, as it's a dynamic representation of
"best play in chess".
If that meta-MCO led entirely to positions that were "obviously"
quiescent, where there was no more "play" left in the game
and the outcome was "obvious", then we'd have practically "solved" chess.
And if we could really prove that all those apparently quiescent positions
were actually quiescent, then we'd have ACTUALLY solved chess!
It'd be an automated sort of theorem proving. There'd be a myriad
of lemmas like "if white is up a minor piece and pawns are equal and
there are fewer than three of them on the board and .... (a bunch of
other conditions here)... then it is a white win". And they'd be
proposed and proved by computer guided by a person.
Eventually, all the lemmas would cover all the terminal positions
we knew, and we'd have really solved chess.
| | but I remain skeptical both of that likelihood
|
Well, it's unclear as to how likely it is.
I personally believe that it could be done.
I think chess will be solved in one way or the
other before the ends of our lives.
I actually think that the game will have lost
interest as an analysis target once we have
"solved" the game and even though it might
be solvable and not just "solvable", people'd
lose interest at that point.
It's just a huge automated theorem prover.
But it doesn't have to traverse any fraction
whatsoever of the whole tree... just a "few"
key positions or classes of position. (A few
as in a million or a billion but I believe less
than a trillion...)
The reason that chess has been intractable is that people
keep thinking about the Vast number of possible games of
chess there are. However, almost all of those games are
stupid games... nearly all of those games start with
"obviously stupid" first moves for example, and nearly
all of the rest have "obviously stupid" second moves.
| | and of the value of
caching middle-game positions.
|
My claims are two-fold:
- people are going to visit a small number of nodes a large number of times.
- also, we need to at least visit all intermediate games to see a specific
game.
(this isn't nearly as bad as it sounds, because you don't have to compute
the views for all the intermediate games... but you still need to visit them,
even if we changed our representation system...)
| | However, none of this means that it couldn't be
profitable to provide a chess service accessible from handheld devices.
|
YES -- this is a key point.
By serving as the canonical way to represent a specific game of chess,
we can serve both the player and the analyst in the BEST way possible.
When you want to point to a specific game of chess, you will
use our naming system.
We will be the address book to the game of chess.
And people will pencil their notes into this address book.
And eventually there will be enough notes and the game will be "solved".
-----
I might also add that quantum computers do their calculations
apparently "instantaneously".
The reason that this doesn't let you compute uncomputable
functions is that, while time is in some sense unbounded
with a quantum computer, space is not.
However, something like chess, with a small, finite problem
size, is a natural for quantum computing.
I am personally very dubious about quantum computing,
and suspect strongly that they'll find some sort of
speed limit due to some phenomenon as-yet-unencountered.
But it might still work at some future point to
do vast sweeps of tree areas in the game.
/t
...electronic a cappella madness <http://volectrix.com>.........
...extreme internet radio <http://extremeNY.com/radio>...
|
|
 |
|
