Check out Symmetric Chess, our featured variant for March, 2024.


[ Help | Earliest Comments | Latest Comments ]
[ List All Subjects of Discussion | Create New Subject of Discussion ]
[ List Earliest Comments Only For Pages | Games | Rated Pages | Rated Games | Subjects of Discussion ]

Comments/Ratings for a Single Item

Earlier Reverse Order Later
Mathematical definition of a chess piece?[Subject Thread] [Add Response]
Garth Wallace wrote on Tue, Nov 20, 2018 04:48 AM UTC:

For a while now I've been playing with the idea of defining chess pieces in strictly mathematical terms. Originally this was meant as a more flexible/descriptive alternative for Betza Funny Notation, perhaps as a way of specifying pieces for chess-variant-playing AIs, but there is also the possibility of defining operations and functions over them, and maybe even proving some things algebraically.

My early attempts were to define pieces as sets of possible paths, where paths are sequences of steps, and steps are vectors; notation would use the Kleene star for unlimited equal steps. So a wazir, for example, would be {(0,1),(1,0),(0,-1),(-1,0)}, and a rook would be {(0,1)(0,1)*,(1,0)(1,0)*,(0,-1)(0,-1)*,(-1,0)(-1,0)*}. Since most pieces are symmetrical it would make sense to parameterize this as a kind of shorthand, but since some pieces aren't symmetrical it shouldn't be assumed (in the way that "a 1,2 leaper" usually implies the (1,-2), (2,1), etc. leaps). This works for the usual steppers, leapers, and riders, and even bent riders; it's basically how people usually think of chess moves, just in more formal terms.

But this starts to get awkward where pawns are involved (and a way of describing chess pieces that has trouble with pawns is seriously flawed!). First off, we need to separate passive moves from captures. That's not too bad; we can even do so by introducing a "capture step" distinct from a passive step, which must be to a square occupied by an opposing piece, and this lets us do fun things like define the Chu Shogi Lion and the Locust. Then there's the initial double move, and promotions. We can introduce a new kind of "step" that is a promotion to another piece type to deal with these: the initial double-step can be implemented by defining a "starting pawn" that has it, where every move ends with a "promotion" to a "basic pawn" piece that doesn't. The promotion step is also strange, because it always happens at the end, but if you define operations that derive pieces from other pieces (like a "double move" operation that derives a Hook Mover from a Rook) in terms of sequence concatenation, you can end up with a promotion in the middle, or even more than one. So we've unfortunately introduced a distinction between "well-formed" and "ill-formed" pieces, and a need for some sort of normalization.

Introducing hoppers also complicates things. We have to introduce another step, one that requires a hurdle like the capture step but doesn't capture it. But now we've introduced the possibility of moves that "collapse": after all, what is the difference between a (1,2) knight move, and a pair of a regular mao-move and a mao-move over an obligatory hurdle?  Or between the latter and a pair of a regular moa-move and a moa-move over an obligatory hurdle? Equivalence is a mess.

I never found a satisfying way of dealing with en passant, or castling. Defining a piece in terms of the path is travels doesn't lend itself to a move where two pieces are repositioned.

Finally I realized that this approach fundamentally allowed for pathological alternate definitions of pieces. For example, take the rook. One or more equal orthogonal steps, right? Now let's define an "inside-out rook": a piece that leaps orthogonally directly to the square right next to its final destination, then slides by orthogonal steps until it reaches its starting square, then finally leaps directly to its final destination. This piece behaves exactly like the basic rook. It's entirely equivalent: any square it can reach, a standard rook can also reach under the same conditions, and vice versa. Yet it is considered a different piece. While the example is obviously contrived, similarly weird things could be produced by operations that concatenate or interpolate paths.


Garth Wallace wrote on Tue, Nov 20, 2018 07:31 AM UTC:

Because of the "inside-out rook" problem, I started trying to define equivalence for pieces in terms of what conditions (relative piece positions) a move can be performed under, until I realized that this was a much better way of defining moves in the first place. the inside-out rook demonstrates that the sequence of steps is entirely irrelevant, only which squares relative to the starting square can it be blocked on and how.

So at this point, I changed my approach. Instead of a path being a sequence of steps, it becomes a destination vector and a set of "tests", where a test is a pair of a vector and a state that must be true of the square that vector away from the starting square for the move to be legal.

