Check out Glinski's Hexagonal Chess, our featured variant for May, 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 ]

Single Comment

Game Courier Logs. View the logs of games played on Game Courier.[All Comments] [Add Comment or Rating]
H. G. Muller wrote on Tue, May 14 07:19 AM UTC in reply to Fergus Duniho from 02:09 AM:

5. It checks whether the King is in check by checking whether any enemy piece can move to the King's space. As an optimization, it returns true as soon as it finds one check.

The efficiency of your algorithm depends on whether there is a fast method to answer the question "does the piece at square A attack square B", which then can be combined to a function "IsSquareAttacked" by looping over all pieces A. But for complex multi-leg moves (pieces that turn corners, or jump over others, or do not end their move at the square they attack) it is hard to find a shortcut even if you are writing dedicated code for it. Often the best way is to just generate all moves of the piece at A, and for each of those test if it happens to hit B. For simple sliders and leapers it would be possible to immediately exclude they are attacking B based on the (x,y) coordinates of the leap from B to A (e.g. x*y!=0 for a Rook), or even tabulate in which direction you would have to move to arrive at B (and then test whether this path is unobstructed).

I could of course classify pieces (or even their individual moves) as simple or complex, and use a fast "does A attack B" function for leaps and straight slides, and only generate the complex moves of all enemy pieces to test whether these hit B. Typically only a small fraction of the pieces will have complex moves, and then this could be competitive.

This optimization might be helpful when not using piece functions, but one thing about it concerns me. While it might be helpful in determining whether a move by the King would be into check, I'm not sure it will work for revealed checks. It is because of the possibility of revealed checks that my code checks for check for the position resulting from every single pseudo-legal move it finds.

Marking of attacked squares to weed out illegal King moves is just one of the two things the accelerated check test does. The other thing is that it tabulates for each board square which (attempted) sliding moves visit it. If such a move did not hit B before, it cannot hit B after a move that would not mutate at least one of the squares that the move visited. E.g. if a Cannon is looking at the King directly it would not check, but during move generation the first leg of the move in the direction of the King would have been attempted, and perhaps even succeeded by capturing something that was behind the King. But whether it succeeded or not, all the squares between Cannon and King would get this Cannon move added to the list of moves that visit them.

If the move to be tested for legality would land on an empty square between Cannon and King, it would see in the constructed table that there was a Cannon that had a move that went over the destination square, and thus will be affected. It will then retry that move of that Cannon, to test whether it hits the King in the new position. Likewise, it would see whether (say) a Bishop had been attacking its origin, and then rerun that Bishop move to test whether it hits the King. This takes care of discovered slides and hopper activation. Moves of other pieces, as well as other moves of these same pieces would not have to be tried; these were not hitting the King before, none of the squares they visited was mutated, so they won't hit the King now.

This is actually the most robust part of the algorithm, which would even work in case of multiple absolute royals: moves that were not checking before cannot check after a move that did not mutate any squares in their path. (But if there are Immobilizers...)

In general the algoritm is very fast: for each move with a royal you test whether the destination is marked as attacked, and for moves with non-royal pieces you only have to rerun the opponent sliding moves that were tabulated as hitting origin or destination (and occasionally other squares that were mutated). And on average there are fewer than 1 enemy sliding moves (i.e. moves that could potentially have continued if the occupancy of the square had been different) to a square, in a typical variant. So in many cases a pseudo-legal move can be accepted as legal by just concluding that the mover was not royal, and the origin and destination of it were not visited by any opponent move. When already in check, it always reruns the move that was delivering that check, as the first test. (Most moves would not resolve the check, and these can then be discarded without further testing.)

Anyway, it is possible to configure the preset to not use the accelerated test, and for a not-too-lage variant (8x8 or 10x10) this will probably work fine.