Comments/Ratings for a Single Item

I have not played this game personally, but I must say, for a multi-move variant, this game was very well-made.

Also, the new circle symbol in GC for past moves is very nice. However, this functionality doesn't seem to work with hexagonal boards (like Hex Shogi 91's).

Now that Game Courier supports viewing past moves without loading a new page for each move, it has become easier to annotate games. So, I played a sample game of Marseillais Chess against myself, then annotated it in one window while viewing it in another. I also made some fixes to the code for generating an HTML form after annotating a game. I have included the game on this page as one more example game.

Marsellais chess has a rule where each player moves 2 pieces in the same turn. Castling is considered a single move. All other castling rules apply.

I still wanted to comment a bit on legality checking and game-end detection:

There is no need to assign illegal moves the same score as a legal losing game termination. You can assign it an even lower score. This reminds me of the fact that there are many Xiangqi engines that prefer losing by perpetual checking over being mated in 1. But the behavior can entirely be controlled by setting the score for the various kinds of game termination; minimax or alpha-beta doesn't require a binary game outcome. (Luckily, or the heuristic evaluation would not be any good.) If losing by illegal move gets a lower score than any form of losing by legal means, minimax should always avoid it. Unless the game rules themselves are incomplete, and allow you to manoeuvre by legal moves into positions where you have no legal moves, but which are not defined as terminal. (Most common case of this is failing to define stalemate as game end in games where the goal is King capture, under the false assumption that you will always have pseudo-legal moves.) Even in that case the illegal-move score will merely show up in the root as the most dishonorable form of losing.

It is useful to distinguish 'direct' termination conditions (detectable from the move or piece counts, such as King capture or baring) from 'indirect' ones (depending on the location of pieces and how they move). 'Check' is already a complex condition, defined in terms of pseudo-legal moves. 'Legal' (and thus illegal) are again defined in terms of check. And 'checkmate' is defined in terms of 'legal'. These definitions taken at face value often imply search, being of the form "there must not exist a move that ...". The definition of checkmate even involves a two-ply search, as it requires all pseudo-legal moves to be searched for legality, which again requires all replies to be examined for King capture.

Now it is very possible that there exist shortcuts for doing these searches, e.g. check detection through the super-piece method, or mate detection through estabishing that the checker(s) cannot (all) be captured, nothing can be interposed to block the check(s), and the King has nowhere to withdraw to. This is pretty well developed for orthodox Chess, but can get arbitrary complex in arbitrary variants. E.g. for determining whether a square is attacked when there are hoppers, bent sliders or locust capturers around (not to mention Coordinators, Immobilizers and Pincher Pawns). The super-piece method requires generation of retrograde captures, which must be handled by dedicated code, which can easily be inconsistent with the prograde move generator used in search. And for mate detection, what if there is a Lion around that can capture two checkers in one move? Or capture one, and block the other? What if there are bent sliders, that can both be blocked on a single square? What if the checkers involve a hopper, and its mount can move away, capturing or blocking another checker? How do I determine whether a locust capturer will attack me after the evasion? If I just stick to the official definition of these game concepts I only need prograde pseudo-legal-move generation, and there is not nearly as much that could go wrong.

You mentioned the 'beaten path', but you should keep in mind that this is the path used by developers of engines for orthodox Chess, and thus might not necessarily lead to where you want to be. No matter how much smartness you built into your engine for more efficient detection of the game-end conditions, it will never hurt to be prepared for game rules where these shortcuts fail, and some illegal moves escape your dedicated detection for those. So I would recommend to reserve a score for 'illegal move', (which, with checking rules, would be the negated score of capture or extinction of royal(s)), so that your engine will not crash if you inadvertantly run into a King capture. And in any node detect whether enough of the moves you thought to be legal are indeed legal, so that you would not have to declare game end after all (with an appropriate score different from the illegal-move score, like a draw or a distance-to-root-corrected losing or winning score). Which is pretty easy by starting bestScore at the illegal-move value, and see at the end if it stayed there. In cases where your dedicated game-end detection fails, your would then have a safety net in the engine. As for the GUI, you could always subject all moves to a search to make sure they are legal, and make the depth of this search a parameter of the variant, which can then be increased for variants with unusually complex game-termination rules.