A welcome byproduct of defining everything in terms of vectors from the starting square, instead of vectors from the previous step in a sequence, is that "exotic" board topologies become much easier to deal with. The sequence method was fine for hex boards (it's just a different set of basis vectors), but trying to define, say, a bishop on a moebius strip board was weird (try it!). But if all vectors are treated as having the same origin, there's nothing special about it.

Nice, right? Oops, forgot about divergent captures. Okay, instead of just a destination vector, we have a set of results, a set of "things that happen when the move is taken", which can include a destination and/or capture vectors. The Chu Shogi Lion's igui capture can be expressed as a move with a capture vector but no destination vector, since the Lion doesn't move; a null-move like the Lion's jitto is a move where the result set is the empty set ∅. Promotions? Another kind of member of a result set.

There's still a problem with promotion though. We need to know when it's an option. All moves are relative, but pawn promotion happens at a certain absolute position. Let's say that there is a "promotion zone" state for squares, and any pawn step onto a square with that state is a move with a promotion result. En passant can be defined in terms of a capture move to a "just stepped over by a pawn's double move" state. Of course hte problem here is that "state" is very vague. A promotion zone is permanent, but the en passant square only exists for one turn, and there's no way of specifying that sort of thing within this system yet.

Another important thing has been left out: black and white, or more generally sides. At this point I'd been mostly ignoring them and was thinking in terms of just e.g. "knight" rather than "black knight" and "white knight". I was more or less treating captures as explicitly affecting the opposite side. But that's not very flexible (it disallows, say, a hopper that can only use friendly hurdles, or a piece that can capture friendly pieces). Abstracting away the actual human players (who may not even exist, e.g. in a chess problem), what is the distinction between the sides? Alternating turns! Counting from the beginning of a game, white pieces move on odd-numbered plies and black on even-numbered plies (and neutral on all). So we should include, as part of a move's condition (set of tests), which plies it may be performed on, in most cases some number modulo the number of sides. Together with obligate promotion, we can even define oddities like Petkovian half-neutrals, which change sides when moved. Now that we've introduced a time dimension, we can even include that in our test vectors, allowing us to define en passant more concretely in terms of the previous turn's position instead of hand-waving an "en passant square" state.

I'll get into royal status, mimics, what a "state" really is, rethinking captures, and generalizing to almost everything later, but it's getting late and I have work tomorrow.


H. G. Muller wrote on Wed, Nov 21, 2018 09:39 AM UTC:

I am not sure how this comment could have ended up in this untitled discussion; I am pretty sure I posted it as a reply to Garth Wallace's piece-definition topic. This must be a bug of the posting system. Perhaps an editor can move this comment to the topic where it belongs. Moved. I'm not sure what could've happened to it initially. --BR

From a practical point of view: the Jocly move generator defines each piece type through a 'graph', which is a board-size array. For each square this stores a set of 'trajectories', where each trajectory is a set of (squares, rights) combinations. The 'rights' part indicates under which conditions the piece can move there: when it is empty, occupied by an enemy (the latter still distinguishing royal and non-royal enemies), or never (but passing through it). First occupied square in the trajectory normally makes all later squares inaccessible (but does not affect other trajectories), except when a capture specifies hopper-capture, in wich case it only considers the moves behind the first occupied square. (This obviously was added as a not very general kludge to be able to do Xiangqi.) By listing this for each board square separately, it does allow location-dependent moving, and boards of irregular topologies. Although the principal reason for doing it that way was probably just efficiency: the graphs would never contain any moves that stray off board, so you would never have to test for that during move generation.

The extended Betza notation used by the XBoard GUI (XBetza) indeed implements general hopping as the ability of a step V, or repeated sequence of identical steps VV* (together referred to as a 'leg' of the move) as a condition on the occupancy of the final square of that leg, namely that it must be occupied, but will not be affected. This makes no sense in final legs of a move, but in non-final leg this 'p' modality supplements the usual 'm' or 'c'. It makes no difference between friend or foe (as hoppers usually don't), but XBoard allows the use of the combination 'tp' to limit the hopping to friendly mounts. (At some point the alphabet is just too small... XBoard also uses 'tc' for a 'tame capture', i.e. one that cannot capture royalty.) As you remarked locust capture can be indicated by a non-final leg with capture rights. And lameness as a non-final leg with 'm' rights only.

To define pieces as the Ultima Withdrawer, still another modality is needed. In principle the move can be seen as a locust capture that starts with a King leg, and then reverses direction for a Queen leg of minimally 2 steps. (Which again can be seen as a King leg followed by a Queen leg in the same direction.) You cannot combine this move with a normal Queen move, because that would make the capture optional. (Which in Ultima it isn't.) But if you always force the detour, the move must not be blocked by a friendly piece there. This can be done by also giving it hop rights (so total modality of the first leg 'mcp'). But that still fails when the Withdrawer wants to move away from a board edge. So I needed an extra modality on non-filal legs for that ('o'), which means 'can (temporarily) leave the board. Then 'mcpo' on the first leg would do it. Similarly, the 'Advancer' would be given a move that overshoots its final destination to make a capture, and then inverts direction.

In my proposal for a Betza 2.0 I tried to solve the problem of combination moves like castling (or catapult pieces) by defining a 'u' modality for 'unload'. The idea is to have one piece transport the other. In any case there also has to be a modality for 'friendly fire' (I picked 'd' for 'destroy'), which enables you to capture friendly pieces. A 'u' in a later leg would then leave there what you 'picked up' (= captured or destroyed) on a previous leg.

Move induction (as in Knight-Relay Chess) is also an interesting problem. It could be seen as a move of the induced piece, but then it would have to 'probe' if a friendly Knight is attacking it. This can be done by a leg step that can hop onto friendly Knights only, and use the first two legs of the move to make back-and-forth Knight jumps, and then a final Knight jump if that was possible. Or it can be seen as a move of the inducer, where it hops onto a friendly piece, transports it by another Knight jump, unloads it there and then retraces its steps. When every piece is inducible, and only a single piece type can induce, the latter method is conceptually simpler. Otherwise you would have to assign the inducible moves to every piece. Except that it is rather cumbersome to have the inducer retrace its steps after it unloaded the induced piece. But for convenience you could make a special unload modality for that ('tu'), which would mean 'unload and return'.

As to the ambiguity of move definitions: to get rid of that you would have to abandon the concept of trajectories, but make 'lameness' an intrinsic part of the definition. So each move becomes a set of squares to be modified in some specified way, (usually just the 'from-square' that gets emptied, and the 'to-square' that gets to hold the moved piece or its promotion choice), plus a set of squares on which a certain condition has to be fulfilled with respect to its occupancy (usually that they have to be empty). As mathematical sets are considered the same irrespective of the order in which their elements are mentioned, and can mention each element only once, you would have no freedom in specifying the move. But this quickly leads to very cumbersome descriptions for sliders (which would be decomposed into lame steps of various distances), and even worse for sliding hoppers (which would have to specify each of their distant hops as a number of combination of empty and occupied squares along their path to make sure the move is only allowed if there is exactly one occupied square in the path).


Garth Wallace wrote on Thu, Nov 22, 2018 07:54 AM UTC:

Considering a move to be a set of changes on the board is, in fact, exactly where I ended up going with this. And you're right, it doesn't lend itself to a very compact notation—perhaps a summation-like notation could be introduced to make it easier to describe the common case where a subset of a pieces moves have a direct, progressive relation to each other (like riders). Though as an abstract formulation, it's really powerful. For example, castling is now easy to define. In fact, it seems like you can define nearly everything in the game in these terms, even things that aren't usually considered pieces or qualities of pieces.

I approached move induction in terms of Mimes. When I was still working with sequence-of-step paths, I basically gave up on describing them, which rankled because it meant that I couldn't use set operations like union or intersection on them like I could with "regular" pieces without a lot of hand-waving. When the analysis treats their behavior as "then a miracle occurs", you can't get very useful results. Knight-Relay would be the sort of thing that I wasn't able to deal with, since in that the pieces should really be describable as unions of regular pieces with very limited (knight-only) mimes, and I couldn't figure out how to describe a piece with moves that "changed".

After moving away from sequences, though, I realized that you could include the path from the "move-lending" piece to the mimic as part of the condition. This is basically equivalent to your first method, moving the mime onto the lender and back before proceding to its destination, except that there is no actual "moving", just checking to see if the right squares are unoccupied or occupied by the right pieces. This is nice because it means that mimes are still just sets of moves. The downside is that you can't really define a "generic" mime, since you have to know which pieces it can interact with. But in a way that makes sense, since you can't really draw any conclusions about what a mime is capable of without knowing what moves it can borrow anyway.

Similar reasoning can be applied to define Annan Chess (borrowing a move if there is an unbroken line backwards to the lender), and the Ultima Coordinator (actually simpler, since only the relative position of the friendly King matters).

Soon after hitting on this I realized that you could even apply this to the King's inability to move into check, by including tests for enemy attacks in all of the King's moves. Previously I'd assumed that royal status had to be dealt with in some way outside of this system, but it doesn't have to be. Royal status is really a blanket term that covers a few different qualities. It turns out that the rule against exposing a royal to check can also be expressed in this system, though counterintuitively it is a property of every other piece besides the royal.


4 comments displayed

Earlier Reverse Order Later

Permalink to the exact comments currently displayed.