Looking for C developper

[hgm]

@Evert:
As to move encoding: you can go a long way with 16 bits, if you drop the requirement to always encode from- and to-square. I am used to working with 0x88-type boards, so I tend to think of this as using off-board to-squares, but it is basically equivalent to just having an extra flag in the format (outside the fromSqr and toSqr fields) that indicated the move is special, and has non-standard encoding. In this format the toSqr field can probably contain all information you ever need to be encoded, by using it as an index in a table that provides these additional fields, provided you calculate the real toSqr as a step (taken from the table) plus the fromSqr. Then you would only require 3 codes for every promotion choice with orthodox Pawns (one for each possible step). In general moves that would have to be encoded this way are rare in the tree, so it has no impact whatsoever what you have to do to decode the format when the flag is set. So fromSqr, toSqr + 1-bit flag is usually enough.

Btw, no one plays Shatranj, but there are millions of people that play Makruk. And many of them would be very interested in having a strong engine. So Makruk is a totally different case from Shatranj; building an engine for it would be a worthy cause in itself.

I don't know anything about chess variants (except Chess960). But I think we shouldn't goo for too much generality or we risk to never complete the project. Better stay with 8x8 board using bitboards. As for piece types, I would prefer to limit ourselves to normal chess pieces, for simplicity and efficiency. That way move can fit in 16 bits (which is useful for TT). Also, adding "fairy" pieces means we need to go back to computing magics for those

Well, it is none of my business what you are going to build, of course, but with this attitude you immediately withdraw into the corner of stuff that will not spark any interest with anyone but yourself. The umptieth bitboard-based orthodox Chess engine... While an open-source engine of somewhat more general capabilities (even if it would only be the support of board sizes upto 10x8 or pieces with arbitrary gaits) would be a unique thing.

[Evert]

You seem to have more experience than me in the matter. And you're probably right. I've been a bit naive…