Since you brought up the rule in Shogi against checkmating a King in Shogi with a Pawn drop, I checked how I handled it in Game Courier. I handled it similarly. After checking for checkmate in the Post-Game code, my code checks whether the checkmate was due to a Pawn drop, and if it was, it reports an illegal move instead of concluding the game.

But then I am not so happy that this requires an alteration of the normal (full-turn) FENs, which would require w2 and b2 stm field in your proposal. I would much rather have it that the exceptional partial-turn FENs would require something special. As the full-move counter is actually completely useless, and in balanced Marseillais the first turn is special in that it only allows a single move, recognizing half-turn FENs by artificially setting their move count to 1 would be OK with me.

The WinBoard Alien Edition would not consider positions half-way a turn not as game positions; when you step through the game later it would always alternate player between two turns, and show the effect of the pair of moves (like it was dealing with castling). Animation of the move might tell you the order.

As to the legality issue: I took the pragmatic approach in my Shogi engines as well as WinBoard: I do not consider Pawn-drop mates illegal, just losing. If checkmate is detected, its scoring depends on whether the previous move was a Pawn drop or not. So even without engine WinBoard allows the user to enter the Pawn drop, which then will end the game for him as a loss. For Shogi this is of course entirely justifiable. But it would not disturb me if Marseillais was treated the same; if we thing it should not be allowed to stalemate yourself after the first turn, just detect the stalemate and declare it a loss if the user elects to play into it.

Ok, I see.  Yes, probably representing positions in the middle of turns would not be common.  But since ChessV considers the legs to be different moves, I needed to do something.  I don't want to break the property that everything has an FEN.

Yes, FEN is very useful in general. What I was questioning is whether it would be useful to design special FEN conventions for representing game states halfway a turn. I have never seen an orthodox-Chess puzzle like "white mates in four after he has touched his Rook", or people pushing for a FEN field to indicate which piece has been touched. Or a Chu Shogi problem that said "white mates, now that he has captured a Gold something with the first leg of his Lion move. Neither can I imagine why you would want to load a position half-way a turn in a GUI or engine.

More later

About the FEN: is this really needed? Why would one ever want to have a FEN for a position after the first move?

Really?  FENs are useful.  For example, the CECP setboard command.  I think the fact that ChessV will give you the FEN for the current position or load a new position by FEN in any game to be a useful feature.

[idea!] Why not use a fraction on the full-move counter if you want to do this? E.g. move 10.5 would mean after the first half of the 10th turn of the player on move

I'm sorry, but I don’t like this at all.  Instead of adjusting the side-to-move from “w2” to “w” and then to “b2”, you are going to go from “w” on move 10, to “w” but on move 10.5, and then to “b” and roll the move counter back to 10?  That is not cleaner than my approach.  And my approach is cleanly extensible to Progressive Chess

It seems to me that a Marseillais Chess cannot be implemented without some dedicated code that would be useless in single-move variants.

It is certainly true that allowing multi-move variants requires extra code.  So the goal was to add this capability in a modular fashion that is not specific to Marseillais.  ChessV has Rule objects which can be plugged in to enable various capabilities.  To support this, I made a special type of Rule called a MoveCompletionRule which handles updating the side-to-move when moves are made or unmade.  Every game must have exactly one of these.  Unless you are playing a multi-move variant, you just leave the default in place which just oscillates between white and black.  Other implementations can do more complex things.  The MarseillaisMoveCompletionRule can be plugged into any game – add it to Capablanca Chess and you have Marseillais Capablanca with one line of code.

It should be clear that you cannot judge the legality of a turn before you have seen the full turn

Well, this is what we are discussing... I wish to avoid that complexity, which I consider unnecessary and possibly undesirable, at least for Marseillais.  But you do have one excellent point, which is:

Take the Shogi Pawn-drop-mate ban.

Yeah.  That’s a problem.  I may not be able to avoid this issue long term since I deffinately want to be able to support Shogi.  I think that rule did cross my mind previously and I immediately pushed it to the side so as not to give myself nightmares.  Say, I wonder if Zillions can handle that rule?  I bet it can’t.

