Grand Chess

[TonyJH]

H.G., here is a new Grand Chess engine (WB) to try. It seems to be working so far.
http://tonyjh.com/chess/TJchess10x10.zip

[Daniel Shawul]

Nebiyu 1.2 is available at https://sites.google.com/site/dshawul/N ... edirects=0

New variants added :

Code: Select all

            Grand chess
            Gothic chess
            Capablanca chess
            Knightmate chess
            Shatranj chess
            Courier chess

The rest of the variants are also updated.

HG:
I will try to add them one by one , Ultima being the ultimate varaint. The problem is I have an "artificial barrier" with the super-variants which doesn't let me mix things up. For instance the "go & amazons" variants fall under the zonal games... I would have to rethink the overall design before starting to do Ultima stuff.

Next up is Makruk and then Berolina. Cylinder is too fancy with that twisted bounday condition. It must be a mathematicain who invented it I don't know about the ICS variants so those will be at the very end of the todo list. So after the above two it is a re-design for the ultima and other staff. Piece values are probably bad and that has become a _severe_ issue. Fairy & Nebiyu disagree a lot when I played courier atleast until Nebiyu kicks fairy's butt and afirms its authority I will do something about it once I am done with the rest.

[Daniel Shawul]

Thanks Tony. It is good to have many chess variants capable engines.
Cheers

[Evert]

Evert, this is not a good challenge For boards other than 8x8 , bitboards only become useful when you want to do some local analysis such as pattern matching on part of the board.

To each his own.
Although I am curious to know why you think bitboards are no longer useful for larger boards. They're not the most flexible data type (can't beat a plain 2D array for that), but they retain most of what makes them an attractive choice on an 8x8 board.
It's true that you no longer have the benefit of using a data type that fits the machine's native word type, but then again, you don't get that in 32 bit mode either and it's not as if bitboards are suddenly useless there.
It's also true that the "normal" way of doing bitboard move generation (through occupancy lookup) will no longer be feasible for large boards, but that's not the only way to do move generation from bitboards.
Aside from bitboards benefitting from 64-bit hardware in normal chess, I don't think it really matters one way or the other what board representation is used: you're always representing the same data and each representation has its strengths and weaknesses.
I've read a lot of archived discussion with pro and con statements (the most hilarious being "if bitboards are so great, how come none of the strong programs use them?") and what I took away from that is that it's not a very interesting metric by which to estimate program strength. It's certainly not going to be a deciding factor in the strength of Sjaak (or BigSjaak), one way or the other.

Grand chess took me 1hour to implement which I am not happy with. My target is to make a templetized code that will allow me to add 10 variants per day:) Something like the engine for zillions of games.

My goals are nowhere near that high, fortunately.
If Sjaak had all the features that have been on my wish-list for a while (optional promotion zones, caps on the number of pieces of a particular type; both of these are needed for Makruk) and supported board sizes larger than 8x8 (not something I planned, but it is something I had in mind to do some day), this would have taken me about one minute to add in. As it is, it first needs a couple of new things.

I use 10 bits each for from & to squares and the rest for capture/promotion piece and other flags == 32 bits. For checkers I had to drop that all in all and use a struct there.

I read a description of how moves are handled in ChessV and decided to do something similar. Sjaak defines a number of actions for each move, most notably pickups and drops (as well as a few other flags). Each pickup (or drop) needs 1 bit for the colour, 4 bits for the piece type and 6 for the square for 11 bits total. In a normal chess-like game, you need to be able to store 4 of these (castling), so I need 44 bits at least. There's also a store/retrieve action that affects the holdings. Add in special flags to set the en-passant square, clear the 50-move flag, change the side to move etc.

I wanted to only use 32 bits, but this encoding was just so attractive that I ended up using 64 bits afterall. Now, in Jazz, I also use 64 bits to store a move, but for completely different (and ultimately silly) reasons. I'm going to get rid of it there.

[hgm]

How can it be that Nebiyu 1.2 scores the symmetric initial position of Grand chess as -1.45?

[hgm]

I read a description of how moves are handled in ChessV and decided to do something similar. Sjaak defines a number of actions for each move, most notably pickups and drops (as well as a few other flags). Each pickup (or drop) needs 1 bit for the colour, 4 bits for the piece type and 6 for the square for 11 bits total. In a normal chess-like game, you need to be able to store 4 of these (castling), so I need 44 bits at least. There's also a store/retrieve action that affects the holdings. Add in special flags to set the en-passant square, clear the 50-move flag, change the side to move etc.

