A technique for compacting butterfly tables

[sje]

A technique for compacting butterfly tables:

A butterfly table can be defined as a 4,096 entry array indexed by a from-square and to-square value pair. These tables can be used for history popularity counts, reply moves, scores, and other values of interest.

However, in regular chess there aren't really 4,096 different from-square and to-square value pairs. In fact, there are only 1,792 of them. So more than half the storage used by a butterfly table is wasted.

To handle this issue, one technique is to provide a butterfly indexing vector. This array consists of 4,096 values each only two bytes long that is addressed by a from-square and to-square value pair. Each entry contains a twelve bit unsigned integer from 0 to 1,791 that is an index into a suitably compacted butterfly table. For a butterfly table containing 32 bit moves, there is a space savings of over 25% and that number increases to about 50% for a butterfly containing 64 bit popularity counters.

Note that the same butterfly indexing vector can be used for every butterfly table in a program. And although the use of such a vector means an added level of indirection, the overall beneficial effects of a better data cache hit rate could easily compensate for that indirection.

Somewhere I have a butterfly index vector; if not, I can make one easily enough. I'll put it on my web site so that others may use it in their programs.

Maybe this should go in the wiki.

[rvida]

Sorry if I got something wrong (or out of conetext), but I don't see the point of optimizing access to some lousy tables in a engine with 6000nps search. With all respect, I think the efficiency bottleneck lies somewhere else....

The new CIL toolkit manages only about 6,000 nodes per second in analysis! The node count will go down as hopefully the quality of the analysis goes up.

If I understand correctly, CIL = Chess in LISP... Please explain why on the earth one would want to do an analysis with a LISP engine at 6000 nodes per second

P.S:
OTOH, I saw an engine written entirely in BASH... That is really an achievement

[Gerd Isenberg]

Sorry if I got something wrong (or out of conetext), but I don't see the point of optimizing access to some lousy tables in a engine with 6000nps search. With all respect, I think the efficiency bottleneck lies somewhere else....

The new CIL toolkit manages only about 6,000 nodes per second in analysis! The node count will go down as hopefully the quality of the analysis goes up.

If I understand correctly, CIL = Chess in LISP... Please explain why on the earth one would want to do an analysis with a LISP engine at 6000 nodes per second

P.S:
OTOH, I saw an engine written entirely in BASH... That is really an achievement

Typical reaction of the young and successful

May be for some it is more satisfying to work on Lisp and AI-abstraction rather than to write another 08/15 mainstream program in C or Delphi. On hashing the butterfly from-to index, I proposed something similar on the Influence Quantity of Pieces page.

[mcostalba]

Typical reaction

Don't worry Richard, I've took mine a week ago when I questioned about putting untested stuff in the wiki, welcome in the club !!!!

P.S: Just because I am a very bad and indisciplined guy: can someone prove that butterfly tables do work somehow ? Do we are trying to _possibly_ optimize (two memory accesses instead of one and Gerd teach me is a bad thing) something that _possibly_ already doesn't work

[Gerd Isenberg]

Typical reaction

Don't worry Richard, I've took mine a week ago when I questioned about putting untested stuff in the wiki, welcome in the club !!!!

P.S: Just because I am a very bad and indisciplined guy: can someone prove that butterfly tables do work somehow ? Do we are trying to _possibly_ optimize (two memory accesses instead of one and Gerd teach me is a bad thing) something that _possibly_ already doesn't work

I don't like the harsh attitude versus Steven's contributions here. I am not an AI or Lisp proponent, but it deserves respect imho. I would like to understand more about it, the Lisp history, McCarthy, MIT, the Lisp machines. Other programming paradigms, etc..

With todays architectures, cache and memory sizes, I agree that an additional indirection don't pays off to save some KByte. If you have a bunch of butterfly tables for whatever purpose, to compute a dense minimal perfect key from coordinates and/or piece, captured piece, i.e. to enumerate all possible moves, it might be interesting.

Cheers,
Gerd

[Gian-Carlo Pascutto]

Typical reaction of the young and successful

I think this is the wrong hobby for that. I would advise to learn to play the guitar, or the local variety of football.

May be for some it is more satisfying to work on Lisp and AI-abstraction rather than to write another 08/15 mainstream program in C or Delphi.

Expressiveness of language + Time available to programmer + Familiarity of programmer with language + Programmer ability + Generated code speed = performance

http://ai-contest.com/rankings.php => LISP #1

PS. What do you mean with 08/15?

[Gerd Isenberg]

Expressiveness of language + Time available to programmer + Familiarity of programmer with language + Programmer ability + Generated code speed = performance
http://ai-contest.com/rankings.php => LISP #1

Wow!

PS. What do you mean with 08/15?

I noticed it is a German phrase, origing from a machine gun in WWII, and a later film in the 50s. It is a common derogatory phrase for something completely ordinary, nothing special, average , mediocre or nothing worth mentioning.

[rbarreira]

Expressiveness of language + Time available to programmer + Familiarity of programmer with language + Programmer ability + Generated code speed = performance

This would be true were it not for bottlenecks... Unfortunately that additive math doesn't always work.

[Gian-Carlo Pascutto]

This would be true were it not for bottlenecks... Unfortunately that additive math doesn't always work.

Multiplication would be closer, but not entirely. My point was that the end result is a combination of the factors.

[Steve Maughan]

Hi Steven,

Brilliant!! It may be a huge speedup for Monarch as I was about to use an array of moves:

moves[piece][from][to]

your system should improve the memory footprint considerably.

Many thanks,

Steve