Author: Eugene Nalimov
Date: 20:29:26 09/18/99
Go up one level in this thread
I am really using one byte per position. And yes, 4Gb is overkill - 2Gb will be
more than enough. It just happened that I could use 4Gb machine, and had no 2Gb
machines...
Main idea of the currently used algorithm is:
FOR side to move = WHITE, BLACK
FOR each position
IF mated
stored score of current position = LOSS IN 0
ELSE
stored score of current position = DRAW
END IF
END FOR
END FOR
REPEAT
changed = FALSE
FOR side to move = WHITE, BLACK
FOR each position
IF no valid moves
best = draw
ELSE
best = -infinity
FOR each valid move
make it
score = REPLACE_RESULT (probe resulting position)
// REPLACE_RESULT means that loss in N will become
// win in N+1, win in N will become loss in N, draw
// will remain draw.
best = MAX (score, best)
unmake move
END FOR
END IF
IF best != stored score of current position
stored score of current position = best
changed = TRUE
END IF
END FOR
END FOR
UNTIL NOT changed
Please note that algorithm is not the best one - it is the simplest one to write
and debug, so I could concentrate on more interesting/important parts of the
program, and I had enough horsepower to use it. As a result, generator was
written and debugged in ~2 months, and all 5-man TBs were generated in ~2 months
more. For "real" 6 man TBs a lot of things had to be changed; it just happened
that I can easily generate KQQKQQ, and there were a lot of requests for it.
Eugene
On September 18, 1999 at 22:12:59, Anthony Bailey wrote:
>On September 18, 1999 at 21:34:38, Eugene Nalimov wrote:
>>You can thank Compaq. Recently it stopped NT development on Alpha, and suddenly
>>we have huge Alpha NT servers that have nothing to do - now they will be used
>>only for testing service packs for already shipped products. So I was able to
>>use 2 such servers with 4 Gb of RAM each. Unfortunately, generator itself
>>doesn't use more than 1 CPU, and I don't want to spend time on that. But even
>>with 1 CPU I was able to generate KQQKQQ and KRRKRR; right now they are being
>>verified, and I think that tomorrow or on Monday I'll be able to download them.
>
>Excuse a question from a newbie... but why is that much (8Gb, you're implying)
>RAM required? It seems to suggest you are using quite a number of bytes to
>encode the current knowledge about each position in the tablebase whilst it is
>being generated. (I saw the number 1,546,346,34 bandied about for the number of
>positions in the thing.)
>
>Now, I expect I'm missing some reason why the following algorithm doesn't
>work... but if you start the process by going through each position in turn,
>counting the legal moves from it, there still aren't be more than 64 even for
>wild positions like kqq. And for each position you only have to know which of a
>few possible evaluations (I presume win/lose/draw suffices) applies so far, and
>how many more times you need to backtrack into the position in question
>until you've effectively covered all the moves forward from it. So that's one
>byte per position.
>
>I can see you need some kind of direction information (like moves to a finishing
>position) once the position is evaluated, but it seems you can generate that
>once per ply when you write the newly evaluated positions out to disk. (It's
>random look-up from the disk that you're trying to avoid by holding working
>information in RAM, right? You can afford to write a few Gb to disk linearly
>once per ply...?) Even if you can't, two bytes of RAM is going to suffice, it
>seems?
>
>I presume I've made some silly false assumption here. I confess to being
>completely new to all this (came in on the Kasparov vs World ship) and any
>citations of electronically available papers that describe the algorithms
>usually used would be great.
>
> - Anthony.
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.