The other examples you give, like Paco Shako – are probably not going to happen – at least not unless other programmers start assisting me.  ChessV is now up to 400 files of source code.  It’s a ridiculously ambitious project for one guy in his spare time.  Some things just aren’t going to happen.  Unless I win the lottery.  Or find a wealthy benefactor.

The reason I mentioned QS was because I assumed this would be required to detect the fact that the previous ply exposed the King

That’s not how I am handling it.  One of the messages a Rule object can accept is MoveBeingMade – upon which it can update internal information (in the case of the castling rule or en passant rule), but it can also rule that the move is illegal.  The Checkmate rule handles MoveBeingMade, checks to see if the king is attacked, and rules the move illegal if it is.  And, determining if a square is attacked is also routed by message passing.  Butterfly Chess includes a CaptureByAdvance rule which handles the Advancer’s capture ability.  So the Checkmate rule handles MoveBeingMade, fires off IsSquareAttacked messages, which are picked up by the CaptureByAdvance rule.  So Butterfly Chess has both capture-by-advance and check/checkmate/stalemate without either Rule object knowing anything about the other!  Beyond that, support for Butterfly comes entirely from the scripting language - no C#, entirely plug-and-play. Computationally very inefficient, hence my lousy nodes-per-second, but that’s how ChessV is able to play such a wide variety of games and how I am able to add support for new games very quickly.

French translation:

Marseillais Chess is a chess variant where each player plays two successive moves. On top of the rules for the normal game, the players must honor the following rules:

• A player that is in check must evade the check on his first move.
• If a player checks a King with his first move, he loses the capability to play a second move.
• If, after having played his first move, a player finds himself in a position where it is impossible to play a legal move, this is considered a stalemate.
• En-passant capture should be performed with the first move, except when two e.p. captures are possible. In the latter case, the two e.p. captures can be made in each of the two moves.
• Pushing Pawns two spaces beyond their initial location cannot be considered a double move (two advances of one space). So the player can make his second move after that.

About the FEN: is this really needed? Why would one ever want to have a FEN for a position after the first move? In orthodox Chess we also do not have a special form of the turn indicator for positions half-way a castling, where the King has already moved and the Rook is yet to move. Or in Chu Shogi, for after the Lion made the first leg of a locust capture. The exceptional case for the initial position can already be recognized from the full-move counter in the FEN.

[idea!] Why not use a fraction on the full-move counter if you want to do this?  E.g. move 10.5 would mean after the first half of the 10th turn of the player on move.

As to legal move generation:

It seems to me that a Marseillais Chess cannot be implemented without some dedicated code that would be useless in single-move variants. One task for this code would be to score a stalemate after the first move different from one before it, namely as an illegal position (whatever score you want to use for that) rather than a draw. A second task should be to treat first-moves  that get such a score as illegal moves, i.e. ignore them, and correct the legal-move count that might have been made during move generation for it. This would need a 'delayed' mate detection to handle the case where this count hits zero because all 1-move-legal moves turn out to cause self-stalemate the player, aborting the node with a checkmated or a draw score depending on the in-check status.

It should be clear that you cannot judge the legality of a turn before you have seen the full turn. So that would be 2 ply in Marseillais, and a progressive number of ply in Progressive. If you wouldn't try the last ply of the turn, you could never know if the turn can be legally completed. Unless of course the rules guarantee there always is a legal move irrespective of the position, e.g. because passing on the second turn is always allowed. If you do a full judgement on the legality of the position after the turn, one turn should be enough.

The reason I mentioned QS was because I assumed this would be required to detect the fact that the previous ply exposed the King. The assumption was that the root node of QS would start generating moves, and detect that one of the moves captured the King before really searching any. And then abort with a very happy score. So it would always be a 1-node QS, or a dedicated King-capture test, if you want. Depending on the variant there could be simpler ways to detect King capture than generating all moves and see what they hit. E.g. making all possible retrograde captures from the King, and see if they hit an enemy that reciprocates one (sometimes referred to as the 'super-piece method').  Depending on the complexity of the moves in the variant the super-piece method might be cheap or very expensive. (E.g. bent sliders, Cannons or Fire Demons are a pain.) Just generating all prograde capture moves, which you must be able to do anyway, is always a sure method, though.