Don't feel too bad about it.
There are a few highly successful open-source projects, and you tend to think of those as the way open source software development goes. Even then there can be bears on the road.
Take Stockfish. Back when it was still Glaurung, Tord was the sole developer, and my impression (from reading forum archives) is that at some point he found that he had less time to devote to Glaurung; perhaps he got a little bored with it as well (I don't know that for a fact). Then Marco forked Glaurung, called it Stockfish and started improving it, and it grew from there. Then not too long ago, Marco announced that he would have less time to spend improving Stockfish. The source repository was made public, and eventually the testing framework emerged. But there are at least two points where development could have stagnated and the project dropped.

Someone may yet pick up DiscoCheck 5 and continue with it.

Parallel search, from day 1. This impacts the overall design of the datastructures. Of course, making it efficient is something that needs to happen incrementally. Optimal parallel search for an engine that has a minimalistic evaluation and no or poorly implemented reductions will (probably) not be an optimal search for an engine with a balanced and well-tuned evaluation and a good single-threaded search.

Totally agreed. That being said, I have no experience in writing an SMP engine myself. But you have.

Yes, but I do have to say that I don't have massive experience writing parallel code. In particular, I've been fortunate enough to not have to suffer the nightmare of debugging race conditions, which means I don't have much experience doing that.

A design that will naturally and easily lend itself to playing chess variants. This can take various forms. If limited to "standard" chess pieces, this could include things like atomic (different capture rules), losers/giveaway (very different evaluation weights), Fischer Random, Bughouse and Crazyhouse. I'm more interested in variants with "fairy pieces", but that forces you to make a few design decisions early on: how many fairy pieces will you support? Are they fixed or arbitrary? Can pieces be asymmetric? Can the king be different from the "standard" king? Can the pawns? What about promotion options? In normal chess, you need 6+6=12 bits to encode from/to squares, and 2 bits to encode promotion choices, giving you 14 bit in total, which fits into a standard 16 bit integer and leaves you 2 bits for other information (castling flag, say). If you have more piece types, this may not fit and you'll need to use a 32 bit integer. But then, you can store loads more stuff as well (the piece type, for instance, so you don't need to look that up on the board). This affects the data structures needed, as well as how you write the evaluation (it needs to be scalable to adding additional pieces). Can the board be different from 8x8? Can the topology be different from a square (say, a cylinder)?

Personally, I would suggest a plain 8x8 board, and just add support, or at least the ability to support, a range of different fairy pieces (say, Archbishop, Chancellor/Marshal, Ferz, Elephant, Silver general, Berolina pawns) and rule extensions (atomic captures, giveaway, piece drops). That allows for Berolina Chess, Seirawan Chess, Atomic chess, Bug/Crazy house (whichever is the two-player version of the game, I get them mixed up), Giveaway chess, Fischer Random Chess, Makruk and Shatranj, which is a decent enough mix. It doesn't need to play all of them equally well, and Makruk and Shatranj are perhaps more for "because we can" sake (I don't think anyone plays Shatranj anymore).

I don't know anything about chess variants (except Chess960). But I think we shouldn't goo for too much generality or we risk to never complete the project. Better stay with 8x8 board using bitboards. As for piece types, I would prefer to limit ourselves to normal chess pieces, for simplicity and efficiency. That way move can fit in 16 bits (which is useful for TT). Also, adding "fairy" pieces means we need to go back to computing magics for those

It's actually not so bad. The trick with extra pieces, for the most part, is to make sure that a) you can store them (have a bitboard for them), and b) the move generator can generate moves for them. If the evaluation only does PST+value for them, that's good enough initially. This is all just a matter of making sure arrays can accomodate them. If I were to pick any one variant with fairy pieces to support initially, I'd go with Seirawan Chess, for which there is at least some interest from players (but no strong engine), the new pieces are not particularly strange (B+N and R+N, when Q=R+B) and it has the infrastructure for piece drops.

Are the four extra bits of a 16 bit integer needed for anything, or could they be used to encode for 16 possible promotion pieces? If the latter is possible, I'd suggest going with that (I've only ever done 32 and 64 bit move structures, where that's not a concern).

As for magics: no need for new ones: you'd encode N+B as knight_attacks(square) | rook_attacks(square, occ). At least if you stay away from things like Nightriders (which I would).

I will send you a more detailled PM with what I have in mind.

Ok.

[Evert]

@Evert:
As to move encoding: you can go a long way with 16 bits, if you drop the requirement to always encode from- and to-square. I am used to working with 0x88-type boards, so I tend to think of this as using off-board to-squares, but it is basically equivalent to just having an extra flag in the format (outside the fromSqr and toSqr fields) that indicated the move is special, and has non-standard encoding. In this format the toSqr field can probably contain all information you ever need to be encoded, by using it as an index in a table that provides these additional fields, provided you calculate the real toSqr as a step (taken from the table) plus the fromSqr. Then you would only require 3 codes for every promotion choice with orthodox Pawns (one for each possible step). In general moves that would have to be encoded this way are rare in the tree, so it has no impact whatsoever what you have to do to decode the format when the flag is set. So fromSqr, toSqr + 1-bit flag is usually enough.

Yes, good point!

Btw, no one plays Shatranj, but there are millions of people that play Makruk. And many of them would be very interested in having a strong engine. So Makruk is a totally different case from Shatranj; building an engine for it would be a worthy cause in itself.

True. I admit I quite like the idea of supporting Makruk, but I've never been able to get very excited about the game itself. A "proper" Makruk engine should probably implement all of the horrible counting rules though.

Well, it is none of my business what you are going to build, of course, but with this attitude you immediately withdraw into the corner of stuff that will not spark any interest with anyone but yourself. The umptieth bitboard-based orthodox Chess engine... While an open-source engine of somewhat more general capabilities (even if it would only be the support of board sizes upto 10x8 or pieces with arbitrary gaits) would be a unique thing.

Sjaak (and Leonidas, to a lesser extent) fulfills those requirements.
The source (of Sjaak) is a horrible mess though - and neither program is very strong.

[hgm]

Well, I was thinking more of an engine with about the strength of DiscoCheck. You are right about Makruk not being the most exciting Chess variant. It is not nearly as bad as Shatranj, however, and doesn't require much special to implement it. (Except, indeed, those counting rules. But these only kick in when there are no Pawns left, and should be considered as special end-game knowledge, on par with the fact that KRKB is a draw rather than +2, etc. Engines try to checkmate their opponent as quickly as they can anyway. So from the point of view of the engine it just means it should be inhibited to convert to end-games where it would not have enough moves to checkmate. This really isn't any different from discounting the eval of KBBKN in normal Chess because the 50-move rule will almost always make it a draw.)

