One of the greatest challenges in programming is modular design. Building code that adapts well to change is a Holy Grail quest for most of us. This two-part Ruby Quiz is designed to put your ability to predict the future to the test.
This week, the Ruby Quiz is to build an engine for two player chess. Note that I said "two player" there. You are not expected to develop an AI at any point, just a board and piece interface players can use for games. The game should prevent illegal moves, make sure the right player moves at the right time, declare a winner when a game ends, etc.
You can use any interface you like, but my recommendation is to keep it as simple as possible. ASCII art is fine. Pieces are traditionally represented as follows:
K = King
Q = Queen
B = Bishop
N = Knight
R = Rook
P = Pawn
Uppercase is usually used for white pieces, lowercase for black. It's fine to assume that both players alternate turns at the same keyboard. Just provide some means to make moves and see the resulting position. That's all we need.
Next week, in part two of this quiz, I will provide a list of chess variants you are expected to modify your program to support. You may prepare for this with your initial version in any way that you like (plug-in support, a domain specific language for chess games, etc.) There is little point in trying to predict my chosen variations exactly though. You don't want to know how many different variations there are to chess, trust me.
Please do not post any variations this week, even after the spoiler period. For now, we are concerned only with standard chess.
If you are not familiar with the rules of chess, you can read about them here:
Note the description of the "en-passant" rule for pawns. Some casual chess players are not aware of this rule. Some people are also unaware that you can castle to queenside, but you can as the rules show.
You do not need to concern yourself with chess notation (unless you want to use it as an interface) or recognizing draws (other than stalemate). You should recognize check (because it affects legal moves) and checkmate (as it signals the end of the game).
Quiz Summary
As Gavin Kistner pointed out, this quiz was too much work. There's nothing that hard about a chess game, as long as you don't need an AI, but there's just a lot of things you have to take care of.
You have to define moves for six different pieces, build a board with some helper methods that can handle chess geometry, and handle edge cases like en-passant, castling and pawn promotion. That's just a lot of tedious work.
Check is the real challenge, for me anyway, because it affects so much of the game. You must get out of check when you're in check. You can never make a move that puts you in check. You can't even castle through a square if you would be in check in that square. All that eventually adds up.
What I should have done with this quiz was provide a chess library and then ask for the variations, which is the interesting part of the challenge. Luckily, Ruby Quiz solvers are always making me look good, and that's basically what we have now, thanks to their efforts. Three people have submitted libraries and another person has submitted an example of how to use an existing library to solve this problem, with very little code even. Now, if anyone else wants to give round two a try, my hope is that you'll use these libraries as jumping off points and still be able to join in on the fun.
The three libraries are surprisingly similar. We all had about the same idea, build a class hierarchy for the pieces and create a board. I believe even Bangkok, the library used by Jim Menard's example works that way. The idea is that common chess piece behavior goes in a Piece class. Then you subclass Piece for Pawn, Knight, etc., adding the unique behaviors. In chess, this generally amounts to the piece's unique moves.
Paolo Capriotti skipped the chess subclasses and rolled the move types into the Board class. This isn't unreasonable. Knowing what moves a piece can make at any point in the game requires knowledge of the board. Those of us who use piece classes pass the board down to the piece to account for this. Paolo just reverses that.
The other essential part of a chess library is a Board object, as I said before. Chess definitely has its own geometry and you need an object that encompasses that. One question is how to refer to the square themselves. You can go with a two dimensional array style notation, wrap those x and y pairs in a class, or lean on chess notation and accept things like "e4". When dealing with chess positions, we often need information about ranks, files, diagonals, those wacky L-shaped knight jumps, etc. Board provides this information as well.
Obviously, Board also needs to provide piece moving routines and this can be heavy lifting. These methods need to be aware of castling, pawn promotion, en-passant capture, and check. That's the real guts of a chess game.
I'm not going to dump entire chess libraries in here. Instead, I'll show usage. Here's Paolo's chess game portion of rchess.rb:
attr_reader :board
include UI
def initialize
@board = Board.new(8,8)
@board.promotion_piece = :queen
(0...8).each do |x|
@board[x,1] = Piece.new( :black, :pawn )
@board[x,6] = Piece.new( :white, :pawn )
end
@board[0,0] = Piece.new( :black, :rook )
@board[1,0] = Piece.new( :black, :knight )
@board[2,0] = Piece.new( :black, :bishop )
@board[3,0] = Piece.new( :black, :queen )
@board[4,0] = Piece.new( :black, :king )
@board[5,0] = Piece.new( :black, :bishop )
@board[6,0] = Piece.new( :black, :knight )
@board[7,0] = Piece.new( :black, :rook )
@board[0,7] = Piece.new( :white, :rook )
@board[1,7] = Piece.new( :white, :knight )
@board[2,7] = Piece.new( :white, :bishop )
@board[3,7] = Piece.new( :white, :queen )
@board[4,7] = Piece.new( :white, :king )
@board[5,7] = Piece.new( :white, :bishop )
@board[6,7] = Piece.new( :white, :knight )
@board[7,7] = Piece.new( :white, :rook )
end
def play
while (state = @board.game_state) == :in_game
begin
move
rescue RuntimeError => err
print "\n"
if err.message == "no move"
say :exiting
else
say err.message
end
return
end
end
show_board
say state
end
def move
loop do
say ""
show_board
from, to = ask_move
raise "no move" unless from
if @board.is_valid(from) and @board.is_valid(to) and
@board.legal_move(from, to)
if @board.promotion(from, to)
@board.promotion_piece = ask_promotion_piece
end
@board.move(from, to)
break
else
say :invalid_move
end
end
end
end
@game = ChessGame.new
@game.play
You can see that Paolo's library also includes a UI module, which this game object makes use of. The constructor is straight forward, it sets up some initial state information, including a board, and places the pieces in their starting positions. Notice that the Board object is indexed as a multidimensional array and the pieces can be constructed from just a color and a type.
The play() method is the game itself. It's really just a loop looking for an end game condition. Aside from a little error checking and displaying the final state, it simply calls move() again and again.
Which brings us to the move() method. It shows the board (with the help of the UI method show_board()) and then asks for a move (another UI helper). You can see that the move is validated using the Board object, and then Board.move() is called to advance the game.
The final two lines kick off the methods we just examined. All the details are handled by the library itself.
Here's the same thing using my own library:
# chess
#
# Created by James Edward Gray II on 2005-06-14.
# Copyright 2005 Gray Productions. All rights reserved.
require "chess"
board = Chess::Board.new
puts
puts "Welcome to Ruby Quiz Chess."
# player move loop
loop do
# show board
puts
puts board
puts
# watch for end conditions
if board.in_checkmate?
puts "Checkmate! " +
"It's #{board.turn == :white ? 'Black' : 'White'}'s game."
puts
break
elsif board.in_stalemate?
puts "Stalemate."
puts
break
elsif board.in_check?
puts "Check."
end
# move input loop
move = nil
loop do
print "#{board.turn.to_s.capitalize}'s Move (from to): "
move = $stdin.gets.chomp
# validate move
moves = board.moves
if move !~ /^\s*([a-h][1-8])\s*([a-h][1-8])\s*$/
puts "Invalid move format. Use from to. (Example: e2 e4.)"
elsif board[$1].nil?
puts "No piece on that square."
elsif board[$1].color != board.turn
puts "That's not your piece to move."
elsif board.in_check? and ( (m = moves.assoc($1)).nil? or
not m.last.include?($2) )
puts "You must move out of check."
elsif not (board[$1].captures + board[$1].moves).include?($2)
puts "That piece can't move to that square."
elsif ((m = moves.assoc($1)).nil? or not m.last.include?($2))
puts "You can't move into check."
else
break
end
end
# make move, with promotion if needed
if board[$1].is_a?(Chess::Pawn) and $2[1, 1] == "8"
from, to = $1, $2
print "Promote to (k, b, r, or q)? "
promote = $stdin.gets.chomp
case promote.downcase[0, 1]
when "k"
board.move($1, $2, Chess::Knight)
when "b"
board.move($1, $2, Chess::Bishop)
when "r"
board.move($1, $2, Chess::Rook)
else
board.move($1, $2, Chess::Queen)
end
else
board.move($1, $2)
end
end
I pull in my chess library, and create a Chess::Board. Next, I display a welcome message then launch into my game loop which begins by printing the board. My Board object defines to_s(), so you can just print it as needed.
My chess game then checks for game end conditions using helper methods on Board like in_checkmate?() and in_stalemate?(). When found, the code prints messages and breaks out of the game loop.
The next loop is my move input loop. It looks like a lot of code but there are two good reasons for that. One, I wanted good error messages, so I'm checking every little thing that could have gone wrong and printing a custom message for it. Two, I avoiding using HighLine to simplify the process, so I wouldn't add the dependancy to the library. So really I'm just reading input and printing error messages here, nothing exciting.
The final chunk of code checks to see if the requested move is a pawn promotion. When it is, the user is prompted to choose the new piece type. Either way, the requested move is passed along to Board.move(), which handles the rest of the game.
One last example. Let's look at Gavin Kistner's code:
include GKChess
require "rubygems"
require "highline/import"
board = Board.new
while !board.game_over?
puts "\n#{board}\n\n"
puts "Move ##{board.move_number}, #{board.turn}'s turn"
#puts "(#{@turn} is in check)" if board.king_in_check?( @turn )
piece = ask( "\tPiece to move: ",
lambda { |loc| board[ loc ] } ){ |q|
q.responses[ :not_valid ] = ""
q.validate = lambda { |loc|
case loc
when /[a-h][1-8]/i
if piece = board[ loc ]
if piece.color == board.turn
if !piece.possible_moves.empty?
true
else
puts "That #{piece.name} has no " +
"legal moves available."
false
end
else
puts "The #{piece.name} at #{loc} " +
"does not belong to #{board.turn}!"
false
end
else
puts "There is no piece at #{loc}!"
false
end
else
puts "(Please enter the location such as " +
"a8 or c3)"
false
end
}
}
valid_locations = piece.possible_moves.collect{ |move|
move.colrow
}
dest = ask( "\tMove #{piece.name} to: " ){ |q|
q.responses[ :not_valid ] = "The #{piece.name} cannot " +
"move there. Valid moves: " +
"#{valid_locations.sort.join(', ')}."
q.validate = lambda { |loc|
valid_locations.include?( loc.downcase )
}
}
board.move( piece.colrow, dest )
end
end
Gavin start's by pulling in the GKChess namespace and the HighLine library to ease the input fetching process. The code then creates a Board and loops looking for Board.game_over?(). It prints the board and turn, much like my own code did, then fetches a move from the player.
Again, this looks like a lot of code, mainly because of the error messages. The player is asked to select a piece (which HighLine fetches and returns), then the code loads all the valid moves for that piece (using possible_moves()). Finally, the player is asked to select one of those moves for the piece and Board.move() is called to make it happen.
As I said, all three solutions were surprisingly similar.
Now we have to think about how we would adapt these to chess variations. Obviously, you need to get a little familiar with your library of choice. Get to know the methods it provides. Then, you'll probably need to subclass some of the objects and override them with some special behavior. At that point, you should be able to plug your chess variant objects into something like the above examples. Of course, any code handles some changes better than others and that's were the real fun comes in.
I hope you'll consider giving next week's challenge a shot, even if you didn't suffer through this week's torture. Grab a library and start adapting. See how it goes.
I apologize for not estimating this challenge better and presenting it in a more digestible format. Thanks so much to Gavin Kistner, Jim Menard, and Paolo Capriotti for for trying it anyway!