How much extra you need compared to the turn you want to judge the legality of unavoidably depends on how complex the conditions for legality can be in the variant at hand. Take the Shogi Pawn-drop-mate ban. To detect it you must be able to see that that the Pawn drop checks (which is of course trivial), but that every conceivable reply move is illegal (exposes your King, or perhaps (worse) completes a perpetual checking cycle). So that is two turns plus a King capture test.

But it can be worse. Imagine a variant where it is illegal (rather than just losing) to expose yourself to mate-in-1 (rather than just to King capture). To judge a move you then have to take into account all replies that check, and then all evasions to any of those, to see if these expose the King. That is 3 ply + 'QS' (or 2-ply + mate-test). Imagine a variant where it is illegal to check when you cannot continue checking until you checkmate. (Tsume Chess?) Far fetched? Take the chained release moves of Paco Shako, implemented as a multi-move turn. It is illegal to release a piece from an embrace (by jumping into it) if the released piece cannot find an empty square to go to, an enemy to enbrace, or trigger another legal release. You will have to verify that at least one chain of releases (no matter how long) exists that terminates. There is just no predicting how many ply it can take.

Is there any French speaker here who can provide an accurate English translation of this? Google translate is not good enough to make it clear.

Les échecs marseillais sont une variante du jeu d'échecs où chaque joueur joue deux coups à la suite. En plus des règles du jeu normales, les joueurs doivent respecter les règles suivantes :

• Un joueur en situation d'échec doit parer l'échec au premier de ses deux coups.
• Si un joueur fait échec au roi au premier coup, il perd la faculté de jouer son deuxième coup.
• Si après avoir joué son premier coup, un joueur se trouve dans une situation où il lui est impossible de jouer un coup légal, il est déclaré pat.
• La prise en passant doit être effectuée au premier coup sauf si deux prises en passant sont possibles. Dans ce dernier cas, les deux prises en passant peuvent être effectuées à chacun des deux coups.
• L'avance de deux cases des pions depuis leur position initiale ne peut pas être considérée comme un coup double (avance de deux fois une case). Donc le joueur peut jouer ensuite son deuxième coup.

An additional note, which I will add to the text of the page itself at some point, when we finish discussing modern Marseilleas:

The concept of an FEN Notation needs to be updated for Marseillais Chess.  ChessV can load/save an FEN for any game, so I needed to decide how to enhance FEN for Marseillais.  The only part that needs to be expanded is the part that records the side on the move - typically "w" or "b".  I add the additional options of "w2" for white on-the-move with two moves still to make and "b2" for black on-the-move with two moves still to make.  I like this alteration in part because the starting position for a (balanced) game still has the same FEN as orthodox chess.

We might miscommunicate, because I am thinking in terms of a pseudo-legal-move search, while you might want to determine move legality before searching them.

A reasonable distinction - from the point of view of a pure engine, it might not matter if a move is technically legal if you return -INFINITY for those moves that aren't.  For a GUI (that is, either Game Courier, or ChessV at the root), we need to know what is legal vs. illegal, although you do address this (quoted later.)

IMO independently trying to establish legality of moves in a search is just a waste of time, as moves are legal more often than not. Just do the search, and when the move is illegal this will discover it soon enough, and will return -INFINITY. But most of the time there is nothing to discover. As long as an illegal move will get a score lower or equal than anything else, the search will work fine.

What you say makes perfect sense.  It does.  And yet, Stockfish does not work this way.  It does not allow a king to be captured and evaluate it badly - rather, it considers that move to be illegal, even in a deep search.  I've looked at a ton of open source chess engines, and what you desribe is not how they work.  In truth, I don't really "understand" chess engines well at all - I sort of understand, but have a very, very hard time visualizing it.  You clearly understand these things on a level that I do not. I'm really just a sophisticated copy-cat who models my open-source engine after the code of others.  What you describe is a nice simplificaiton, but you are far off the beaten path and I am reluctant to follow you down this road, especially given that ChessV doesn't just play Chess, it plays over a hundred games, and it does it with absolutely NO "special cases" for any given game jammed in the middle of anything.  None.  It does what it does by means of a very sophisticated architecture of message-passing between Game, Piece, PieceType, and Rule classes glued together dynamically at run-time.  Not to brag, but there is nothing else in the world like it.  I don't want to tear apart what works on promise of what might be a 0.01% improvment in a typical game, nor what might make an unlikely corner-case of Marseillais more playable.

