|
Re: on caching
|
Cliff Harris
|
May 18, 2001 08:49 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.
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;
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). Of course,
existing chess programs have large libraries of openings, but for the middle
game, I don't think anyone has ever attempted to cache positions (not that I'm
an expert on this).
Let's say that theoretically there is a forced win for white. Suppose that for
the first 30 moves of the game, black always has a choice of 20 moves. That
means, if we want to store the forced win in its entirety, we need to store at
least 20**30 responses to black moves. That's an awful lot of data. Maybe of
the 20 legal moves, 16 of them are "stupid", so if black makes one of the
stupid moves, we can leave it up to white to win in the old-fashioned way. That
still leaves 4**30 (roughly 10**20) responses, still a very large number. (If
each response is one byte, we need 1 billion 100GB disk drives.)
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. 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?
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, but I remain skeptical both of that likelihood and of the value of
caching middle-game positions. However, none of this means that it couldn't be
profitable to provide a chess service accessible from handheld devices.
- Cliff
Tom Ritchford wrote:
| | | | I am reminded of the old proverb: "First make it work, then make it
work faster."
Suppose 10% of the positions reached in a game are already cached.
Then by caching
we cannot save more than 10% of the CPU. So is it worth the bother?
Not only that,
but much of the load will be from managing sockets, which is not
helped by caching.
|
if 90% of the games hit are that cached 10%, you can save 90% of the CPU...
/t
...electronic a cappella madness <http://volectrix.com>.........
...extreme internet radio <http://extremeNY.com/radio>...
|
|
|
 |
|
