0x88 engines

[Tord Romstad]

I was under the impression that Glaurung 1.x was 16x16. I remember Tord described his mailbox approach here before, and I want to say it was the same as he used in Glaurung.

Gerbil is the only other one off the top of my head I can think of that is pure 0x88. It's probably a better idea to look at Fruit though.

that may be right, Glaurung seems to use a lot of 128 byte arrays when referencing the board, but there are also some 256...so i'm a little confused now, will have to take a closer look. (i had always assumed it was pure 0x88...)

It's sort of a hybrid. The relevant part of the position data structure looks like this:

Code: Select all

struct position_t {
  uint8 board_[256];
  uint8 *board;
  /* ... */
};

In the function that initializes position objects, I do this:

Code: Select all

  pos->board = pos->board_ + 64;

In the rest of the code, I never use the pos->board_[] array directly, but only the pos->board pointer. This gives me the normal 0x88 board indices, and the choice between doing pos->board[square] == OUTSIDE or (square & 0x88) when I want to test whether a square is outside the board. In practice, I do pos->board[square] == OUTSIDE almost everywhere, because it's a tiny bit faster, and more importantly, because the & 0x88 trick is so ugly.

Tord

[Tord Romstad]

The first step is to come up with a workable design that you are happy with. Which starts with board representation. Then a functional search and evaluation that plays chess.

I would recommend the opposite order: Write the search and evaluation function first, and do the board representation later. Starting with the board representation is a form of premature optimization: Before you have decided what sorts of questions you want to ask about the position in the search and evaluation, you can't know what board representation suits your needs.

Tord

[wgarvin]

or with 0x88 squares ...

Code: Select all

int colorOfSquare (int x88square) {
   return (0x00AA0055 >> x88square) & 1;
}

I think this code is actually non-portable... but it works on all of the x86 compilers, and probably on all other modern compilers.

I think bit shifts by more than the number of bits in the left operand are implementation-defined. The implementations all just use a single shift instruction, and x86 (and all other popular architectures, AFAIK) only look at the bottom N bits of the count operand to shift or rotate a 2^N bit number. I think the 8086 did not behave like this, but the 80286 and upwards did.

[wgarvin]

Code: Select all

#define TO_BOARD128(x) (x + (x & ~7)) 
#define TO_BOARD64(x) (x - ((x & ~7) >> 1))

You could try this one:

Code: Select all

#define TO_BOARD64(x) ((x + (x & 7)) >> 1)

I picked row and col rather than rank and file on purpose. In chess, ranks are 1-8, and they may or may not be relative - rook on 7th rank can refer to rook on 2nd rank for black. Row within my program is absolute, and 0-7 instead of 1-8, and actually backwards - ROW(A8) is 0 and ROW(A1) is 7. File is absolute in chess but it's ambiguous in the programming sense. Plus chess files are characters a-h, not 0-7.

Hey, I really like that! By calling them Row and Col, you can define them to mean exactly what you want.


Side complaint: If I'm not allowed to edit my post after 15 minutes, why the hell does it still show an Edit button?

[Dann Corbit]

or with 0x88 squares ...

Code: Select all

int colorOfSquare (int x88square) {
   return (0x00AA0055 >> x88square) & 1;
}

I think this code is actually non-portable... but it works on all of the x86 compilers, and probably on all other modern compilers.

I think bit shifts by more than the number of bits in the left operand are implementation-defined. The implementations all just use a single shift instruction, and x86 (and all other popular architectures, AFAIK) only look at the bottom N bits of the count operand to shift or rotate a 2^N bit number. I think the 8086 did not behave like this, but the 80286 and upwards did.

From ISO/IEC 9899:TC3 Committee Draft — Septermber 7, 2007 WG14/N1256
pages 84,85 section: Language §6.5.7

