Chess piece as array, enum, or struct?

Selek

Member
I'm refactoring my world's-slowest-chess-engine, fussing around with beta 2.3, but my question also pertains to my work in 2.2. I define my chessboard as an 8 x 8 2D array. Since I want to refactor this array to meet the beta's new preference for arrays, I figured I might as well rethink how I define my pieces. Right now I define them as an array with two elements, using constants: for example, grid[1][1] = [PAWN, BLACK]. Will the game run faster if I represent the pieces as single numbers, either a macro or an enum? E.g., grid[1][1] = Black.Pawn or grid[1] = BLACK_PAWN? Will it run faster if I construct my own struct?

To complicate things a bit, a few chess pieces have special states that I currently don't handle very elegantly: e.g., can a king castle left or right or both or not at all; has a rook moved yet; can a pawn be promoted; is a pawn eligible to be captured en-passant. I could of course define macros for all these cases: KING_THAT_CAN_CASTLE_LEFT or KNIGHT_THAT_SAYS_NI or such. But that seems klunky. Setting flags can work too, but my AI passes thousands of possible moves back and forth (using Minmax), and I need to keep track of these special states without getting myself confused.

A related, newbish question: if I were to define the piece as part of an Enum, is there any way to test whether a piece is an enumerated type? In the case of my Black.Pawn enum, I don't think GMS supports (if grid[1][1] == Black); or at least, the compiler yells at me, and the manual is silent. I can't find an is_type(Enum) function either.

Finally, a question about posting etiquette. Should I have put these very short code snippets in code tags? I'm sorry for all the questions; I'm rather new to this.

Many thanks in advance.
 

FrostyCat

Redemption Seeker
I strongly recommend that you use an enum for the pieces and a 1D array for the board (see: row/column major order). This allows you to replicate a board by a simple array_copy() call, and cuts out one extra array dereference whenever you pull from the board.

A 1D board represents the cells in either row-major or column-major order. For example, in row major order, in order to find zero-indexed position (xx, yy) on a flattened 8x8 board, you look up position xx+yy*8 (general form) or xx | (yy << 3) (bitwise arithmetic form, applicable only to powers of 2).

Store the identity of a piece in the first 3 bits, and the colour in the fourth, like this:
Code:
enum SIDE {
    WHITE = 0,
    BLACK = 8
}
enum TYPE {
    KING = 6,
    QUEEN = 5,
    ROOK = 4,
    BISHOP = 3,
    KNIGHT = 2,
    PAWN = 1,
}
Then every piece becomes a single int64, which is much easier for a computer to work with than an array or struct. You can form one using bitwise OR (e.g. SIDE.BLACK | TYPE.KING), find the colour by piece & 8, and the type by piece & 7.

Also, store the ability to castle and en-passant at the state level, not at the piece level. These are not properties of a piece, these are properties of what happened during the game.
 

Selek

Member
Thanks for that extremely helpful response, @FrostyCat. I love the idea of a flat representation of the board. I'm in!

Then every piece becomes a single int64, which is much easier for a computer to work with than an array or struct. You can form one using bitwise OR (e.g. SIDE.BLACK | TYPE.KING), find the colour by piece & 8, and the type by piece & 7.
I just tested all this and it worked a treat. Would it slow things down much to assign SIDE.BLACK | TYPE.KING) to a variable, for readability? Likewise, again for readability, could piece & 8 be its own function, or would that add too much overhead?
Also, store the ability to castle and en-passant at the state level, not at the piece level. These are not properties of a piece, these are properties of what happened during the game.
That's sort of what I do now. By state do you mean boardstate? Should it be something I include in the 1D board array?

Thanks again for your help.
 

FrostyCat

Redemption Seeker
I just tested all this and it worked a treat. Would it slow things down much to assign SIDE.BLACK | TYPE.KING) to a variable, for readability? Likewise, again for readability, could piece & 8 be its own function, or would that add too much overhead?
It won't add any more overhead than assigning the true value, because it is an expression that can be evaluated at compile time.

You are free to make piece & 8 its own function for readability, but if you're using YYC (which you should given the CPU-heavy nature of this work), make sure you inline it by including gml_pragma("forceinline");. That cuts out one function call.
That's sort of what I do now. By state do you mean boardstate? Should it be something I include in the 1D board array?
There are 2 parts of the state, what's directly visible on the board (i.e. contents of the 64 squares) and what isn't but is still important to the game (e.g. whose turn it is, which castles/en-passants are available, turns since the last capture). You can either optimize this aggressively and pack the extra information after the first 64 entries of the array, or be less aggressive and store the board as an array in a struct with other properties stored as keys. It's up to you whether to choose performance or "readability", but the first method is visibly faster because a single array_copy() takes care of everything.
 

Selek

Member
Thanks again. You've answered all my questions! I really appreciate your taking the time. And I'm not a fanatic about readability, so I think I'll opt for the performance option and pack board-state stuff after the first 64 entries of the board array.

Thanks again! I'm off to do some coding.
 
Top