Looking for C developper

[Sven]

You know, I think I could make Sjaak play this with relatively little extra work. Flipping the side to move is handled by a field within the move struct, so it would already be easy to make it not flip the side to move. The extra difficulty is doing it every other move instead, but I think I've thought of a way to do it that isn't too hacky.

EDIT: wait, so what is the rule on how turns progress? Does white get two moves on his first turn, or not? I always thought he didn't, but it does raise a problem: when I am fed a position, can I assume that the side to move has the right to make two moves? If I can, do I have to check if the position I receive is the starting position? Or do we need a way to indicate this in the FEN itself? Say, "W" means white can play 2 moves, "w" means white has already played the first move and only gets one (that way the standard chess startup FEN is the same for Marseillaise: white gets a single move at the beginning of the game). Or perhaps a more general "w2" meaning "white to move, 2 legs remaining" with "w1" simply being written as "w".

For the problem with the initial position, I think its FEN is always fixed. So you can compare the FEN to the one of the initial position and decide about single or double move based on that.

Note also that the side to move must be switched after a check in the first leg as well.

Furthermore, I don't think the solution is as easy as you say. I think a correct search in a "Marseillais Chess" engine needs to find the best "move pair". That can mean to generate as much as, say, 40x40 "move pairs" in a position with 40 moves that are legal in orthodox chess, which is of course a huge addition of complexity. Negamax-based alpha-beta search won't work otherwise since the algorithm negates from one ply to the next. So one ply would be a "move pair", or only a single move in the exceptional cases like the initial position or a move giving check. Therefore I think we really need a different move generator and a different move data structure. You can't just start to search one of the 40 "first moves", how would you continue in the next ply where the turn is at the same player? Alpha-beta would fail here. The decision you make at each node is a decision between all available move pairs, so these need to be generated.

Apart from this complexity issue, the big challenge might be the evaluation. I think that a lot of our orthodox chess evaluation principles are simply wrong in Marseillais chess. For instance a rook on an open file can effectively be a loss, even if defended, since the opponent can reach many squares in two moves. The game is very tactical, so I would propose, for a start, to skip *all* evaluation features except material (where good material scores still have to be found step by step), and fully rely on the search until you know more about the inner workings of the game.

Sven

[Evert]

For the problem with the initial position, I think its FEN is always fixed.

Maybe, but I can't base any decisions based on that for Sjaak, which doesn't know or assume anything about the game (apart from it being "chess-like").
Besides, you can always decide to play Marseillaise Fischer Random Chess, and then all bets are off.

By the way, I was thinking of coming back to the initial position after the first move had been played, but now with white having two moves instead of one. It turns out that you can't do that because you'd still need to lose a tempo in order for white to now have two moves left, which you can't do. So that's not really an issue.

Note also that the side to move must be switched after a check in the first leg as well.

True. That's a detail that's "easy" to handle though.

Furthermore, I don't think the solution is as easy as you say. I think a correct search in a "Marseillais Chess" engine needs to find the best "move pair". That can mean to generate as much as, say, 40x40 "move pairs" in a position with 40 moves that are legal in orthodox chess, which is of course a huge addition of complexity.

I said I thought I could make it play; I didn't say it'd play very well.

It so happens that I could almost make Sjaak play it like that, because it encodes moves as pickup/drop operations, and it'd be a matter of folding in the second pickup/drop. I said almost, because (at the moment) Sjaak can only handle a total of 4 pickup/drops in one move, which is not enough for a multi-leg move that involves captures.

Negamax-based alpha-beta search won't work otherwise since the algorithm negates from one ply to the next. So one ply would be a "move pair", or only a single move in the exceptional cases like the initial position or a move giving check.

Good point, I hadn't really considered that. However, what if I don't negate the score (or flip the bounds) after my first move? I'd have to look at a short tree to work out whether that would work or not, but I think doing that would just defer the scoring until after I played both my moves. I just try move pairs recursively rather than iteratively.