[Evert]

Well, I was thinking more of an engine with about the strength of DiscoCheck. You are right about Makruk not being the most exciting Chess variant. It is not nearly as bad as Shatranj, however, and doesn't require much special to implement it.

For Sjaak I made two design decisions because of Makruk: keeping the promotion zone in a variable (also because of Sittuyin) and having "asymmetric leapers" that move differently for black and white (needed for the elephants). The latter was a later addition, I think I first implemented it using different piece types for black and white (which I also do for pawns).

(Except, indeed, those counting rules. But these only kick in when there are no Pawns left, and should be considered as special end-game knowledge, on par with the fact that KRKB is a draw rather than +2, etc. Engines try to checkmate their opponent as quickly as they can anyway. So from the point of view of the engine it just means it should be inhibited to convert to end-games where it would not have enough moves to checkmate. This really isn't any different from discounting the eval of KBBKN in normal Chess because the 50-move rule will almost always make it a draw.)

I guess a tablebase would also help to determine whether a position can be won in the required number of moves. Which reminds me that I should get back to my tablebase generator as well.

[hgm]

The latter was a later addition, I think I first implemented it using different piece types for black and white (which I also do for pawns).

Indeed, this is also how Fairy-Max stil does it. It is a bit annoying, though, to have to duplicate piece definitions in symmetric pairs. And in variants with many asymmetric pieces you can run out of piece types because of this. So it is still on my wish list to automatically reflect pieces when black uses them. For Fairy-Max a piece is fully determined by an index in the list of moves, specifying where the moves for that piece start. Currently it masks of the color before looking up this first-move index. It should be quite easy to leave the color bit before doing this lookup, so that white and black pieces with the same uncolored encoding can have independent lists of moves. And then normally initialize those the same, unless the piece is asymmetric, in which case you would initialize the black version with the negated board steps.

[zamar]

For example, I could learn Go (the board game) and Go (the programming language) and write a concurrent Go program, just so I can call it GoGo (or someone has already done it?). Now that would be a real challenge.

I wrote a small Go (board game) engine a few years ago. Just for a change really. It was really basic though:
- Standard search (I've forgotten the name of the Monte Carlo algorithm they use in go)
- Very light playouts
- SMP support

The result was an engine that would be around 1300 ELO in chess terms in 9x9 board.
Anyway at that point I realized that I don't have the time to start developing it seriously. But this is something I might find interesting at some point in the future.
Chess engines have been tuned to death. You migth find developing a Go engine much more interesting... Give it a try

[Rein Halbersma]

There are a few highly successful open-source projects, and you tend to think of those as the way open source software development goes. Even then there can be bears on the road.
Take Stockfish. Back when it was still Glaurung, Tord was the sole developer, and my impression (from reading forum archives) is that at some point he found that he had less time to devote to Glaurung; perhaps he got a little bored with it as well (I don't know that for a fact). Then Marco forked Glaurung, called it Stockfish and started improving it, and it grew from there. Then not too long ago, Marco announced that he would have less time to spend improving Stockfish. The source repository was made public, and eventually the testing framework emerged. But there are at least two points where development could have stagnated and the project dropped.

It's not a coincidence. The Glaurung source was very clean and readable to begin with, and Marco improved it with great discipline. I think one of the main reasons why Stockfish attracted a community is Marco's skill as a programmer (he sets the bar very high for contributions, which attracts top programmers). Nobody wants to contribute to a mediocre engine, but anyone likes to bask in the glow of successful engine, even if they have only contributed little pieces.

[hgm]

I think that is the most important point. You would never attract contributors to a Chess Engine unless it is the best (or at east the best open source, and within striking range of the absolute best).

But even for Fairy-Max I sometimes get contributions (although I don't olicit them). Not often, but it happens. Because it apparently can do things that other open-source programs cannot already do better. To be succesful in this respect you really need to offer something unique, or beat anyone else who offers something similar.

[Michel]

I think one of the main reasons why Stockfish attracted a community is Marco's skill as a programmer (he sets the bar very high for contributions, which attracts top programmers).

Don't forget that for leading an open source project you need to be pragmatic and yet have strong opinions at the same time.

These qualities are rarely found in one person (they are almost contradictory) and that is why so may open source projects fail. Either the leader is too dominant, driving other contributors away, or else he/she is too soft and the project loses direction.