If you want to test legality of an input move, just do a sufficiently deep search on it (1 ply + QS in normal chess, 2 ply + QS in Marseillais), and reject it if the score is -INFINITY. You don't need any special code for that.

Ok, here you might be right.  As a GUI, I really only need to know what is legal at the root, and again, what you say makes sense.  But I am afraid to follow you.  For one thing, ChessV must, must, must do the right thing in every chess variant which it comes across.  I stipulate that as an immutable parameter of its design (a parameter which I have temporarily broken by implementing Makruk without the counting rules.)  Is it always the case that an evaluation of -INFINITY (game lost) is the same as a move that is not legal?  And 1 ply + QS in normal chess, 2 ply + QS in Marseillais?  Doesn't this already indicate that we don't really know and we are doing an approximation?  Is this univerally applicable to all variants it supports and may support?  For Progressive Chess, does it need to be X ply + QS?  And what the heck does QS even mean in terms of a game like Marseillas where there are no quiescent positions?

Please don't misintrepret - I am not doubting you.  Your engines are awesome and there are many different games where you have the best engine in existance and, in some cases, the only engine.  I'm not doubting you.  I'm doubting MYSELF.  I'm just not willing to make a radical change when I cannot fathom the consequences.

All that said, at some point I will have a sophisticated test suite of dozens of positions in dozens of different games so I can test architectural changes with some level of confidence.  For example, I really like the alternative to mate-distance-pruning you suggested on another forum that is like a universal application of it that prefers the shortest route to any advantage.  It seems genious, and I want to use it.  But I'm afraid, given that Stockfish doesn't use it ...  And I have no robust test suite to prove it doesn't break anything...

We might miscommunicate, because I am thinking in terms of a pseudo-legal-move search, while you might want to determine move legality before searching them. For me an illegal move is simply a move that receives score -INFINITY when I search it. In an engine for normal chess this happens when the next ply captures your King, which gets awarded +INFINITY, and is then negated. Incidentally -INFINITY is also the start value of bestScore, and if it is left at -INFINITY all of the moves must have been illegal. That means mate or stalemate, and if stalemate is a loss both can get the same score, and -INFINITY would be a very suitable value, and you don't really have to do anything other than just returning the maximum move score.

IMO independently trying to establish legality of moves in a search is just a waste of time, as moves are legal more often than not. Just do the search, and when the move is illegal this will discover it soon enough, and will return -INFINITY. But most of the time there is nothing to discover. As long as an illegal move will get a score lower or equal than anything else, the search will work fine.

If you want to test legality of an input move, just do a sufficiently deep search on it (1 ply + QS in normal chess, 2 ply + QS in Marseillais), and reject it if the score is -INFINITY. You don't need any special code for that. I you want to make a list of legal moves (e.g. for the purpose of highlighting taret squares), just write a small loop to subject every prseuo-legal move of interest to such a search.

