Board representation : 0x88 or 10x12 ??

[H.G.Muller]

In ancient days, where memory had been expensive, I did it, too. Actually there are some castling relevant data fields to support e.g. Chess960. Also notice the two root fields for my two color specific double linked sorted piece lists consisting of the existing board pieces.

Actually, I consider memory exactly as expensive as it used to be when I was writing chess codes 20 years ago. I want my program to run (almost) exclusively from the L1 cache. And this is similar in size (32-64KB) to the address space of the 8-bit CPUs of those days...

The only advantage I take from the huge memory sizes is that now I can afford transposition tables and end-game table bases. But access to those is still outrageously expensive, on my Celeron a random hit in DRAM (most likely causing also a DRAM page miss and a TLB miss) takes 351 CPU clocks (27 FSB clocks) to process (if the flushed cache block was clean!). The latency is somewhat smaller, but the throughput limits hash-table lookups to ~4M per second.

The low-bit = square color I had not realized. Great trick! And yet another argument in favor of this representation.

As Reinhard said, it's not used very often though. In Kiwi (which has a standard 8x8 board for this stuff), I have this code:

Code: Select all

inline int color_of( int sq ) {
    return (sq + (sq >> 3)) & 1;
}


so it's not much more expensive. I use it only in the KBBK and KBNK recognizers so far.

I use the square-color test a lot in my end-game table-base generator. When it is generating retrograde moves, it has to take account of the fact that the move might have been a capture, and leave behind any of the pieces currently in custody on the square it 'came from' (besides leaving it empty). If a Bishop or other color-bound piece is amongst the captured pieces, I want to put it back only on the color it belongs.

[Reinhard Scharnagl]

Allessandro,

so I am not talking on SMIRF details yet but on my problems in fora. People react sometimes very emotional, when I am arguing a direction they do not expect or what seems to "devalue" their work. So, when I notice, that people are defending their position, where I am sure e.g. by my Perft results, that they are obviously wrong, so why should I insist and escalate the discussion into a quarrel? I have nothing to win, only to earn antipathy.

In contrast to writing an engine for about two years, I was improving my chess program data structures for more than ten years, and still I find out new simplifications and viewpoints. Thus I am actually slowly rewriting SMIRF again, slowly, because there is no big interest. I have learned, that discussing on performance is making only limited sense. Best is to make two variants of a program and compare e.g. Perft results. The more I optimize, the more I am sure, that there still are existing uncovered possibilities to improve.

Nevertheless Perft is focussing to the move generator and does not cover a whole engine. That is one reason, why I have integrated caching into a Perft variant, to also test its combined performance and relyability.

SMIRF's move representation actually is 4 Byte long. In future it will only need two. But its impact to performance still is not clear, because I will reduce the included check thread direction information. But I hope for an encouraging outcome.

Reinhard.

[Reinhard Scharnagl]

In ancient days, where memory had been expensive, I did it, too. Actually there are some castling relevant data fields to support e.g. Chess960. Also notice the two root fields for my two color specific double linked sorted piece lists consisting of the existing board pieces.

Actually, I consider memory exactly as expensive as it used to be when I was writing chess codes 20 years ago. I want my program to run (almost) exclusively from the L1 cache. 8-) And this is similar in size (32-64KB) to the address space of the 8-bit CPUs of those days...

The moment I decided to use a cached transposition table, memory has lost that high priority compared to a clearness of routines. Nevertheless that is no reason to waste memory. But my SMIRF engine size actually is only about 60K in total.

Reinhard.

[H.G.Muller]

Well, I still consider it useful to theorize about performance, and discussions sometimes help to get new ideas. If you treat the performance question purely empirically, you lose the feeling for how far you are from what should be theoretically possible, and as a result you might fail to identify major inefficiencies that are remaining. I am also going for a 4-byte move representation: when I will eventually hand-recode my move generator in assembler, I want to push those moves on the system stack, to also make use of %esp as a register, and the fact that it is automatically incremented in the same instruction as I push someshing....

At the moment I am working to on a perft, (in C), as a first step to my new engine. (Making grateful use of the data you posted on CCC, Reinhard!) I just figured out why my perft(6) from the initial position came out 24 too low... That is fixed now, but my check count in the perft(5) is still 12 too low!

Efficiency is my major drive for doing this, I want to use the most efficient algorithm, and make a virtually branch-less implementation of it. (Branch mispredictions are very costly on these newe machines. On the Pentium M the suffered penalty is again 2 cycles more than on Pentium-II, -III, namely 11 against 9. Pentium 4 is a total disaster...)

