[QUIZ] Chess Variants (I) (#35)
Ruby Quiz
1. Please do not post any solutions or spoiler discussion for this quiz until
48 hours have passed from the time on this message.
2. Support Ruby Quiz by submitting ideas as often as you can:
3. Enjoy!
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
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:
http://www.chessvariants.com/d.chess/chess.html
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).
Gavin Kistner
> This week, the Ruby Quiz is to build an engine for two player
> chess. Note that
> I said "two player" there.
> The game should
> prevent illegal moves, make sure the right player moves at the
> right time,
> declare a winner when a game ends, etc.
> If you are not familiar with the rules of chess, you can read about
> them here:
>
> http://www.chessvariants.com/d.chess/chess.html
>
> Note the description of the "en-passant" rule for pawns.
> Some people are also unaware that you can
> castle to queenside, but you can as the rules show.
> You should recognize check (because it affects legal moves) and
> checkmate (as it signals
> the end of the game).
This looks like a fun problem and (as my past two quizzes have shown)
I'm not a great judge of time required for a problem, but...is it
really expected that the above should take 30-60 minutes for an
average coder?
Am I that slow to imagine that the above is 3-5 hours (at minimum)?
James Edward Gray II
> This looks like a fun problem and (as my past two quizzes have
> shown) I'm not a great judge of time required for a problem,
> but...is it really expected that the above should take 30-60
> minutes for an average coder?
No, probably not. The time "goal" is, and has always been, a rough
guideline. This time I'm probably stretching it a little, but we've
also had quite a few easy quizzes lately, I think. Last week's may
have been the easiest one yet.
> Am I that slow to imagine that the above is 3-5 hours (at minimum)?
Your guess sounds a little high to me, but they may be because I'm a
chess nut.
A chess game is basically defined by the moves of six pieces, many of
which are trivial. The King is the biggest challenge, because you
need to look for check and checkmate, but that gives you the ending
conditions as well. Bishop and rook are no challenge at all and a
queen is a bishop plus a rook, right? A knight's movements are
probably harder to teach a human than a computer. The pawn is the
only other piece that requires a little work, I think. Do a little
thinking before you code and my guess is that a good plan can be
implemented a little faster than you think.
Beyond that, it's my opinion that this will be a really fun problem.
You try to leave your solution open to next week's challenge and see
how you fair. I'm hoping that will entice someone to give it a
chance...
However, the ultimate choice is naturally yours. If you think it's
too much of a time sink, skip this round. You always have this
option and it seems to me that many people take advantage of it
regularly.
If you haven't noticed by now, I work every quiz that no one
touches. That's my way of telling you that I don't ask you to do
anything I wouldn't do. So if you really think it's ridiculous you
can votes with your silence and "call my bluff". I feel this did
happen on the Yahtzee quiz and you guys were right that it was harder
than I intended. (You were dead wrong about not working the Code
Cleaning quiz though and I'm still bitter about that! <laughs>)
The moral is that I'm trying something a little different with this
quiz. We'll see if it flies... ;) I'm also listening though and I
now know that at least one of you considers it over the top.
James Edward Gray II
Gavin Kistner
> The moral is that I'm trying something a little different with this
> quiz. We'll see if it flies... ;) I'm also listening though and
> I now know that at least one of you considers it over the top.
Over the top for the stated 30-60 minutes, perhaps.
Certainly not over the top in terms of fun and worthiness. I'm coding
right now :)
James Edward Gray II
> Over the top for the stated 30-60 minutes, perhaps.
>
> Certainly not over the top in terms of fun and worthiness.
My biggest challenge in running Ruby Quiz is always coming up with
unique ideas. I try to find interesting challenges and sometimes I
think I even succeed. :)
Ruby Quiz fans have another right I forgot to mention in my last
message though. You can submit your own problems! I run your stuff
before mine, so the community could keep my quite for a good long
time if they desired. Instead, my inbox has been ghostly quiet lately.
Of course, I'm not targeting Gavin with that comment, since he holds
the Ruby Quiz submission record!
James Edward Gray II
Gavin Kistner
> you can as the rules show.
As castling involves moving two pieces with one move, how is it
traditionally specified?
Do you simply specify to move the King to the appropriate square, and
(because it is a distance-two move with a rook in the right spot and
all other criteria met) it is allowed and the rook is moved at the
same time?
James Edward Gray II
You nailed it. That's exactly how it's done in most of the software
I've ever seen. Or, if you were using notation to specify moves
castling is written:
O-O (kingside)
O-O-O (queenside)
James Edward Gray II
Jim Menard
> The three rules of Ruby Quiz:
>
> 1. Please do not post any solutions or spoiler discussion for this quiz until
> 48 hours have passed from the time on this message.
>
> 2. Support Ruby Quiz by submitting ideas as often as you can:
>
> http://www.rubyquiz.com/
>
> 3. Enjoy!
Can I start with Bangkok (http://bangkok.rubyforge.org), the
chess-game-replaying library I already wrote? :-)
Jim
--
Jim Menard, ji...@io.com, http://www.io.com/~jimm
"Even your Magic Eight Ball can tell you, 'Outlook not so good.'"
-- Chris Mattern in rec.arts.anime.misc
James Edward Gray II
> Ruby Quiz wrote:
>
>> The three rules of Ruby Quiz:
>> 1. Please do not post any solutions or spoiler discussion for
>> this quiz until
>> 48 hours have passed from the time on this message.
>> 2. Support Ruby Quiz by submitting ideas as often as you can:
>> http://www.rubyquiz.com/
>> 3. Enjoy!
>>
>
> Can I start with Bangkok (http://bangkok.rubyforge.org), the chess-
> game-replaying library I already wrote? :-)
Please do!
James Edward Gray II
Kristof Bastiaensen
>
> 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
>
>
for Ruby-Gtk. It doesn't implement an engine, but it is particularly well
suited for implementing Chess Variants. That is in fact what I intended
to do (write a program for variants of Shogi, Japanese Chess), but I
haven't found the time finish it. The board API however works very well
(even better that xboard if I may say so myself ;-). Adapting it for
another toolkit shouldn't be very difficult, but requires C-code, so may
be it would be to much effort for this quiz. I have some documentation,
but I haven't included it yet, so if anyone is interested I'll upload it.
You can find it at (http://gcboard.sourceforge.net)
KB
Paolo Capriotti
I don't know if I will have time to adapt it (it seems to me a highly
nontrivial task).
Best regards,
Paolo Capriotti
---
class Numeric
def sign
if self > 0
1
else
if self < 0 then -1 else 0 end
end
end
end
class Piece
attr_reader :type, :color
def initialize(color, type)
@type = type
@color = color
end
def type_initial
if @type == :knight
'n'
else
@type.to_s[0,1]
end
end
def ==(other)
return false unless other.respond_to?(:color)
(@type == other.type and @color == other.color)
end
end
class Vector
attr_reader :x, :y
def initialize(x,y)
@x,@y = x,y
end
def +(other)
x = @x + other[0]
y = @y + other[1]
Vector.new(x,y)
end
def -(other)
x = @x - other[0]
y = @y - other[1]
Vector.new(x,y)
end
def *(number)
x = @x * number
y = @y * number
Vector.new(x,y)
end
def ==(other)
return false unless other.respond_to?(:[])
@x == other[0] and @y == other[1]
end
def [](i)
case i
when 0
@x
when 1
@y
end
end
def clone
Vector.new(@x,@y)
end
end
class Board
attr_reader :size, :turn
attr_writer :promotion_piece
def initialize(size_x, size_y)
@size = Vector.new(size_x, size_y)
@board = []
(0...size_x).each do |x|
@board[x] = []
end
@turn = :white
@king_moved = Hash.new(false)
@queen_rook_moved = Hash.new(false)
@king_rook_moved = Hash.new(false)
end
def [](*position)
position = get_pos(position)
@board[position.x][position.y]
end
def []=(*args)
value = args.pop
position = get_pos(args)
@board[position.x][position.y] = value
self
end
def move(from, to)
piece = self[from]
execute_move(from, to)
case from
when king_starting_position
@king_moved[@turn] = true
when king_rook_starting_position
@king_rook_moved[@turn] = true
when queen_rook_starting_position
@queen_rook_moved[@turn] = true
end
if castling(from, to)
if to.x - from.x > 0
self[from+[1,0]] = self[king_rook_starting_position]
self[king_rook_starting_position] = nil
else
self[from+[-1,0]] = self[queen_rook_starting_position]
self[queen_rook_starting_position] = nil
end
end
if to == @en_passant
self[to-[0,pawn_dir]] = nil
end
if piece.type == :pawn and (to.y - from.y) == 2
@en_passant = to-[0,pawn_dir]
else
@en_passant = nil
end
switch_turn
end
def pseudolegal_move(from, to)
return false if from == to
piece = self[from]
return false unless piece
return false unless piece.color == turn
return false if self[to] and self[to].color == piece.color
d = to - from
case piece.type
when :king
if (d.x.abs <= 1 and d.y.abs <= 1)
return true
end
if castling(from, to)
return false if @king_moved[@turn]
if d.x > 0 # king side
return false if @king_rook_moved[@turn]
return false unless (self[from + [1,0]] == nil or self[from
+ [2,0]] == nil)
else
return false if @queen_rook_moved[@turn]
return false unless (from + [-1,0] == nil or from + [-2,0]
== nil or from + [-3,0] == nil)
end
return true
end
when :queen
return ((rook_slide(d) or bishop_slide(d)) and check_free_path(from, to))
when :rook
return (rook_slide(d) and check_free_path(from, to))
when :bishop
return (bishop_slide(d) and check_free_path(from, to))
when :knight
return knight_jump(d)
when :pawn
case d.x.abs
when 1
return (d.y == pawn_dir and ((self[to] and (not self[to].color
== piece.color)) or to == @en_passant))
when 0
case d.y
when pawn_dir
return self[to] == nil
when pawn_dir*2
return (from.y == rank(2) and self[from+[0,pawn_dir]] == nil
and self[to] == nil)
else
return false
end
else
return false
end
end
end
def legal_move(from, to)
return false unless pseudolegal_move(from, to)
old_turn = @turn
switch_turn
res = check_legality(from, to, old_turn)
@turn = old_turn
return res
end
def is_valid(*args)
position = get_pos(args)
position.x >= 0 and position.x < size.x and position.y >= 0 and
position.y < size.y
end
def find_piece(piece)
each_piece do |position, p|
return position if piece == p
end
return nil
end
def each_piece
(0...size.x).each do |x|
(0...size.y).each do |y|
pos = Vector.new(x,y)
piece = self[pos]
yield(Vector.new(x,y), self[x,y]) if self[x,y]
end
end
end
def show
(0...@size.y).each do |y|
(0...@size.x).each do |x|
piece = self[x,y]
if piece
s = piece.type_initial
s.upcase! if (piece.color == :white)
print s, ' '
else
print ' '
end
end
print "\n"
end
print "\n"
end
def promotion(from, to)
to.y == rank(8) and self[from].type == :pawn
end
def capturing(from, to)
return true if self[to]
self[from].type == :pawn and (not from.x == to.x)
end
def game_state
generator = MoveGenerator.new(self)
if generator.unstalled
return :in_game
else
old_turn = @turn
switch_turn
if leaving_king_safe(old_turn)
res = :stalemate
else
res = (@turn == :white ? :white_wins : :black_wins)
end
return res
end
end
def pawn_dir
@turn == :white ? -1 : 1
end
def rank(r)
@turn == :white ? 8 - r : r - 1
end
def possible_starting_points(piece_type, to, capt)
generator = MoveGenerator.new(self) do |from, dest|
if to == dest and self[from].type == piece_type and
pseudolegal_move(from, dest) and capturing(from, to) == capt
from
end
end
generator.generate_all
end
def king_starting_position
Vector.new(4, rank(1))
end
def king_rook_starting_position
Vector.new(7, rank(1))
end
def queen_rook_starting_position
Vector.new(0, rank(1))
end
private
def check_legality(from, to, old_turn)
if castling(from, to)
castling_directions(from, to)+[[0,0]].each do |direction|
return false unless leaving_position_safe(from+direction)
end
end
old_board = []
(0...size.x).each do |x|
old_board[x] = @board[x].clone
end
execute_move(from, to)
res = leaving_king_safe(old_turn)
@board = old_board
res
end
def check_free_path(from, to)
d = to - from
inc = [d.x.sign, d.y.sign]
pos = from.clone
while not pos == to - inc
pos += inc
return false if self[pos]
end
return true
end
def castling(from, to)
from == king_starting_position and (from-to).x.abs == 2
end
def rook_slide(d)
d.x == 0 or d.y == 0
end
def bishop_slide(d)
d.x.abs == d.y.abs
end
def knight_jump(d)
(d.x.abs == 2 and d.y.abs == 1) or (d.x.abs == 1 and d.y.abs == 2)
end
def switch_turn
@turn = (@turn == :white ? :black : :white)
end
def leaving_king_safe(old_turn)
king_pos = find_piece(Piece.new(old_turn, :king))
leaving_position_safe(king_pos)
end
def castling_directions(from, to)
if (to.x > from.x)
return [[1,0]]
else
return [[-1,0],[-2,0]]
end
end
def leaving_position_safe(safepos)
each_piece do |position, piece|
if piece.color == @turn
return false if pseudolegal_move(position, safepos)
end
end
end
def get_pos(v)
case v.size
when 1
v[0]
when 2
Vector.new(v[0], v[1])
end
end
def execute_move(from, to)
if promotion(from, to)
self[to] = Piece.new(@turn, @promotion_piece)
else
self[to] = self[from]
end
self[from] = nil
end
end
class MoveGenerator
def initialize(board, &valid)
@board = board
if block_given?
@valid_move = valid
else
@valid_move = lambda do |from, to|
if @board.is_valid(to) and @board.legal_move(from, to)
return to
end
end
end
end
def unstalled
@fast = true
found = catch(:move_found) do
@board.each_piece do |position, piece|
if piece.color == @board.turn
can_move(position)
end
end
end
found == true
end
def generate_all
@fast = false
move_list = []
@board.each_piece do |position, piece|
if piece.color == @board.turn
move_list += can_move(position)
end
end
move_list
end
def can_move(from)
piece = @board[from]
move_list = []
return [] unless piece
case piece.type
when :king
generate_directions.each do |direction|
move = got_move(from, from + direction)
move_list << move if move
end
when :queen
generate_directions.each do |direction|
move_list += generate_slide(from, direction)
end
when :rook
[[1,0],[-1,0],[0,1],[0,-1]].each do |direction|
move_list += generate_slide(from, direction)
end
when :bishop
[[1,1],[-1,1],[1,-1],[-1,-1]].each do |direction|
move_list += generate_slide(from, direction)
end
when :knight
[[2,1],[2,-1],[-2,1],[-2,-1],[1,2],[1,-2],[-1,2],[-1,-2]].each do |jump|
move = got_move(from, from + jump)
move_list << move if move
end
when :pawn
[[0,@board.pawn_dir],[0,@board.pawn_dir*2],[1,@board.pawn_dir],[-1,@board.pawn_dir]].each
do |jump|
move = got_move(from, from + jump)
move_list << move if move
end
end
return move_list
end
private
def generate_slide(from, direction)
move_list = []
pos = from
while @board.is_valid(pos += direction) do
move = got_move(from, pos)
move_list << move if move
end
move_list
end
def generate_directions
dirs = []
(-1..1).each do |x|
(-1..1).each do |y|
dirs << [x,y] unless x == 0 and y == 0
end
end
return dirs
end
def got_move(from, to)
if move = @valid_move[from, to]
throw(:move_found, true) if @fast
move
else
false
end
end
end
module UI
def ask_move
@promotion_piece = nil
loop do
print ": "
input = gets
raise "no move" unless input
case input.chomp
when /^\s*$/
return nil
when /^(\d)(\d)\s*(\d)(\d)$/
return Vector.new($1.to_i, $2.to_i), Vector.new($3.to_i, $4.to_i)
when /^([RNBQK]?)([a-h1-8]?)(x?)([a-h])([1-8])(=[RNBQK])?[#+]?$/
piece_type = letter2piece($1)
prom = $6
to = Vector.new($4[0]-'a'[0], 8 - $5.to_i)
sp = @board.possible_starting_points(piece_type, to, $3 == 'x')
unless $2.nil? or $2 == ""
letter = $2
if letter =~ /[a-h]/
check = lambda do |possible_from|
possible_from.x == letter[0] - 'a'[0]
end
else
check = lambda do |possible_from|
possible_from.y == 8 - letter.to_i
end
end
sp.reject! do |possible_from|
not check[possible_from]
end
end
case sp.size
when 0
say "incorrect notation"
when 1
from = sp.first
else
say "ambiguous notation"
end
if from
if piece_type == :pawn and to.y == @board.rank(8)
@promotion_piece = letter2piece($5[1,1])
end
if from
return from, to
end
end
when "O-O"
pos = @board.king_starting_position
return pos, pos + [2,0]
when "O-O-O"
pos = @board.queen_starting_position
return pos, pos - [2,0]
end
end
end
def letter2piece(letter)
case letter
when 'R'
return :rook
when 'N'
return :knight
when 'B'
return :bishop
when 'Q'
return :queen
when 'K'
return :king
else
return :pawn
end
end
def ask_promotion_piece
return @promotion_piece if @promotion_piece
print "promote to (default: queen): "
case gets.chomp!
when "rook" || 'r'
return :rook
when "knight" || 'n'
return :knight
when "bishop" || 'b'
return :bishop
else
return :queen || 'q'
end
end
def say(msg)
puts msg.to_s.gsub(/_/) { ' ' }
end
def show_board
say "turn : #{@board.turn.to_s}"
(0...@board.size.y).each do |y|
(0...@board.size.x).each do |x|
piece = @board[x,y]
if piece
s = piece.type_initial
s.upcase! if (piece.color == :white)
print s, ' '
else
print ' '
end
end
print "\n"
end
print "\n"
end
end
class ChessGame
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
Jim Menard
is at http://www.io.com/~jimm/rubyquiz/quiz35/. I need to improve the board
drawing routine and make the input more tolerant. Input for each move must be
of the form used for chess game files (e.g., "f4", "Nf6", "Nxc6").
Jim
--
Jim Menard, ji...@io.com, http://www.io.com/~jimm
"An operating system is a collection of things that don't fit into a
language. There shouldn't be one."
-- Dan Ingalls
Gavin Kistner
My solution does not allow castling or en-passant. (Castling would be
far easier if you didn't have to determine if any other piece
challenged the intermediary space :p En-passant is annoying because
of the turn-based restriction.) It also does not check for checkmate.
Things I'm proud of:
* Subclassing Piece for each type to delegate the possible moves
calculation.
* Some of the DRY stuff in calculating possible moves along various
axes for everyone but the Pawn
* Some nice robustness and messages when you try to pick an invalid
piece, or send a piece somewhere it can't go. (After you pick the
piece to move, if you give it an invalid destination it tells you
what moves are legal.)
* Subclassing RuntimeError for the first time only and using it to my
advantage. (OutOfBoundsError and IllegalMoveError).
I'm actually not sure if I should be proud of the last one...is it
'good' to run code you know will throw an error and then catch that
as a way of detecting bounds, versus calculating the bounds properly?
When calculating the moves that a rook could do, for example, I moved
along a particular axis until I found another piece, adding each
square to the possible moves. However, if no pieces existed between
me and the edge of the board, I let the algorithm charge off the edge
of the board, waiting for the Move constructor to throw an
OutOfBoundsError as another way to let me know that it was time to stop.
Things I'm not so proud of:
* Sometimes I use 'a2' to access information, sometimes ['a','2'];
consequently a lot of my methods have code like:
def foo( col, row=nil )
col, row = (col.to_s+row.to_s).split('')
so that I can pass the information around as separate arguments,
one string, or an array. Tricky, but hacky.
* The pieces know what they are allowed to do on the board...but
don't know anything about check or checkmate. That's up to the Board.
Consequently, pieces think they can make a move that would result in
self-check, and list those choices among the options. The error
message when you try to make a move that would put your own king in
check is not helpful.
* I use #deep_clone with the Marshal hack to set up a scenario to
detect check without altering the current board. This feels
wrong...the board should be able to try out a move and then undo it
without having to clone itself. (I was concerned about putting pieces
back on the board afterwards.) Further, when I make the clone, I
can't the real #move method to try out the change, because that
method has all sorts of warnings that I'd have to hide. Ugly.
The trickiest part for me (that I ended up not solving) is figuring
out where the logic of the game goes. Shouldn't each piece know what
it can do? But then it needs to know about the entire board. And (for
en-passant) the recent history of moves for each piece. Ugly.
Thanks for a challenging puzzle. Having refactored some pieces twice,
it was a very useful exercise in thinking about roles and
responsibilities, and my own need to plan a little more before coding.
Paolo Capriotti
> Here is my solution.
I've found a bug. Here you can find the new version:
http://linuz.sns.it/~capriotti/ruby/rchess.rb
Paolo Capriotti
James Edward Gray II
> Here is my solution.
My own can be found at:
http://rubyquiz.com/ruby_quiz_chess.zip
I tried to go the extra mile with tests and documentation to make it
very approachable, in case others would like to use it to try part II
of this quiz...
James Edward Gray II
James Edward Gray II
> My hacked-together solution, based on Bangkok (http://
> bangkok.rubyforge.org), is at http://www.io.com/~jimm/rubyquiz/
> quiz35/. I need to improve the board drawing routine and make the
> input more tolerant. Input for each move must be of the form used
> for chess game files (e.g., "f4", "Nf6", "Nxc6").
Egad that's short!
Unfortunately, I'm having trouble running it:
$ ruby -rubygems main.rb
/chessgame.rb:9:in `play': undefined method `board=' for
#<DisplayListener:0x39e35c> (NoMethodError)
from main.rb:5
James Edward Gray II
Jim Menard
>
>
>>My hacked-together solution, based on Bangkok (http://
>>bangkok.rubyforge.org), is at http://www.io.com/~jimm/rubyquiz/
>>quiz35/. I need to improve the board drawing routine and make the
>>input more tolerant. Input for each move must be of the form used
>>for chess game files (e.g., "f4", "Nf6", "Nxc6").
>
>
> Egad that's short!
>
> Unfortunately, I'm having trouble running it:
>
> $ ruby -rubygems main.rb
> from main.rb:5
>
> James Edward Gray II
>
>
Oops. Remove the line
@listener.board = @board
from chessgame.rb. I've posted a fixed file and playchess.tar.gz file to
http://www.io.com/~jimm/rubyquiz/quiz35/. That's what I get for making a
last-minute change without any tests. (Bangkok has tests, but not this simple
playchess interface.)
James Edward Gray II
> Oops. Remove the line
You're going to wish I would shut pretty soon, but...
It's not notifying me of checkmates and looking at the code it seems
like it should. Am I missing something?
$ ruby -rubygems main.rb
BR BN BB BQ BK BB BN BR
BP BP BP BP BP BP BP BP
WP WP WP WP WP WP WP WP
WR WN WB WQ WK WB WN WR
White: e4
BR BN BB BQ BK BB BN BR
BP BP BP BP BP BP BP BP
WP
WP WP WP WP WP WP WP
WR WN WB WQ WK WB WN WR
Black: e5
BR BN BB BQ BK BB BN BR
BP BP BP BP BP BP BP
BP
WP
WP WP WP WP WP WP WP
WR WN WB WQ WK WB WN WR
White: Bc4
BR BN BB BQ BK BB BN BR
BP BP BP BP BP BP BP
BP
WB WP
WP WP WP WP WP WP WP
WR WN WB WQ WK WN WR
Black: Nc6
BR BB BQ BK BB BN BR
BP BP BP BP BP BP BP
BN
BP
WB WP
WP WP WP WP WP WP WP
WR WN WB WQ WK WN WR
White: Qf3
BR BB BQ BK BB BN BR
BP BP BP BP BP BP BP
BN
BP
WB WP
WQ
WP WP WP WP WP WP WP
WR WN WB WK WN WR
Black: d6
BR BB BQ BK BB BN BR
BP BP BP BP BP BP
BN BP
BP
WB WP
WQ
WP WP WP WP WP WP WP
WR WN WB WK WN WR
White: Qxf7
BR BB BQ BK BB BN BR
BP BP BP WQ BP BP
BN BP
BP
WB WP
WP WP WP WP WP WP WP
WR WN WB WK WN WR
Black:
James Edward Gray II
Jim Menard
> I think I'd better withdraw my solution. It isn't a solution to the quiz you
> posed. Oh, well, Only 15-20 minutes of my life wasted.
I'm sorry that I wasted *your* time, though.
James Edward Gray II
> No, I missed something. Bangkok reads pre-existing chess game
> files. Those files contain standard chess move strings that have
> modifiers that explicitly say "check" or "checkmate". Bangkok
> notifies the listener when it sees those; it does not look at the
> pieces and determine if there is a check or checkmate.
I must say, I had seen Bangkok on RubyForge before and wondered about
it. That is one unique concept you've got for a library there. It's
very interesting and I'm glad I've now had an excuse to look a little
deeper at it.
> I think I'd better withdraw my solution. It isn't a solution to the
> quiz you posed. Oh, well, Only 15-20 minutes of my life wasted.
I still found it informative and I'm glad you sent it in. It is a
good example for part II of this crazy idea of mine...
James Edward Gray II
Jim Menard
>
> It's not notifying me of checkmates and looking at the code it seems
> like it should. Am I missing something?
No, I missed something. Bangkok reads pre-existing chess game files. Those
files contain standard chess move strings that have modifiers that explicitly
say "check" or "checkmate". Bangkok notifies the listener when it sees those;
it does not look at the pieces and determine if there is a check or checkmate.
I think I'd better withdraw my solution. It isn't a solution to the quiz you
posed. Oh, well, Only 15-20 minutes of my life wasted.
Jim
Ruby Quiz
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:
@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:
#!/usr/local/bin/ruby -w
# 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:
if $0 == __FILE__
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!
James Edward Gray II
> Err... uhhh... it seems I missed the deadline.
There is no such thing. There's only James's schedule, which forces
him to write when he has time. Don't let that hinder you though.
> Oh well, here's my incomplete chess program. :)
Thanks for the submission. I enjoyed looking it over. I hope you'll
consider trying to adapt it to tomorrow's challenge...
James Edward Gray II