Spartacus is a lot less flexible. It is really written to only handle 'pure' Chess moves: one from-square, moving to one to-square, capturing what is there. Square numbers are limited to 8-bit, and because I use a 0x88-style capture test, the width of the internal board has to be twice that of the real board. (Actually 2N-1 would be wide enough for that, but it would leave an enormous amount of (cached) unusable memory between the ranks of PST and Zobrist table. By taking 2N I can interleave white and black board-size tables for a perfect memory fill. I swicthed to a 24-wide internal board now, so I can do 12-wide real boards, and that would allow upto 11 ranks (upper-right corner = 251).

All moves that are not 'pure' Chess moves, such as castling, e.p., promotion, but also double pushes (because they need to set e.p. rights)need to be encoded as 'special moves', invoking code that is executed before performing the normal move. The different types of special moves all need completely different code, and you have to figure out which code to execute. This is obviously only competative if the specal moves are rare. (Which for double-pushes is a dubious assumption, although they do get rare later in the game.) To make the test for special moves as cheap as possible, I encode them with off-board to-squares, and put the entire unused part of the internal board (plus a rim around it of squares that need not be enumerable with an 8-bit code, because they never occur in moves). So the move decoding starts by fetching the victim from the to-square (something that would have to be done anyway for normal moves).

The only overhead in the common case is than that I have to test the victim for being a boundary guard, and branch to the code section for special moves if it is. In the latter case all info about the special move can be retrieved from tables indexed by the to-square: the real to-square (where the piece on the from-square should go), the 'capture-square', which should be cleared, Rook from- and to-square for castling, bit mask for the castling rights to test to determine castling legality, left and right neighbor for determining e.p. rights, promotion piece type. The latter is actually used more generally, to distinguish the different types of special move, where castlings have 'promotion piece' -1, and e.p. and double-pushes 0, so that I can quickly test for the move being e.p./double-push, castling or promotion, based on the sign.

All squares are given as board step relative to the from-square. That allows me to always use the same to-square code for a promotion by a step straight ahead, which again simplifies the move generator. (Basically it defers calculating the to-square by adding step to from-square to the point where the move is actually searched, rather than generated, which is always a good thing.)

The code is completely free of direct tests on the square number now. To test if a square is in the promotion zone, or on the initial Pawn rank, I have a board-size tables of flags I can test, like "if(pawnRank[from] & stm)...".

[Daniel Shawul]

It was a problem with recalculating piece square tables when variants are switched. If you invoke variant grand twice it will score it as 0. Now that is fixed and uploaded.

[Evert]

Spartacus is a lot less flexible. It is really written to only handle 'pure' Chess moves: one from-square, moving to one to-square, capturing what is there. Square numbers are limited to 8-bit, and because I use a 0x88-style capture test, the width of the internal board has to be twice that of the real board. (Actually 2N-1 would be wide enough for that, but it would leave an enormous amount of (cached) unusable memory between the ranks of PST and Zobrist table. By taking 2N I can interleave white and black board-size tables for a perfect memory fill. I swicthed to a 24-wide internal board now, so I can do 12-wide real boards, and that would allow upto 11 ranks (upper-right corner = 251).

All moves that are not 'pure' Chess moves, such as castling, e.p., promotion, but also double pushes (because they need to set e.p. rights)need to be encoded as 'special moves', invoking code that is executed before performing the normal move. The different types of special moves all need completely different code, and you have to figure out which code to execute. This is obviously only competative if the specal moves are rare. (Which for double-pushes is a dubious assumption, although they do get rare later in the game.) To make the test for special moves as cheap as possible, I encode them with off-board to-squares, and put the entire unused part of the internal board (plus a rim around it of squares that need not be enumerable with an 8-bit code, because they never occur in moves). So the move decoding starts by fetching the victim from the to-square (something that would have to be done anyway for normal moves).

Part of the appeal for me in the approach I took is that the make/unmake move functions are completely agnostic of any rules of the game and also completely symmetric.
In an earlier draft I had pickups, drops and slides where a piece could slide from one location to another. I abandoned that because it became much too complicated for my liking.

Rook from- and to-square for castling, bit mask for the castling rights to test to determine castling legality,

Castling legality checking always gives me a bit of a headache, not entirely sure why. I do the legality checking for it in the move generator, which is expensive in principle, but positions where castling is possible are relatively rare.
Whenever castling shows up in the move list, I know it's a legal move.

[Daniel Shawul]

Ok Makruk and Berolina are added but i have some doubts.
Stalemate is sometimes a win and sometimes not. I consider it a win only for shatranj. Is that correct ?
For Berolina chess, how is the additional info for enpassant stored in the FEN ? It is possible to generate enpassant move by looking at the previous move but I don't know how to do it if only FEN is given.

[hgm]

I think that is correct. I don't think it is actually known for Courier (a historic variant) what the stalemate rules were. Xiangqi is the other game I know where being stalemated counts as a loss. Of course in variants like suicide, stalemate counts as a win.

About the Berolina FEN. I don't really know, I guess it is upto us to think up something. Up to now WinBoard did not really support berolina; I just made some hacks in it to prevent Pawns from disappearing from the display due to mis-identified e.p. captures, and then it could be played with legality testing off. I think a logical extension to the FEN standard would be to mention both the skipped square and the square the pawn to be captured is now on. Like

[d]rnbqkbnr/ppp1p1pp/8/3pPp2/8/8/PPPPPPP1/RNBQKBNR w KQkq e6f5 0 3

1. hf4 fd5 2. e5 df5 {above diagram} 3. exe6 {e.p.-captures f5}

An alternative would be to mention the Pawn move (from-square + to-square). But that is less upward-compatible with the normal FEN standard. If you mention the e.p. square first, a normal FEN reader could progress up to that point, and the only thing you would have to add is a check to see if there now is another square appended. If it is, it is the e.p.-victim square.