I am still in doubt w.r.t. the legal vs pseudo-legal issue. The problem is that the engine I have in mind will start any node that it won't know from the hash with a simple QS, trying to capture the piece that last moved, ('recaptures') and try to capture anything over the square it evacuated ('pins'). This would completely duplicate the effort I need to make to ensure that a King move does not blunder into check, or that I don't move a piece that is pinned on the King.

It is true that I can prevent moving such pinned pieces in a much more efficient way, not on a per-move basis, but by scanning the opponent's slider list for line-ups with my King, and tracing the ray to see if there is a single piece of mine in between. (And then temporary disabling this piece during move generation by removing it from its piece list.) That way I prevent all moves of the pinned piece at once, in stead of having to check all my pieces, or all my moves. (Of course I still have to allow for partially pinned pieces, that still retain some moves along the line.) Distant checks I stumble across for free, if there turns out to be nothing on the ray.

But if I know that on the next ply I will start repeating the pin test, which I have to do because I also want to react in QS to moving of pieces that were pinned on Queens or undefended pieces. So the King pin test would still be purely extra work, no matter how efficient it can be done... Leaving the occasional move of a pinned piece on the move stack, and aborting the search of it when the pilot search on the next ply stumbles across a King capture thus seems a very competative strategy. After all, the illegal move might actually never be performed, because an earlier legal move causes a beta cutoff before we get to the illegal one.

If we do attempt to search an illegal move it quickly returns an 'illegal-move' score, and if we want we can take action then: certaily we remove it from the move stack, so that in later IID iterations we don't waste more time on it, but we could also look at the refutation, and if it was due to a pin pre-emptively throw other moves with that same piece from the move stack. In the same way, after we attempt a King move and it turns out to blunder into a check by a slider, we can look if that slider ray covers other squares in the King neighborhood, and pre-emptively interdict those to our King.

I'll let you know when I have results!

[Alessandro Scotti]

Allessandro,

so I am not talking on SMIRF details yet but on my problems in fora. People react sometimes very emotional, when I am arguing a direction they do not expect or what seems to "devalue" their work. So, when I notice, that people are defending their position, where I am sure e.g. by my Perft results, that they are obviously wrong, so why should I insist and escalate the discussion into a quarrel? I have nothing to win, only to earn antipathy.

Hi Reinhard,
I think this is to be expected and well within the "rules of the game" in public discussions, where emotional reactions or defending a point "to death" is not at all uncommon. It's probably much easier to concede a point in a private discussion than on a public forum!
On the other hand, and speaking in general, I do like posts that show some kind of emotion with respect to the topic, and I usually find them more pleasant than a stone cold "just the plain facts" post, which nonetheless I also enjoy.
However, dropping out of a discussion that is becoming too heated or emotional is always a good idea IMO. If anything, it can be continued at a later time after things have cooled down a little.

In contrast to writing an engine for about two years, I was improving my chess program data structures for more than ten years, and still I find out new simplifications and viewpoints. Thus I am actually slowly rewriting SMIRF again, slowly, because there is no big interest. I have learned, that discussing on performance is making only limited sense. Best is to make two variants of a program and compare e.g. Perft results. The more I optimize, the more I am sure, that there still are existing uncovered possibilities to improve.

Well your original thinking and ideas do show in your posts, and that is something I really like a lot. For me, chess programming is just a hobby and something to relax and have fun (except when hunting for bugs... grrr!!!) and as much as I would like to come out with the next greatest chess algorithm I find myself very often pondering other issues such as my family, job problems, bills to pay and so on. This shows quite a bit in Kiwi, when in several occasions Tord had to explain me why my own engine did or did not work!
But in the next (current) engine I have decided to dive deeper into data structures, algorithms and so on, and to try to create something original. Eventually, I got an original board representation and some little new ideas, not much but enough to make me happy! On the other hand, I've started working on it last October and it's barely able to play now, with only an extremely simple search and no evaluation at all. So, not what you would call a fast progress.
What really matters, I am enjoying this a lot. I've come to meet some really really nice people thanks to this hobby, and this is the part I like most. Having a weak engine, with no one interested in it, doesn't bother me at all.

SMIRF's move representation actually is 4 Byte long. In future it will only need two. But its impact to performance still is not clear, because I will reduce the included check thread direction information. But I hope for an encouraging outcome.

