Chess Variants (II) (#36)

If you have not already done so, please read the Chess Variants (I) quiz. If you would like to work this quiz without working the previous quiz, try adapting one of the Chess Variant (I) solutions submitted by someone else.

This week's quiz, part two of the Chess Variants quiz, is to modify your chess playing program to support as many of the following variations as possible:

1. Fibonacci Chess -- The number of moves a player makes at one time is
determined by the Fibonacci number sequence. White begins by making one
move, then black responds with one move. White is then allowed two (1 +
1) moves, then black gets three (1 + 2). Putting a player in check ends
your turn, even if you have moves remaining.

2. Gun Chess -- Chess is played as normal and the pieces that can be
captured are unaltered, but a capturing piece does not move when taking
an opposing piece. As long as the move is a legal capture, the opposing
piece is simply removed and the capturing piece in untouched.

4. Madhouse Chess -- When a piece is captured, it is not removed from the
board, but instead moved to the square of the capturing player's choice.

3. Blackhole Chess -- The squares d5 and f5 are considered "blackholes".
Any piece moving onto or over either square vanishes as if it was
captured. A King moving onto these squares loses the game.

5. Extinction Chess -- Check and checkmate no longer apply. A player wins
by capturing all of a single piece type of the opposing army (both of
the rooks, for example). Pawns may promote to Kings and a pawn is
counted as the piece it promotes to. Promoting your last pawn is a
loss, unless it results in an immediate win.

6. Baseline Chess -- In this variation, the starting position is altered.
All pawns still appear on the usual squares, but players take turns
placing their major pieces along the back rank before play begins.
Castling is not allowed, but the rest of the rules are as normal.

7. Fairy Chess -- Just like normal chess, except the Queen becomes a Fairy.
A Fairy can make the normal moves of a Queen or jump exactly like a
Knight.

Except as noted above, each variation follows the normal rules of chess from last week's quiz.

Quiz Summary

Everyone must have worn themselves out on the crazy hard task last week and had no juice left for the easier one this week.

Since we're implementing these games in terms of some chess library, it's really best if you can restate the game in chess terms. Let's take Gun Chess, for example. Pieces don't move when capturing. That requires me to rewrite my library's move() method, which is too much work because of all the special cases. Instead, I can just restate the problem: Whenever a piece captures, it returns to the square it started on. That is trivial to implement:

ruby
# An enhanced chess board for playing Gun Chess.
class GunChess < Chess::Board
# Returns a numerical count of all the pieces on the board.
def count_pieces( )
find_all { |(square, piece)| piece }.size
end

# Make standard chess moves, save that capturing pieces do not move.
def move( from_square, to_square, promote_to = nil )
old_count = count_pieces

super # normal chess move

if count_pieces < old_count # if it was a capture...
move(to_square, from_square) # move the piece back
next_turn # fix the extra turn change
end

self
end
end

The overridden move() method is the key here. It counts the number of pieces on the board (using the helper method count_pieces()), then executes a normal chess move. Before returning, the pieces are again counted and if the number is less we move the piece back to it's starting square because a capture has just taken place.

Pop quiz: Why did I count the pieces, instead of checking for a piece on the to_square (which is probably easier)?

En-passant. When capturing en-passant, there is no piece on the to_square, but we can still spot it because the piece count will drop.

Let's examine another variation. Fairy Chess is just chess with an upgraded queen. That should be all the hint you need for an easy implementation. Subclass Chess::Queen and just add the new moves.

My library also requires you to update the king's awareness of check slightly. While it's good to have the ability to change check when needed, this is probably a weakness of my original library. It could find check using the moves of pieces on the board and then we would just need to add the fairy.

Anyway, here's what I came up with:

ruby
#
# The container for the behavior of a chess fairy. Fairies are simply
# treated as both a Queen and a Knight.
#
class Fairy < Chess::Queen
#
# Returns all the capturing moves for a Fairy on the provided _board_
# at the provided _square_ of the provided _color_.
#
def self.captures( board, square, color )
captures = Chess::Queen.captures(board, square, color)
captures += Chess::Knight.captures(board, square, color)
captures.sort
end

#
# Returns all the non-capturing moves for a Fairy on the provided
# _board_ at the provided _square_ of the provided _color_.
#
def self.moves( board, square, color )
moves = Chess::Queen.moves(board, square, color)
moves += Chess::Knight.moves(board, square, color)
moves.sort
end
end

# Make the Chess::King aware of the Fairy.
class FairyAwareKing < Chess::King
# Enhance in_check? to spot special Fairy moves.
def self.in_check?( bd, sq, col )
return true if Chess::Knight.captures(bd, sq, col).any? do |name|
bd[name].is_a?(Fairy)
end

Chess::King.in_check?( bd, sq, col )
end

# Make this piece show up as a normal King.
def to_s( )
if @color == :white then "K" else "k" end
end
end

# An enhanced chess board for playing Fairy Chess.
class FairyChess < Chess::Board
# Setup a normal board, then replace the queens with fairies.
def setup( )
super

@squares["d1"] = Fairy.new(self, "d1", :white)
@squares["d8"] = Fairy.new(self, "d8", :black)
@squares["e1"] = FairyAwareKing.new(self, "e1", :white)
@squares["e8"] = FairyAwareKing.new(self, "e8", :black)
end
end

The first class is my fairy. You can see that my library allows me to access the captures and moves of a queen and a knight. Adding those together gives us a fairy.

The second class is my updated king. It will know when it is in check by a fairy. Because Fairy is a subclass of Chess::Queen, the old check will already spot Chess::Queen threats from a Fairy. All I had to add was the Chess::Knight threats.

Finally, all the new board class has to do is change the initial setup() to include the two new pieces.

Blackhole Chess is even easier than the above two variations, because it's already stated in easy to implement terms. You can check to see if a move will cross one of the blackholes, and simply remove the moving piece when it will:

ruby
# An enhanced chess board for playing Blackhole Chess.
class BlackholeChess < Chess::Board
#
# A general purpose test to see if a _test_ square is between _start_
# and _finish_ squares, on a rank, file or diagonal.
#
def self.between?( start, finish, test )
test_rank, test_file = test[1, 1].to_i, test[0]
start_rank, start_file = start[1, 1].to_i, start[0]
finish_rank, finish_file = finish[1, 1].to_i, finish[0]

( test_rank == start_rank and test_rank == finish_rank and
test_file >= [start_file, finish_file].min and
test_file <= [start_file, finish_file].max ) or
( test_file == start_file and test_file == finish_file and
test_rank >= [start_rank, finish_rank].min and
test_rank <= [start_rank, finish_rank].max ) or
( (start_file - finish_file).abs ==
(start_rank - finish_rank).abs and
(start_file - test_file).abs ==
(start_rank - test_rank).abs and
(test_file - finish_file).abs ==
(test_rank - finish_rank).abs and
test_file >= [start_file, finish_file].min and
test_file <= [start_file, finish_file].max and
test_rank >= [start_rank, finish_rank].min and
test_rank <= [start_rank, finish_rank].max )
end

# End the game if a King goes missing.
def in_checkmate?( who = @turn )
if find { |(s, p)| p and p.color == who and p.is_a? Chess::King }
super
else
true
end
end

# Eliminate any piece moving through the blackholes.
def move( from_square, to_square, promote_to = nil )
if self.class.between?(from_square, to_square, "d5") or
self.class.between?(from_square, to_square, "f5")
@squares[from_square] = nil
next_turn
else
super
end

self
end

# Board display with two added blackholes.
def to_s( )
super.sub( /^(5\s+\|(?:[^|]+\|){3})[^|]+\|([^|]+\|)[^|]+\|/,
"\\1 * |\\2 * |" )
end
end

The between?() method is my helper for checking if a move will cross over a blackhole. You can glance down to move() to see it used, just as I described above. I also have to update in_checkmate?() to recognize a missing king as a losing condition and to_s() to draw the blackholes.

Fibonacci Chess is the easiest of the four I implemented, as long as your library has something like my next_turn() method to override:

ruby
# An enhanced chess board for playing Fibonacci Chess.
class FibonacciBoard < Chess::Board
# Setup chess board and initialize move count sequence.
def initialize( )
super

@fib1 = nil
@fib2 = nil
@count = 1
end

# Advance turn, as players complete moves in the Fibonacci sequence.
def next_turn( )
if @fib1.nil?
@fib1 = 1
elsif @fib2.nil?
@fib2 = 2
next_turn if in_check?(@turn == :white ? :black : :white)
elsif @count.zero? or
in_check?(@turn == :white ? :black : :white)
@fib1, @fib2 = @fib2, @fib1 + @fib2
@count = @fib2 - 1
else
@count -= 1
return
end

super
end

# Return a String description of the moves remaining.
def moves_remaining( )
if @fib1.nil? or @fib2.nil? or @count.zero?
"last move"
else
"#{@count + 1} moves"
end
end
end

As you can see, I just changed the traditional one turn flop to roll after Fibonacci N moves or the other player is placed in check, whichever comes first. The moves_remaining() method was a hook for the interface to give you a move countdown on your turn.

I didn't implement the other three variations, but I would use the same technique. Just shift their changes to something as close as possible to chess.

For example, with Madhouse Chess, you can use a very similar move() override to my Gun Chess example. Save a dup() of the board, instead of just the piece count, because you'll need access to the soon-to-be captured piece. Make a normal chess move, then check the before and after piece counts. If it dropped, prompt the player to select a square and move the captured piece from the old board to the new one at that location.

Baseline Chess is the easiest variation of all, I think. With my library, you can just override Chess::Board.setup() to prompt for the starting squares. Disabling castling is also trivial. Just make a nonsense move with the king after he's placed to the exact same square he was on. This makes the king think he has moved and so he won't allow castling moves.

Extinction Chess is probably the hardest variation (conceptually speaking--it's actually very little code). The first step is overriding Chess::Board.in_checkmate?() to spot the new win condition. Just walk the board looking for one of everything. Then you need to subclass Chess::King as I did in Fairy Chess to shut off check. Just replace in_check?() with something that always returns false. Don't forget to override Chess::Board.setup() to swap the old king out for the new one.

Okay, that's all for chess variants. Sorry again for the time sink element of this one. Faster quizzes are coming soon.

Let me remind everyone that Ruby Quiz is taking a break this weekend to encourage anyone who would like to to compete in the ICFP 05 programming contest. That contest is a lot of work, but they usually have excellent challenges and I think it's worth the effort. Ruby has had a small showing in previous years, so we need all the people showing off our favorite language we can get! Hope to see some familiar names there.

Ruby Quiz returns a week from tomorrow, when we'll build inference engines...