On Jun 26, 7:45 am, help bot wrote:
On Jun 25, 5:49 am, Martin Brown
wrote:

No, I think this in-memory trick is just for speeding
up the search. Somewhere on disk the full tablebases
need to be stored so the program can fetch the move.

That definitely isn't the case. I enabled Shredderbases All34 before I
had any other tablebases at all and they still worked OK.

Okay, but I'm not talking about whether or not the
chess program "works OK"; I was talking about the
ability to win OTB in positions where use of table-
bases are deemed necessary.

Yes. By "works OK" I meant does exactly what you would expect it to do
when the position comes into range of the EGTBs. The reason I enabled
TBs was that I wanted to practice my endgame skills against a
computer. Shredderbases enabled returns the same mate in N answers as
Nalimov whenever I have tested it. I suspect that I have seen the odd
glitch running with Nalimov 5 men and Shredders All44 both enabled but
I can't be sure.

In the most recent computer world championships,
Rybka failed to win a fairly simple, winnable endgame
because it could not "figure out" (or even stumble
into) a winning line over-the-board, at tournament

That doesn't surprise me. Current engines are at their weakest when
making the transition to endgame when there are still a reasonable
number of pieces and moves on the board. Rybka's endgame evaluation is
extremely flat until it sees something inside ts search horizon with
deep extensions. If it fails to chose the extensions wisely in certain
types of position it will require a full depth search before it ever
sees the light.

time controls. In other words, without the table-
bases even the world's strongest chess program is
clueless sometimes.

Not exactly clueless. I expect it held onto a draw where someone who
knew the right heuristics and could apply them or had the right 6man
TB would have won.

I added Nalimovs out to 5men so the other engines could use them too. I
normally only let Shredder have All34 and it has to use Nalimovs for
5men (I begrudge giving it an extra 200MB). When I buy some extra ram
that may change. One minor irritation is that AFAIK you cannot turn
off the Shredderbases without hacking away at a config file.

If you disable the in-memory Shredder-bases then
you have nixed a prime reason for using that program
instead of any of its main competitors, some of which
are stronger in spite of this neat trick.

Shredder is stil one of the more pleasing programs to annotate games
with and spar against. It sees interesting fairly human like strategic
lines. Rybka sometimes finds stronger but strange looking
continuations.

I *think* that the minimum information needed to avoid the
engine having to find the win is Win/Draw/Loss and number
of moves to the Win/Draw/Loss.

Weird. In order to save memory, the author would
prefer to write some tricky code instead of storing
just one perfect move per position?

That is because the former can be represented more compactly and size
is a problem here!

I did wonder if one way Shredder might be doing it is by having a fast
deterministic endgame search engine and storing the rank of the move
to play (hopefully either 1,2 or 3 most of the time).

Sadly, all these
tricks will eventually lead to zero improvement in
ability to actually *play* endgames well, for just as
in the openings, it is so much easier (and more
effective!) to just play by-rote.

Rote is very effective. And firepower is probably best concentrated on
the transition to endgame where the TBs are still out of range. That
is the area where the best humans still have the edge over machines.

Several early efforts had a program keeping control
of the center, when it should have been forcing the
enemy King to the edge of the board to deliver mate.
In the most recent world championships, the top
program put all its pawns on the wrong color... .

It must have seemed like a good idea at the time.

Regards,
Martin Brown

On Jun 25, 5:47 pm, Gian-Carlo Pascutto wrote:
help bot wrote:
Otherwise there will be many cases where the correct
evaluation is plugged in, but the engine cannot win the
game in practice.

I am quite sure that this statement is not backed up (and in fact
refuted) by practise.

How often does Shredder with ShredderBases play into a won endgame it
cannot win? Hardly ever. Why? Because the normal positional evaluation
will still steer it towards more easily won endgames.

But Shredder with Shredderbases enabled quickly returns that same
"Mate in N" (where N can be 50+) answers as Nalimov TBs would when the
position comes in range. I don't think the normal positional
evaluation function is used at all.

Regards,
Martin Brown

Martin Brown wrote:
On Jun 25, 5:47 pm, Gian-Carlo Pascutto wrote:
help bot wrote:
Otherwise there will be many cases where the correct
evaluation is plugged in, but the engine cannot win the
game in practice.
I am quite sure that this statement is not backed up (and in fact
refuted) by practise.

How often does Shredder with ShredderBases play into a won endgame it
cannot win? Hardly ever. Why? Because the normal positional evaluation
will still steer it towards more easily won endgames.

But Shredder with Shredderbases enabled quickly returns that same
"Mate in N" (where N can be 50+) answers as Nalimov TBs would when the
position comes in range. I don't think the normal positional
evaluation function is used at all.

The eval is used once you are *inside* the 5 man endgame. Outside (with
more pieces on the board) the distance-to-conversion is measured.

If you have Nalimovs alongside ShredderBases, then the Nalimovs are used
instead of the positonal evaluation.

--
GCP