I don't store much extra info into a move, just a couple of flags that tell me whether it's an en-passant capture or casting, and the castle side. It's usually a 32-bit integer (or more) inside the program, and only packed into 16 bits when stored into the hash table. Now that you made me notice, the packing code is terrible... will have to profile it soon or later!

[Reinhard Scharnagl]

Well, I still consider it useful to theorize about performance, and discussions sometimes help to get new ideas. If you treat the performance question purely empirically, you lose the feeling for how far you are from what should be theoretically possible, and as a result you might fail to identify major inefficiencies that are remaining.

Maybe I caused a wrong impression on how I try to improve my ideas. During the last ten years I very often have changed my used board representation completely. Really new ideas mostly are incompatible to an existing status quo. I will give you an example:

For a while I tried to have a color independent set of procedures, having no need to encode black or white. What first looks like being really impossible, in fact is not at all, so I finally succeeded. I will give you a short impression of my solution: First I doubled the board in two, each representing the view of a player. The second one has been mirrored (1 <-> 8) to have identic steps for active Pawns. To encode piece types I only have to use Pawn, Knight, Bishop, Rook, Queen, King and (new) Enemy. Additionally I have had two pointers to the boards, being switched when active player (color) had to be changed. Moves have had to be executed on both boards simultaneously.

The result has been a nearly doubled performance and a set of color independent routines.

Such changes are not organic and could not be derived by slowly optimizing a status quo. So I try to always remain able to invent really new ideas. Actually, far from the approach shown above, SMIRF's pieces are simultaneously members of two sorted double linked piece lists of each color. The performance improved again nearly to the double rate.

I still hope to find more such breaking new ideas ...

Reinhard.

[Reinhard Scharnagl]

I don't store much extra info into a move, just a couple of flags that tell me whether it's an en-passant capture or casting, and the castle side. It's usually a 32-bit integer (or more) inside the program, and only packed into 16 bits when stored into the hash table. Now that you made me notice, the packing code is terrible... will have to profile it soon or later!

I forgot to mention, that my method should work also for 10x8 boards. This seems to be a marginal bigger challenge. ;-)
(P.S.: Not to forget promoting Pawn moves into up to 6 different piece types ...)

Reinhard.

[Alessandro Scotti]

Such changes are not organic and could not be derived by slowly optimizing a status quo. So I try to always remain able to invent really new ideas. Actually, far from the approach shown above, SMIRF's pieces are simultaneously members of two sorted double linked piece lists of each color. The performance improved again nearly to the double rate.

Interestingly, this is also what I'm doing now, although I can't say what you link to. In my case, a piece is linked to 1) pieces of the same color and 2) pieces of the same type and color.
I do not care about the exact list order at present, but the original order is always preserved when making/unmaking moves, so I can rely on it being consistent.

I'm also using a "color-independent" approach, using translation tables when needed, such as:

Code: Select all

int ToNextRank[2] = {
    -BoardWidth,
    +BoardWidth
};


[Reinhard Scharnagl]

Such changes are not organic and could not be derived by slowly optimizing a status quo. So I try to always remain able to invent really new ideas. Actually, far from the approach shown above, SMIRF's pieces are simultaneously members of two sorted double linked piece lists of each color. The performance improved again nearly to the double rate.

Interestingly, this is also what I'm doing now, although I can't say what you link to. In my case, a piece is linked to 1) pieces of the same color and 2) pieces of the same type and color.
I do not care about the exact list order at present, but the original order is always preserved when making/unmaking moves, so I can rely on it being consistent.

To keep the order of piece lists is only essential (in my opinion) for:
a) having a sequential move generator,
b) to separate K from bigger pieces, those from Pawns.

I have a double linked list for each color, which makes it simpler to restore a captured piece, or to lift up a promoted pawn. The sorting mainly helps to speed up detecting of check threats or pins, but has also other (unmentioned) benefits.

Reinhard.

[H.G.Muller]

I'm also using a "color-independent" approach, using translation tables when needed, such as:

Code: Select all

int ToNextRank[2] = {
    -BoardWidth,
    +BoardWidth
};


I solved the color-dependence problem so far by considering up-stream and down-stream moving Pawns as different piece types (so in principle I could put pieces on the board that are white but move like black Pawns), and derive notions like ToNextRank from the side_to_move variable. To this end I encoded the latter in an easy relation to the rank step of my board. (This would actually be an argument to stick to 12x16, with rank-step 0x10, despite somewhat more wasted space.) For instance, WHITE = 0x20, BLACK = 0x40. I can use those encodings then in the piece numbers that reside in the board array, e.g. to test for my own pieces by side_to_move & board[x], but also to generate a 'forward' step, by taking 32 - side_to_move. Often exclusive-or can be used to advantage: to generate the to-square of an e.p. capture in a color-independent way, I can use the target y of the previous Pawn double move as y & 0x10.