I think you are describing what I already consider to be Marseillais Chess. In other words, what you are proposing is what I think we should be considereing to be actual Marseillais. But, in any event, what you describe is what ChessV is already doing under the name "Marseillais Chess" and what, on the other TalkChess thread, we agreed the rules to be (although we didn't get into the move-into-stalemate question)

Not arguing - if you are proposing we move forward with this, I am in complete agreement.

Aside from trying to reconstruct the original Marseillais Chess, I would like to propose a game I might call Simplified Marseillais Chess, which is designed with programming it in mind. It would follow the rule of Balanced Marseillais Chess of giving White only one move at the start of the game, it would allow en passant capture only of a Pawn moved on the last part of a player's turn, it would have a turn end with one move if there were no legal moves to follow it, and it would work with normal stalemate and checkmate on a player's first move. I think those are the main differences from regular Marseillais Chess. Is there anything I have overlooked?

Sorry if I'm falling behind in this conversation.  I'm working so messages are coming faster than I can consider or respond to them.  So, for now, I'm only responding to H.G's latest message:

I understand what you are saying here, but I'm not sure how this addresses the issue.  Perhaps the conversation has already moved beyond what I think we are talking about. Regarding the "move into stalemate" issue, H. G. said:

The pair of moves should be legal, and a first move that only occurs in illegal pairs should therefore be considered illegal itself.

I think this is what we were talking about.  If it's not, please let me know.  You describe assigning a stalemate score to a move pair, but I don't think this does anything about making a first move ILLEGAL if it leads to a stalemate when there is an alternate possibility.  If we've already written this off as unworkable, great.  If we're still talking about it, I don't think it is reasonably doable.

Regarding Sven's eninge - that would be awesome.  I didn't remember this from the thread and going back now, it seems this file is no longer available.

One more question remains. While the rules seem to allow for second-order stalemate when the King is not in check, what about when the King is in check? Should this count as checkmate or stalemate? From the understanding that checkmate is check plus stalemate, we could argue that check plus second-order stalemate is also checkmate. Or, we might argue that the ability to escape check, even if no follow-up move is possible by any means of escaping check, constitutes only stalemate. Here's an example:

Here's an example of what I'm calling a second-order stalemate. Black is not in check but has only one legal move.

For the sake of testing some endgame positions as I write the code, here is a game where I played both sides just to get a stalemate position.

Is this really a problem? If you score stalemate after the first move as -INFINITY (which it would automatically get when you score King capture as +INFINITY), the node that searches the first move will end up with score -INFINITY if it has no legal pair of moves. Only there you correct such a score to 'draw' if the player is not in check. This assumes actual checkmates get a slightly better score, either by adjusting them for distance to the root in the leaf itself, or by a delayed-loss bonus when propagating towards the root, so that positions heading for a forced checkmate will not be mistaken for stalemates. (Note that a consequence of the proposed rules is that when your only 1-step-legal check evasions stalemate yourself, this would count as a checkmate.)

BTW, I thought that Sven Schüle said he had made an engine, in the TalkChess discussion you already referred to. I never got around to making a Fairy-Max derivative for it.

I somewhat like the notion that a player can't make a first move that puts himself into stalemate if there is an alternate sequence.  Unfortunately, this would be extremely difficult for me to implement.  Like Zillions, ChessV handes multi-move variants by treating each leg as a separate move and implements the double move by adjusting when the side-to-move is flipped.  To implement this, I would not know if a move is legal without generating moves another level deep, and that would be a radical modification.  In practice, I think this would almost never come up in a real game.  I had a hard time even coming up with a position where I could test this.

So far as I know, there is no other xboard engine that plays Marseillais (or another GUI that enforces the rules.)  I really hope that changes.  To that end, I'm not inclined adopt an interpretation that makes it substantially harder to make a fully compliant engine to address a situation that is extremely rare at best.

Don't get me wrong - when trying to nail down the rules for classic games, ability to program them shouldn't be the top concern, and certainly shouldn't constitute a veto of clearly defined rules.  But the classic rules are in doubt, very likely were played with different interpretations at different times (to the extent these corner-cases were even considered), and the rules have been evolving.

I think I figured out how to interpret the rule in a way that uses stalemate but avoids the problem of letting a player deliberately move into stalemate. This is the interpretation that if a player does not have any combination of two legal moves, the game ends in stalemate at the very beginning of his turn. I could do it like this. After checking for regular check and stalemate in the Post-Game sections, I could try out the available legal moves to see if any are followed by legal moves, stopping as soon as I find at least one. For this, I would use a subroutine that returns false as soon as one legal move is found and does not take the time to go through all possible moves and calculate a list of legal moves. Since there are plenty of legal moves when lots of pieces are on the board, and a position without any combination of two legal moves would be most likely in a position with few pieces left, there should not be a heavy computational load for doing this.