Tony M wrote:
Shredderbases don't store the distance to mate as Nalimov databases
do, they only tell you whether a position is won, lost or drawn.

That isn't enough information on its own: any legal position of KQ vs
K (except stalemates and positions where the queen is en prise) is won
for the side with the queen. But you need to choose the right
sequence of these positions to reach the checkmate.


Dave.

--
David Richerby Natural Tree (TM): it's like a tree
www.chiark.greenend.org.uk/~davidr/ but it's completely natural!

Martin Brown wrote:
I had wondered if there was a very fast deterministic find a mate/
stalemate engine used that allowed them to avoid storing anything in
the tablebases within a range of (I'm guessing here) 16 ply from any
of the terminal nodes.

But then you'd need an efficient coding of legal positions that are at
least (say) 16 ply from mate. That sounds unlikely.


Dave.

--
David Richerby Mexi-Chainsaw (TM): it's like a lethal
www.chiark.greenend.org.uk/~davidr/ weapon that comes from Mexico!

help bot wrote:
Weird. In order to save memory, the author would prefer to write
some tricky code instead of storing just one perfect move per
position?

``Weird. In order to save time, the traveller would prefer to sit in
some tricky machine instead of just swimming from London to New
York.''


Dave.

--
David Richerby Generic Toy (TM): it's like a fun
www.chiark.greenend.org.uk/~davidr/ child's toy but it's just like all
the others!

In article .com,
Martin Brown wrote:
I had wondered if there was a very fast deterministic find a mate/
stalemate engine used that allowed them to avoid storing anything in
the tablebases within a range of (I'm guessing here) 16 ply from any
of the terminal nodes.

If you're prepared to do a 16-ply search, then you can do
a lot better anyway, by "planting" sufficient analysis at certain
nodes. See below. That would solve the "how do I actually play
the [shortest] mate in 137 from this position" problem, but not the
"N ply down the tree, I'm going to hit this tablebase position, so
I need to know whether it's won, drawn or lost" problem. Assuming
that you know whether you're playing for a win or a draw, the latter
seems to need 1 bit per node before compression; the former between
1 and 1.75 -- see below --; and the combination around 2. In any case,
the "interesting" question is then how much such a tablebase can be
compressed [without compromising the search speed too much].

The problem with this is that Shredder on its bitbases manages to tell
you distance to mate for all the possible continuations.

OK, that's not so hard. In uncompressed form, that means four
outcomes [as in my previous article], so two bits per node: W/E/L/D,
where E again means an exceptional win. But in this case, instead of
supplying a move different from that found by shallow search, the
secondary database supplies DTM. If you are prepared to do a 16-ply
search, then you must find an E position down each line provided you
"except" every position whose DTM is a multiple of 8; for those
roughly 1/8 of won positions, a secondary 6-bit entry suffices for
DTM out to 64x8 = 512 moves, 1024 ply, which should be enough for the
time being. That's a little more storage needed than for my earlier
suggestion, where the exceptions were about 1/4000; OTOH, you can
now throw away the W/D/L information, as you discover it by finding
or not finding the E positions down a particular line, which saves
a bit per node. As well over 90% of positions are non-E, even quite
simple compression schemes should work well.

To put some numbers on it, a typical 5-piece tablebase [such
as KQRvsKQ] has 117M positions, so before compression a "win/draw-loss"
WTM tablebase is 15 megabytes, and a "DTM" WTM tablebase is about 20Mb;
they could be combined into around 30Mb of file. The compression you
can get on that depends on being able to "localise" runs of similar
results, but over 90% should be easy, getting you below 3Mb on disc. I
don't have the Shredderbases, so someone else will have to tell me how
that compares with reality. If they're below 1Mb, in the worst cases,
I'll be impressed. [Endings such as KNNvKB have many fewer positions in
the first place, of course, so will be smaller; and endings that are
"usually" drawn will compress much better, as will endings that are
usually quick mates; so I'd expect most 5-man endings to compress to
well under 1Mb.]

My other question is can the bitbases method be extended to 6 men
positions or is it too dependent on having enough transposition table
to preload with the successor positions.

Based on the previous examples, you might need 20x64 = 1280Mb
of RAM devoted to this [for each specific material], which is a little
OTT for home PCs today, but doesn't seem out of reach "tomorrow". I
don't see any problem of principle. Getting the whole lot, compressed,
into RAM seems rather further away ....

--
Andy Walker, School of MathSci., Univ. of Nott'm, UK.

Dr A. N. Walker wrote:

In uncompressed form, that means four outcomes [as in my
previous article], so two bits per node: W/E/L/D, where
E again means an exceptional win.

Consider the case where a chess engine sees that no matter
what it does it will end up at a tablebase position that is
a loss. but it's current move decision determines which lost
position it will end up at.

Let's assume that a Nalimov tablebase tells the engine that
move A leads to a position that is a loss in 3 moves, but move
B leads to a position that is a loss in 30 moves. Clearly
move B is superior. Perhaps the opponent can't figure out
the 30-move win. Perhaps the opponent is in time trouble.
Only knowing that both tablebase positions are losses can
lead to inferior play leading up to the tablebase positions.

I can imagine further information in each tablebase position
that, if the engine had it, might improve play. What if the
engine knew that one position was an easy-to-figure-out win
for the opponent, while the other was full of pitfalls and
easy-to-make mistakes for the opponent?

My guess is that such easy/hard information would not be
worth the storage -- that the storage would be better used
by having more positions in the tablebase. Perhaps the
same is true in the thought experiment above; perhaps it
is better to have a larger tablebase that sometimes leads
to inferior play rather than a smaller tablebase that
sometimes leads to superior play. Especially if the size
difference is fifty to one.

--
Guy Macon
http://www.guymacon.com/

On Jun 27, 5:14 pm, (Dr A. N. Walker) wrote:
In article .com,
Martin Brown wrote:

I had wondered if there was a very fast deterministic find a mate/
stalemate engine used that allowed them to avoid storing anything in
the tablebases within a range of (I'm guessing here) 16 ply from any
of the terminal nodes.

If you're prepared to do a 16-ply search, then you can do
a lot better anyway, by "planting" sufficient analysis at certain
nodes. See below. That would solve the "how do I actually play
the [shortest] mate in 137 from this position" problem, but not the
"N ply down the tree, I'm going to hit this tablebase position, so
I need to know whether it's won, drawn or lost" problem. Assuming
that you know whether you're playing for a win or a draw, the latter
seems to need 1 bit per node before compression; the former between
1 and 1.75 -- see below --; and the combination around 2.

This looks like a good analysis.

In any case,
the "interesting" question is then how much such a tablebase can be
compressed [without compromising the search speed too much].

The problem with this is that Shredder on its bitbases manages to tell
you distance to mate for all the possible continuations.

OK, that's not so hard. In uncompressed form, that means four
outcomes [as in my previous article], so two bits per node: W/E/L/D,

Agree again.

To put some numbers on it, a typical 5-piece tablebase [such
as KQRvsKQ] has 117M positions, so before compression a "win/draw-loss"
WTM tablebase is 15 megabytes, and a "DTM" WTM tablebase is about 20Mb;
they could be combined into around 30Mb of file. The compression you
can get on that depends on being able to "localise" runs of similar
results, but over 90% should be easy, getting you below 3Mb on disc. I
don't have the Shredderbases, so someone else will have to tell me how
that compares with reality. If they're below 1Mb, in the worst cases,
I'll be impressed.

I can't tell you the worst case size since Shredderbases are
encapsulated in one large file. However, their overall total size is
about 1/3 (for 34) to 1/2 (for 345) that of the Scorpio bitbases.
Online at:

http://wbec-ridderkerk.nl/html/details/Scorpio.html

This suggests that there is some additional space saving trick in
Shredders bitbase structure. RAR is no slouch in the compresson
stakes.

And the average size at 157MB for 292 5men files (counting NBW & NBB
as distinct) is around 0.5MB per file or 1MB per combo, So I guess the
worst case ones are larger than this probably by a factor of 2-5x.

My other question is can the bitbases method be extended to 6 men
positions or is it too dependent on having enough transposition table
to preload with the successor positions.

Based on the previous examples, you might need 20x64 = 1280Mb
of RAM devoted to this [for each specific material], which is a little
OTT for home PCs today, but doesn't seem out of reach "tomorrow". I
don't see any problem of principle. Getting the whole lot, compressed,
into RAM seems rather further away ....

Maybe 1800MB to be safe, but it is within the bounds of possibility
for a 32bit machine well populated with ram. Although most of the time
in a game it would be a total waste to have the tablebases soaking up
this space though!

Regards,
Martin Brown

Basically what Vas is doing is using a new paradigm that combines
several powerful ideas from CS Theory (efficiency of algorithms),
namely doing a probabilistic depth first search to *check* on the
correctness of standard (but extremely elegantly formulated)
heuristics. Reminds me of what Botvinnik was trying to do, but the
intellectual tools of CS Theory hadn't been developed at that time.

Endgame was a lower priority in the Rybka scheme due to that emphasis
on probability, simply because endgame positions were less likely to
occur :-)

My main interest is endgames, and now that it is becoming clearer that
Rybka needs improvement in that area, more work is being done.
Tablebases in particular are the most interesting aspect of endgames
to me currently, trying to understand the logic behind various arcane
winning moves. So I think it will be great when Rybka takes better
advantage of the tablebases.

One might try to use statistical information garnered from the
tablebases to improve more general endgame heuristics, for example.

For an engine to beat Rybka, it will probably either have to beat Vas
at his own game, using the same paradigm Rybka is using but do it
better, or else find an even better paradigm or model of computation.
That would seem to be extremely difficult though.

Rybka actually plays extremely "normal" (from my human point of view)
chess, but plays normal chess extremely well. I can almost always
understand the moves Rybka thinks are better than my own when I
analyze my games afterwards, while sometimes I can't make any sense of
the moves other engines think are better.