From: Ruby Quiz <james@...>
Date: 2005-06-23T22:03:31+09:00
Subject: [SUMMARY] Chess Variants (II) (#36)

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:

	# 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:

	#
	# 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:

	# 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:

	# 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...