Care should probably be taken that you don't hit QS (or eval) with moves still waiting in the queue, and static exchange evaluation becomes pretty meaningless, at least on the first leg of the search. In fact, I'm also not sure how to write a QS, and move ordering probably depends on whether this is the first or second leg (it matters if after QxR you can withdraw the queen with your second move, or if your opponent replies PXQ).

Apart from this complexity issue, the big challenge might be the evaluation. I think that a lot of our orthodox chess evaluation principles are simply wrong in Marseillais chess. For instance a rook on an open file can effectively be a loss, even if defended, since the opponent can reach many squares in two moves. The game is very tactical, so I would propose, for a start, to skip *all* evaluation features except material (where good material scores still have to be found step by step), and fully rely on the search until you know more about the inner workings of the game.

Absolutely. However, if I get round to making Sjaak play this (it may be much more complicated than I think, as you say), by its very nature, it will not play it particularly well.

[hgm]

You can't just start to search one of the 40 "first moves", how would you continue in the next ply where the turn is at the same player? Alpha-beta would fail here.

I don't think that is true. Alpha-beta would work fine. The gain in the second leg is included in the score of move in the first leg, as it comes in fact from an evaluation at the end of the branch. So if that score gets above beta, you can cut. All moves in the first leg get the value of the best follow-up move in the second leg incorporated in their score, so you can just select the best first leg.

In the second leg you don't have anything unusual at all. Of course you should not allow stand-pat after a first leg. This should do it:

Code: Select all