In my engine-to-be I use doubly linked lists as well, and have separate lists for Pawns, Leapers (usually only Knights, although the King acts as list header it is usually skipped) and Sliders, for each color separately. Very often I want to do things only with Sliders (e.g. look for pins), and during move generation the process for Sliders and Leapers is very different, and can be tailored for each of those, eliminating conditional branches on piece type within inner loops. That holds even more for Pawns, where some moves can capture and others may not capture, complications that I can then completely forget about when looping through the Leapers. The lists are accessed in a color-independent way by putting the list heads in the table underlying the linked lists in such a way that they can be directly indexed by the side_to_move variable:
piece_nr = next[SLIDERS + side_to_move] gives me my first Slider.

I can imagine that for handling pieces like Arch-Bishops and Marshalls, you would have to set up things differently...

[Reinhard Scharnagl]

Another important question is how to represent piece types. As I already have mentioned, in SMIRF those are members of double linked lists having Bit encoded properties. To find out, which encoding would be best, I recommend to test out the performance of recognizing check threats:

In following examples it has been calculated for each square, if an active king would be in check. Such squares are marked with the most significant threatening piece type property (not necessarily always the real piece type itself):

Code: Select all

FEN: 3q2R1/2P5/1k1B4/4np2/1NPK1Pr1/1R6/PP1N1Q2/3q2b1 w - - 0 1

  +-a--b--c--d--e--f--g--h-+ MS Vis.Studio C++ Vers. 13.10
8 |   :::   [q]   :::<R>:::| (Compilation: Mar  2 2006)
7 |:::   <P>   :::   :::   | Testscenario searching for:
6 |   [k]   <B>   :::   :::| undirected check threats
5 |:::   :::   [n][p]:::   |
4 |   <N><P><K>   <P>[r]:::| Test #:      00
3 |:::<R>:::   :::   :::   |
2 |<P><P>   <N>   <Q>   :::| Test Count:  1454953*64
1 |:::   :::[q]:::   [b]   | per Second:  49649173
=>+-a--b--c--d--e--f--g--h-+ Time:        3.751 sec

   bQ bQ bQ -- bQ bQ bQ --
   bK bK bP bQ bP bN bR --
   bK -- bK bQ -- bQ bR --
   bP bK bP -- -- -- bQ --
   -- -- bN -- bP bR bP bQ
   -- bQ -- bN -- bQ bR --
   -- -- bQ bQ bQ bB bR bB
   bQ bQ bQ -- bQ bQ bQ --


FEN: 3R4/b1N1Q3/2B4K/r2P3b/pB1k2p1/1qR1p3/1Nn5/6n1 w - - 0 1

  +-a--b--c--d--e--f--g--h-+ MS Vis.Studio C++ Vers. 13.10
8 |   :::   <R>   :::   :::| (Compilation: Mar  2 2006)
7 |[b]   <N>   <Q>   :::   | Testscenario searching for:
6 |   :::<B>:::   :::   <K>| undirected check threats
5 |[r]   :::<P>:::   :::[b]|
4 |[p]<B>   [k]   :::[p]:::| Test #:      01
3 |:::[q]<R>   [p]   :::   |
2 |   <N>[n]:::   :::   :::| Test Count:  1454953*64
1 |:::   :::   :::   [n]   | per Second:  43020108
=>+-a--b--c--d--e--f--g--h-+ Time:        4.329 sec

   -- bB -- -- bB -- -- --
   bR -- -- -- -- bB -- --
   bR bP -- -- -- -- bB --
   -- bR bK bK bK -- -- --
   bQ bQ bK bB bK -- bP --
   bQ bP bP bK bP bP -- bP
   bP bQ bP bP bN bP -- --
   bN -- -- -- bN -- -- --


FEN: 3k4/8/8/2N4b/6n1/8/5P2/R3K2R w KQ - 0 1

  +-a--b--c--d--e--f--g--h-+ MS Vis.Studio C++ Vers. 13.10