6.5.7 Bitwise shift operators
Syntax
1 shift-expression:
additive-expression
shift-expression << additive-expression
shift-expression >> additive-expression
Constraints
2 Each of the operands shall have integer type.
Semantics
3 The integer promotions are performed on each of the operands. The type of the result is that of the promoted left operand. If the value of the right operand is negative or is greater than or equal to the width of the promoted left operand, the behavior is undefined.
4 The result of E1 << E2 is E1 left-shifted E2 bit positions; vacated bits are filled with zeros. If E1 has an unsigned type, the value of the result is E1 ´ 2E2, reduced modulo one more than the maximum value representable in the result type. If E1 has a signed type and nonnegative value, and E1 ´ 2E2 is representable in the result type, then that is the resulting value; otherwise, the behavior is undefined.
5 The result of E1 >> E2 is E1 right-shifted E2 bit positions. If E1 has an unsigned type or if E1 has a signed type and a nonnegative value, the value of the result is the integral part of the quotient of E1 / 2E2. If E1 has a signed type and a negative value, the resulting value is implementation-defined.

[Dann Corbit]

The expressions:
E1 ´ 2E2
are not rendered properly.
They should be
E1 * 2^E2
where ^ represents the exponentiation operator.

[wgarvin]

How about board variable types? Right now I am using int board[192]. Is that fastest because it is the register size, or is it better to use char board[192] because it is more compact?

Using int variables compiler generate shorter code, because it can combine calculation instruction with load from memory assembler instruction in one command.

Speed difference may be or may be not noticeable.

I think that will make no difference in most scenarios. Both Intel and AMD handle loads of 8- and 16-bit quantities into a 32-bit register very well. I'd be really surprised if you saw any kind of gain from using int instead of char, there.

I would worry more about L1 cache usage. If you use a different board structure for each ply, and int board[192] is scribbling on 12 cache lines instead of 3, that might have some tiny impact on performance. For any larger tables that are accessed during move generation or evaluation, you definitely want to use 1- or 2-byte types if your data will fit into them.

You should test it. It is probably faster to access the bytes since they will take 3 cache blocks. If you use the values as subscripts, however, then there is a bit of overhead in that you need to convert a byte into something that can be added in address computations. My board array is chars because it benchmarks faster.

That conversion is free on x86 -- to avoid penalties for partial register access, small loads are perform with a movzx instruction (for unsigned types) or movsx (for signed types), in effect promoting the operand to an unsigned or signed int for free.

[MattieShoes]

The first step is to come up with a workable design that you are happy with. Which starts with board representation. Then a functional search and evaluation that plays chess.

I would recommend the opposite order: Write the search and evaluation function first, and do the board representation later. Starting with the board representation is a form of premature optimization: Before you have decided what sorts of questions you want to ask about the position in the search and evaluation, you can't know what board representation suits your needs.

Tord

I like the idea, but I think perhaps it only works if you've written engines before. A lot of this stuff is not very intuitive and you don't figure out what questions you should be asking until AFTER you've got everything working. It's *then* that you have those "duh!" moments and say "Why didn't I think of that before?" For instance, most noob engines will happily trap their rook on h1 by playing Kf1 and Kg1, but humans never expect it because it's such an obviously stupid thing to do.

[bob]

The first step is to come up with a workable design that you are happy with. Which starts with board representation. Then a functional search and evaluation that plays chess.

I would recommend the opposite order: Write the search and evaluation function first, and do the board representation later. Starting with the board representation is a form of premature optimization: Before you have decided what sorts of questions you want to ask about the position in the search and evaluation, you can't know what board representation suits your needs.

Tord

I like the idea, but I think perhaps it only works if you've written engines before. A lot of this stuff is not very intuitive and you don't figure out what questions you should be asking until AFTER you've got everything working. It's *then* that you have those "duh!" moments and say "Why didn't I think of that before?" For instance, most noob engines will happily trap their rook on h1 by playing Kf1 and Kg1, but humans never expect it because it's such an obviously stupid thing to do.

That was my thinking. Until you have something that works, and begin to study how to make it faster, it is hard for a first-timer to predict what needs to be done incrementally, what is done at point of use, and then which clever data structures will work best to make those things work well.

[diep]

The first step is to come up with a workable design that you are happy with. Which starts with board representation. Then a functional search and evaluation that plays chess.

I would recommend the opposite order: Write the search and evaluation function first, and do the board representation later. Starting with the board representation is a form of premature optimization: Before you have decided what sorts of questions you want to ask about the position in the search and evaluation, you can't know what board representation suits your needs.

Tord

You're advicing to do some sort of bottom-up form of design of source code rather than top-down?

Oh dear.

Well, what else could we expect from a math guy