Search(stm, leg2, capt, alpha, beta, depth)
{
  bestScore = -INF;
  if&#40;depth <= 0&#41; &#123; // QS
    if&#40;leg2&#41; bestScore = -Search&#40;!stm, -beta, -alpha, 0&#41;;
    else bestScore = Eval&#40;); // only stand pat in leg 1, otherwise null-move
  &#125;
  for&#40;ALL_SINGLE_MOVES&#41; &#123;
    MakeMove&#40;);
    if&#40;leg2&#41; &#123;
      score = -Search&#40;!stm, 0, -beta, -alpha, depth-1&#41;;
    &#125; else &#123;
      score = Search&#40;stm, 1, alpha, beta, depth&#41;;
    &#125;
    UnMake&#40;);
  &#125;
&#125;

QS will be a problem, though (but that is independent of whether you treat moves in pairs or not). There is a huge potential for search explosion in a capture search, if a capture is defined as a move pair for which at least one of the moves is a capture. But such moves are crucial, as hit-and-run capture will be common. Pairs of two non-captures should obviously be forbidden, but that would IMO not be enough to limit the tree to decent size. The problem is that in two moves most pieces are so powerful that you basically won't run out of captures before the board is completely empty.

Apart from this complexity issue, the big challenge might be the evaluation. I think that a lot of our orthodox chess evaluation principles are simply wrong in Marseillais chess. For instance a rook on an open file can effectively be a loss, even if defended, since the opponent can reach many squares in two moves. The game is very tactical, so I would propose, for a start, to skip *all* evaluation features except material (where good material scores still have to be found step by step), and fully rely on the search until you know more about the inner workings of the game.

Well, as Fairy-Max did not have such evaluation terms in the first place, that would not be a big problem.

[hgm]

I guess I was wrong about QS: Positions at the beginning of the first leg should never be considered quiet. It is the positions after the first leg where you should be allowed to stand pat.

[Sven]

You can't just start to search one of the 40 "first moves", how would you continue in the next ply where the turn is at the same player? Alpha-beta would fail here.

I don't think that is true. Alpha-beta would work fine. The gain in the second leg is included in the score of move in the first leg, as it comes in fact from an evaluation at the end of the branch. So if that score gets above beta, you can cut. All moves in the first leg get the value of the best follow-up move in the second leg incorporated in their score, so you can just select the best first leg.

In the second leg you don't have anything unusual at all. Of course you should not allow stand-pat after a first leg. This should do it:

Code: Select all

Search(stm, leg2, capt, alpha, beta, depth)
{
  bestScore = -INF;
  if&#40;depth <= 0&#41; &#123; // QS
    if&#40;leg2&#41; bestScore = -Search&#40;!stm, -beta, -alpha, 0&#41;;
    else bestScore = Eval&#40;); // only stand pat in leg 1, otherwise null-move
  &#125;
  for&#40;ALL_SINGLE_MOVES&#41; &#123;
    MakeMove&#40;);
    if&#40;leg2&#41; &#123;
      score = -Search&#40;!stm, 0, -beta, -alpha, depth-1&#41;;
    &#125; else &#123;
      score = Search&#40;stm, 1, alpha, beta, depth&#41;;
    &#125;
    UnMake&#40;);
  &#125;
&#125;

Whenever you get a cutoff after the second leg, you also don't continue with other first legs since you have found a move (a pair of legs) that refutes the last move of the opponent. Furthermore, after having played a first leg that does not put the opponent into check you always need to generate all second legs, and you can't get a cutoff after the first leg already. The structure of the search function that you propose might reflect that somehow but I don't see why it is necessary to write it down in a "cryptic" way. Why not writing down the algorithm in a straightforward manner, i.e. why not using exactly the same search algorithm as in orthodox chess? The main differences, in my opinion, to orthodox chess are the move data structure (a move has one or two legs), the move list data structure (mainly due to the huge size of the move list), the move generator (which might in some cases require an internal make/unmake to see all possible second legs), and the detection of check, mate, stalemate and other draw situations.

So I don't see any advantage of your approach of two nested loops per ply (with an additional recursive function call inbetween) over only one flat loop per ply with a long list of pairs of legs, which is what I would prefer. When implemented correctly, both should get the same result but I would consider the "nested" approach a lot clumsier and also harder to read and to understand. Maybe the "nested" approach is also a bit slower due to the almost doubled amount of recursion levels. The nested loops would not go away fully in my approach, they would perhaps be moved into the move generator, although I can imagine that there are some (bitboard?) tricks to partially avoid internal loops and make/unmake to determine all second legs during move generation.

QS will be a problem, though (but that is independent of whether you treat moves in pairs or not). There is a huge potential for search explosion in a capture search, if a capture is defined as a move pair for which at least one of the moves is a capture. But such moves are crucial, as hit-and-run capture will be common. Pairs of two non-captures should obviously be forbidden, but that would IMO not be enough to limit the tree to decent size. The problem is that in two moves most pieces are so powerful that you basically won't run out of captures before the board is completely empty.

Fully agreed. I have no idea yet how to deal with the search explosion issue in QS.

[Greg Strong]

One advantage I see for H.G.'s approach is that it is more extensible. Consider Progressive Chess in which white gets one move, than black gets two, then white gets three, then black gets four, etc ... H.G.'s approach could be extended to accommodate whereas yours could not.

Regarding QS, I suggest only captures on the first leg, and on the second leg, only captures and the move of the piece that captured on the first leg back to its original square (rifle capture.) This overlooks lots of possibilities to be sure, but it would prevent explosion. The chess concept of QS doesn't translate all that well to Marseillais because there are few if any truly quiet positions. I think it's more important to contain QS explosion so you can see deeper in the main search. Any Marseillais engine probably isn't going to be exceptionally strong, (at least without careful study and invention of new techniques), but fortunately humans have a hard time with it too...

[hgm]

So I don't see any advantage of your approach of two nested loops per ply (with an additional recursive function call inbetween) over only one flat loop per ply with a long list of pairs of legs, which is what I would prefer.

The advantage would be that it makes it trivial to modify an existing engine to play it. And I think it is much more straightforward. The game, after all, was defined as orthodox Chess where you play two orthodox turns in a row. You already admit that it probably would be required to do a MakeMove of every first leg in the move generator, so there seems to be very little advantage in the extra recursion. In fact it probably does a lot fewer MakeMoves, as in the conventional design, in an all-node, you would go all 40x40 moves doing two MakeMoves and two UnMakes for each of them. The extra recursion combines all first legs into a single MakeMove/UnMake. (Of course you could also do that non-recursively. But it is well known that you could do the entire search non-recursively.)

It seems all I have to do to make a Fairy-Max derivative that plays this is to add the extra leg argument to the search, and split the recursive call into two based on its value. It would admittedly be a bit clumsy at the root, where it basically would think twice in a row, first iterating for the first leg, and then when it plays it, iterating for the second leg. Perhaps I should change that to limit the depth of the second search to that of the first minus one orthodox ply, to prevent that after an immediate hash hit on the second leg at that depth, it tries to improve.

About QS: I now think that positions where the first leg has to be played are intrinsically non-quiet. Once out-of-depth, the choice should be between stand-pat or a capture in the second leg, assuming that you can use a non-capture second-leg to pre-emptively defend against the worst of the opponents upcoming double turn. For the first leg you should probably try anything, captures as well as non-captures. In the unlikely case that you are already above beta, you can stand pat there too. (As this is basically the same as null-move + second-leg stand pat.) But I don't expect that to happen often; in general you will need the first leg to repair the damage done by the previous opponent double-move.

[Sven]

So I don't see any advantage of your approach of two nested loops per ply (with an additional recursive function call inbetween) over only one flat loop per ply with a long list of pairs of legs, which is what I would prefer.

The advantage would be that it makes it trivial to modify an existing engine to play it.

I don't deny that, it all depends on whether this is actually an important goal. It may be the case for programmers who are generally interested in different chess variants. But if my goal were to write a strong Marseillais engine I would not care about the effort to modify an existing angine, my main focus would be to get it right for this specific variant. Interests may vary here of course.

And I think it is much more straightforward. The game, after all, was defined as orthodox Chess where you play two orthodox turns in a row. You already admit that it probably would be required to do a MakeMove of every first leg in the move generator, so there seems to be very little advantage in the extra recursion. In fact it probably does a lot fewer MakeMoves, as in the conventional design, in an all-node, you would go all 40x40 moves doing two MakeMoves and two UnMakes for each of them. The extra recursion combines all first legs into a single MakeMove/UnMake. (Of course you could also do that non-recursively. But it is well known that you could do the entire search non-recursively.)

True, but then you are a lot less flexible in move ordering. With my approach I would be able to sort those moves close to the top that win a lot of material with their second leg, but without being forced to try all other second legs of the corresponding first legs at around the same point. So I think that your approach will search a much bigger tree, while my additional make/unmake operations are almost negligible. And as you say, they do appear at ALL nodes and only there, while also in Marseillais Chess it should be possible to find a decent move ordering strategy that helps to get a high percentage of cutoffs after trying the first move in the move list, and these cases do not show significantly more make/unmake operations in my approach compared to yours.

It seems all I have to do to make a Fairy-Max derivative that plays this is to add the extra leg argument to the search, and split the recursive call into two based on its value. It would admittedly be a bit clumsy at the root, where it basically would think twice in a row, first iterating for the first leg, and then when it plays it, iterating for the second leg. Perhaps I should change that to limit the depth of the second search to that of the first minus one orthodox ply, to prevent that after an immediate hash hit on the second leg at that depth, it tries to improve.

I believe that you will find a lot more that needs to be changed. For instance, at the interface level you need to deal with a different user move string, e.g. "d2d4,e2e4"; when playing the engine move you need to send one or (in most cases) two moves; there will be changes in the end-of-game detection, e.g. stalemate is different (which also affects the search); repetition detection needs to be changed so that you only consider positions after the last of up to two legs; collection of PVs (provided you do that already - maybe you don't in FairyMax but other programmers do it) will be different if you have your additional recursion; and so on.

We would also need to think about the application of the 50-moves rule. Does it apply to 50 move pairs of both sides (which would be a lot: up to 100 "reversible" legs to be played until it is a draw), or to 50 legs of both sides (which would be difficult to define since moves where the first leg gives check have only one leg, so one player might have played 47 reversible legs and the other already 50), or maybe to 25 move pairs of both sides? It may be unlikely to ever occur in a real Marseillais game, but leaving this issue open for interpretation does not solve the problem at all. So how should we deal with the 50-moves rule?

One more issue comes into mind: what about the null move pruning? There is also a way to achieve the same effect as a null move with regular moves, and that is to make a reversible first leg and then immediately undo it in the second leg, as in Ng1-f3,Nf3-g1. This is a valid move that may have a strategical (or even tactical) reason, so does it deserve a reduction like the "real null move"? And we may have several such move pairs, all having the same effect, so should we map all of them to just one such move pair, e.g. Nb1-c3,Nc3-b1 has the same effect as Ng1-f3,Nf3-g1, so that we can omit to try both?

[hgm]

Well, writing a strong engine from scratch is more than I would want to do for Marseillaise Chess. If I am going to do anything at all, it must at most take an afternoon. The only move sorting in Fairy-Max is that it tries the hash moves first. After that it simply searches all moves (including a repeat of the hash move) in move-generation order. IID must take care of it that a hash moves is discovered cheaply. Because IID starts with QS (or in fact with a pre-QS that picks out the MVV/LVA move), captures are in fact searched before non-captures.

Grabbing the biggest you can get in the first leg seems a good strategy in Marseillaise anyway. If it was protected you simply withdraw on the second leg for a hit-and-run, if something big was threatened you rescue it on the second leg. Only if you are in check it would not work, but you would know that immediately, as all moves but the evations would return with -INF score.

The modifications I had in mind where:
* add the 'leg' parameter to Search
* if pre-QS detects King capture, return +INF (done now) only in the first leg, and return a null-move second-leg search
* if the null-move search returns -INF (i.e. in-check) in the second leg, we return -INF immediately
* indeed the leg should of course be encoded in the hash key, like stm (just add leg*SOMEMAGICNUMBER to it)
* search non-captures in the first leg at any depth (also QS)

A problem might be that the null move can become best move / hash move in the second leg. So I would have to think about how to encode it.

[Sven]

Well, writing a strong engine from scratch is more than I would want to do for Marseillaise Chess. If I am going to do anything at all, it must at most take an afternoon. The only move sorting in Fairy-Max is that it tries the hash moves first. After that it simply searches all moves (including a repeat of the hash move) in move-generation order. IID must take care of it that a hash moves is discovered cheaply. Because IID starts with QS (or in fact with a pre-QS that picks out the MVV/LVA move), captures are in fact searched before non-captures.

Grabbing the biggest you can get in the first leg seems a good strategy in Marseillaise anyway. If it was protected you simply withdraw on the second leg for a hit-and-run, if something big was threatened you rescue it on the second leg. Only if you are in check it would not work, but you would know that immediately, as all moves but the evations would return with -INF score.

The modifications I had in mind where:
* add the 'leg' parameter to Search
* if pre-QS detects King capture, return +INF (done now) only in the first leg, and return a null-move second-leg search
* if the null-move search returns -INF (i.e. in-check) in the second leg, we return -INF immediately
* indeed the leg should of course be encoded in the hash key, like stm (just add leg*SOMEMAGICNUMBER to it)
* search non-captures in the first leg at any depth (also QS)

A problem might be that the null move can become best move / hash move in the second leg. So I would have to think about how to encode it.

Well, I tried do discuss what should be done in general to implement that variant. You focus on FairyMax, no problem for me. As I said: interests are different. But then we also do not discuss the same thing. You may be right about what needs to be modified in FairyMax on that one afternoon that you want to spend for it. I have no doubt that you can do it. It just won't have much in common with the way I would go, it would be just a couple of "hacks". That's fine for me, everyone does it the way he likes best