8 |   :::   [k]   :::   :::| (Compilation: Mar  2 2006)
7 |:::   :::   :::   :::   | Testscenario searching for:
6 |   :::   :::   :::   :::| undirected check threats
5 |:::   <N>   :::   :::[b]|
4 |   :::   :::   :::[n]:::| Test #:      02
3 |:::   :::   :::   :::   |
2 |   :::   :::   <P>   :::| Test Count:  1454953*64
1 |<R>   :::   <K>   :::<R>| per Second:  73090285
=>+-*--b--c--d--*--f--g--*-+ Time:        2.548 sec

   -- -- bK -- bK -- -- --
   -- -- bP bK bP bB -- --
   -- -- -- -- -- bN bB bN
   -- -- -- -- bN -- -- --
   -- -- -- -- -- -- bP --
   -- -- -- -- bN -- -- --
   -- -- -- -- -- bN -- bN
   -- -- -- -- -- -- -- --


FEN: K1RBB1bn/1Q2p2q/pP4p1/k5r1/3N1pp1/2P5/1N1n4/r7 w - - 0 1

  +-a--b--c--d--e--f--g--h-+ MS Vis.Studio C++ Vers. 13.10
8 |<K>:::<R><B><B>:::[b][n]| (Compilation: Mar  2 2006)
7 |:::<Q>:::   [p]   :::[q]| Testscenario searching for:
6 |[p]<P>   :::   :::[p]:::| undirected check threats
5 |[k]   :::   :::   [r]   |
4 |   :::   <N>   [p][p]:::| Test #:      03
3 |:::   <P>   :::   :::   |
2 |   <N>   [n]   :::   :::| Test Count:  1454953*64
1 |[r]   :::   :::   :::   | per Second:  43482149
=>+-a--b--c--d--e--f--g--h-+ Time:        4.283 sec

   -- -- -- -- -- -- bQ bQ
   -- -- -- -- bQ bP bQ bP
   bK bK -- bP bB bP bP bQ
   bR bP bR bR bR bP -- bP
   bK bP bB -- bN -- bR bQ
   bR bB -- -- bP bP bP bP
   bR -- -- -- -- -- -- bQ
   -- bR bR bR bR bR bR bQ

There is another test, investigating check threat directions (double check included), this one stops already after one detected check threat.

Reinhard.

[H.G.Muller]

To keep the order of piece lists is only essential (in my opinion) for:
a) having a sequential move generator,
b) to separate K from bigger pieces, those from Pawns.

Sequential move generation is very important for my search strategy. Since I embark on many speculative captures (e.g. of those pieces that were defended by a piece that is now gone), I want to find out if they are losing as quickly as possible, with absolutely minimal effort. (Otherwise it would be better to study first the attack/defence situation, rather than simply trying.) So the first thing that is always tried is (re)capture of the mover. Since the window on speculative captures is aspirated as if the capture is good, any succesful (winning) capture of the moving piece is an immediate beta cutoff. So I don't want to pre-generate a lot of moves, just the first and best capture (i.e. with the lowest piece), try it, and chances are very good that I don't have to look any further.

This recapture itself is similarly speculative, so as a tentative PV this will generate the entire exchange of captures to the same square, with a narrow window around neutrality. Only if capturing in the obvious order does turn out bad, an alternative is tried. But then we already know that the piece was defended, the reply to our initial failed capture tells us what the problem is. So we can refrain from higher-takes-lower captures if the problem was that the piece was defended, and only try alternative captures with a higher piece if the problem was that the lower piece with which we tried before happened to be pinned.

If the piece was sufficiently defended and no lower-takes-higher or equal-takes-equal captures are available, we go to trying Slider captures over the square this piece left, to make sure that it was not pinned. (In fact, if the piece that moved is of low value and relatively harmless, it might pay to try this first. Especially if his King or Queen are lined up with the evacuated square. The line-up tests are also very quick, and could give rise to do the pin-test by looping through our sliders and tracing the rays, in the moderately rare event that there is such a potential pin. We can then make a better informed decision on what to do. A pin might actually be a discovered threat, bringing our Queen eye to eye with an enemy Bishop. Trying to speculatively capture that Bishop then makes more sense than trying to capture the mover, unless that was a Queen or King... It might even make sense to shift our attention completely to the square of the Bishop in such a case, rather than wasting time on capturing, say, a Knight in all possible ways. Trying to capture that Knight with the Queen would of course still be OK. Using common sense here can earn you tons of time, very advanced QS that would otherwise completely explode can be hardly any work at all...)

By putting the pieces in their lists ordered by increasing value, it becomes very easy to generate the capture with the lowest piece by running through these listst (after looking for capturer Pawns on the board).