Class: RubyKnight::Board

Inherits:
Object
  • Object
show all
Defined in:
lib/rubyknight.rb,
lib/rubyknight/generator.rb

Overview

A Chess Board and State

Defined Under Namespace

Classes: Event, History

Constant Summary

ENPASSANT =
14
LAST_BOARD =
CAN_CASTLE = 15
SYMBOLS =
[ 'P','R','B','N','Q','K',
'p','r','b','n','q','k']

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initializeBoard



39
40
41
# File 'lib/rubyknight.rb', line 39

def initialize
  setup_start
end

Instance Attribute Details

#BLACKObject (readonly)

Returns the value of attribute BLACK



25
26
27
# File 'lib/rubyknight.rb', line 25

def BLACK
  @BLACK
end

#historyObject (readonly)

Returns the value of attribute history



25
26
27
# File 'lib/rubyknight.rb', line 25

def history
  @history
end

#to_playObject (readonly)

Returns the value of attribute to_play



25
26
27
# File 'lib/rubyknight.rb', line 25

def to_play
  @to_play
end

#WHITEObject (readonly)

Returns the value of attribute WHITE



25
26
27
# File 'lib/rubyknight.rb', line 25

def WHITE
  @WHITE
end

Class Method Details

.coord_to_position(coord) ⇒ Object



132
133
134
135
136
137
138
139
140
141
# File 'lib/rubyknight.rb', line 132

def Board.coord_to_position coord
  a, zero = 'a0'.unpack('cc')

  file = coord[0].getbyte(0)
  rank = coord[1].getbyte(0)

  pos = ((8 - (rank - zero)) * 8) +\
        (file - a)

end

.position_to_coord(position) ⇒ Object



143
144
145
146
147
# File 'lib/rubyknight.rb', line 143

def Board.position_to_coord position
  file = position % 8
  rank = (8 - (position - file) / 8)
  "#{(file + 97).chr}#{rank}"
end

Instance Method Details

#_undoObject



65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
# File 'lib/rubyknight.rb', line 65

def _undo
  evt = @history.pop
  return unless evt
  place_piece evt.piece, evt.orig

  if evt.promotion then unplace_piece evt.promotion, evt.dest
  else unplace_piece evt.piece, evt.dest end

  if evt.capture then place_piece evt.capture, evt.dest end

  if last = @history.last
    mark_enpassant last.piece, last.orig, last.dest
  else
    mark_enpassant nil,  nil, nil
  end

  # handle castling
  @bitboards[CAN_CASTLE] = evt.can_castle
  # are we castling?
  if (evt.piece == WKING or evt.piece == BKING) and
     (evt.dest - evt.orig).abs == 2
    # yes, we are
    case evt.dest
      when 62
        move_piece WROOK, 61, 63  
      when 58
        move_piece WROOK, 59, 56  
      when 2
        move_piece BROOK, 3, 0  
      when 6
        move_piece BROOK, 5, 7
    end
  end

  @to_play = if @to_play==WHITE then BLACK
             else WHITE end
end

#all_board_for(piece) ⇒ Object



212
213
214
# File 'lib/rubyknight.rb', line 212

def all_board_for piece
  12 + (is_white(piece) ? 0 : 1)
end

#bits_to_positions(bits) ⇒ Object



321
322
323
# File 'lib/rubyknight.rb', line 321

def bits_to_positions bits
  (0..63).select {|i| 1<<i & bits !=0}
end

#can_castle(color, side) ⇒ Object



333
334
335
# File 'lib/rubyknight.rb', line 333

def can_castle color, side
  @bitboards[CAN_CASTLE] & (1 << ((color * 2)+side)) > 0
end

#cnotation_move(cnot) ⇒ Object

Make a move in coordinate notation, ex. e2e4



150
151
152
153
154
# File 'lib/rubyknight.rb', line 150

def cnotation_move cnot
  start, dest, promotion = cnotation_to_bits cnot
  raise IllegalMoveException, "Unreadable move" unless start
  move start, dest, promotion
end

#cnotation_to_bits(cnot) ⇒ Object



156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
# File 'lib/rubyknight.rb', line 156

def cnotation_to_bits cnot
  if cnot =~ /([a-h][1-8])([a-h][1-8])([qrbnkp]{0,1})/
    unless $3 == "" 
      promotion = if @to_play == WHITE then 0
                  else 6 end
      promotion += 
        case $3
          when 'q' then WQUEEN
          when 'p' then WPAWN
          when 'r' then WROOK
          when 'b' then WBISHOP
          when 'n' then WKNIGHT
          else
            return false
        end
    else promotion = false end
    [ Board.coord_to_position( $1), Board.coord_to_position( $2),
      promotion]    
  else
    false
  end
end

#different_colors(white, piece) ⇒ Object



105
106
107
108
# File 'lib/rubyknight/generator.rb', line 105

def different_colors white, piece
  (white and !is_white piece) or
  (!white and is_white piece)
end

#dumpObject

Dump the board state to a string



49
50
51
52
53
54
55
56
# File 'lib/rubyknight.rb', line 49

def dump
  @bitboards[@bitboards.size] = @history
  @bitboards[@bitboards.size] = @to_play
  ret = Marshal.dump(@bitboards)
  @bitboards.delete_at(@bitboards.size-1)
  @bitboards.delete_at(@bitboards.size-1)
  ret
end

#gen_bishop_moves(white) ⇒ Object



174
175
176
177
178
179
180
181
# File 'lib/rubyknight/generator.rb', line 174

def gen_bishop_moves white
  moves = []
  bishops = @bitboards[white ? WBISHOP : BBISHOP]
  bits_to_positions(bishops).each do |r|
    moves += gen_bishop_type_moves( white, r)
  end
  moves
end

#gen_bishop_type_moves(white, piece, start_limit = 8) ⇒ Object



146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
# File 'lib/rubyknight/generator.rb', line 146

def gen_bishop_type_moves white, piece, start_limit = 8
  moves = []
  [-9,-7,7,9].each do |inc|
    limit = start_limit 
    trying = piece + inc
    rank = trying / 8
    lastrank = piece / 8
    while limit > 0 and
          trying >= 0 and trying <= 63 and
          (lastrank - rank).abs == 1 do
      target = whats_at trying
      if !target
        moves << [piece, trying]
      elsif different_colors( white, target)
        moves << [piece, trying]
        break
      else
        break
      end
      lastrank = rank
      trying += inc
      rank = trying / 8
      limit -= 1
    end
  end
  moves
end

#gen_castle_moves(white, king) ⇒ Object



206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
# File 'lib/rubyknight/generator.rb', line 206

def gen_castle_moves white, king
  color = white ? WHITE : BLACK
  goodcastles = []
  # kingside
  if can_castle color, KINGSIDE
    test = if white then [60,61,62]
           else [4,5,6] end
    if !whats_at(test[1]) and !whats_at(test[2])
      left = prune_king_revealers(@to_play,
                 test.map {|dest| [test[0], dest]})
      if left.size == 3 
        goodcastles << [test[0],test[2]] 
      end
    end
  end
  # queenside
  if can_castle color, QUEENSIDE
    test = if white then [60,59,58]
           else [4,3,2] end
    if !whats_at(test[1]) and !whats_at(test[2])
      left = prune_king_revealers(@to_play,
                 test.map {|dest| [test[0], dest]})
      if left.size == 3 
        goodcastles << [test[0],test[2]] 
      end
    end
  end
  goodcastles
end

#gen_king_moves(white) ⇒ Object

TODO: how much time is wasted with the each? We'll never have

multiple kings, will we?


195
196
197
198
199
200
201
202
203
204
# File 'lib/rubyknight/generator.rb', line 195

def gen_king_moves white
  moves = []
  kings = @bitboards[white ? WKING : BKING]
  bits_to_positions(kings).each do |king|
    moves += gen_rook_type_moves( white, king, 1)
    moves += gen_bishop_type_moves( white, king, 1)
    moves += gen_castle_moves( white, king)
  end
  moves
end

#gen_knight_moves(white) ⇒ Object



236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
# File 'lib/rubyknight/generator.rb', line 236

def gen_knight_moves white
  moves = []
  knights = @bitboards[white ? WKNIGHT : BKNIGHT]
  bits_to_positions(knights).each do |k|
    [-17, -15, -10, -6, 6, 10, 15, 17].each do |m|
      target = k+m
      if target >= 0 and target <= 63 and
         ((target % 8) - (k % 8)).abs < 3
        capture = whats_at target
        if !capture or different_colors(white, capture)
           moves << [k, target]
        end
      end
    end
  end
  moves
end


7
8
9
10
11
12
# File 'lib/rubyknight/generator.rb', line 7

def gen_legal_moves
  moves = nil
  time_it("gen_moves"){ moves = gen_moves(@to_play)} 
  time_it("legal filtering"){ moves = prune_king_revealers(@to_play,moves)}
  moves
end

#gen_moves(player) ⇒ Object



95
96
97
98
99
100
101
102
103
# File 'lib/rubyknight/generator.rb', line 95

def gen_moves player
  white = player==WHITE
  time_it("gen_pawn") {   gen_pawn_moves(white)} +
  time_it("gen_knight") { gen_knight_moves(white)} +
  time_it("gen_rook") {   gen_rook_moves(white)} +
  time_it("gen_bishop") { gen_bishop_moves(white)} +
  time_it("gen_king") {   gen_king_moves(white)} +
  time_it("gen_queen") {  gen_queen_moves(white)}
end

#gen_pawn_moves(white) ⇒ Object



254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
# File 'lib/rubyknight/generator.rb', line 254

def gen_pawn_moves white
  pawns = @bitboards[white ? WPAWN : BPAWN]
  if white
    in_front_int = -8
    second_rank_high = 56
    second_rank_low = 47
    two_away_int = -16
    attack_left = -9
    attack_right = -7
    promote_low = -1
    promote_high = 8
    promotes = [WROOK, WQUEEN, WKNIGHT, WBISHOP]
  else
    in_front_int = 8
    second_rank_high = 16
    second_rank_low = 7
    two_away_int = 16
    attack_left = 7
    attack_right = 9
    promote_low = 55
    promote_high = 64
    promotes = [BROOK, BQUEEN, BKNIGHT, BBISHOP]
  end
  do_pawn = Proc.new do |p|
    possible = []
    in_front = whats_at( p + in_front_int)
    #single step
    if  !in_front
      in_front_pos = p + in_front_int
      possible << in_front_pos
      if in_front_pos > promote_low and in_front_pos < promote_high
        promotes.each { |piece| possible << [in_front_pos, piece] }
      end
    end
    #double jump
    if p < second_rank_high and p > second_rank_low and !in_front and
       !whats_at( p + two_away_int)
      possible << ( p + two_away_int)
    end
    #captures
    unless p % 8 == 0 # we're in the a file
      ptarget = whats_at( p + attack_left)
      if ptarget and different_colors(white, ptarget)
        possible << ( p + attack_left)
      end
    end
    unless p % 8 == 7 # we're in the h file
      ptarget = whats_at( p + attack_right)
      if ptarget and different_colors(white, ptarget)
        possible << ( p + attack_right)
      end
    end
    #check en-passat
    if @bitboards[ENPASSANT] != 0 
      passant = bits_to_positions( @bitboards[ENPASSANT]).first 
      if (p + attack_right) == passant or (p + attack_left) == passant
        possible << passant
      end
    end
    possible.collect {|i| [p, *i]}
  end
  moves = []
  bits_to_positions(pawns).each do |p|
    moves += do_pawn.call(p)
  end
  moves
end

#gen_queen_moves(white) ⇒ Object



183
184
185
186
187
188
189
190
191
# File 'lib/rubyknight/generator.rb', line 183

def gen_queen_moves white
  moves = []
  queens = @bitboards[white ? WQUEEN : BQUEEN]
  bits_to_positions(queens).each do |r|
    moves += gen_rook_type_moves(white, r)
    moves += gen_bishop_type_moves( white, r)
  end
  moves
end

#gen_rook_moves(white) ⇒ Object



137
138
139
140
141
142
143
144
# File 'lib/rubyknight/generator.rb', line 137

def gen_rook_moves white
  moves = []
  rooks = @bitboards[ white ? WROOK : BROOK]
  bits_to_positions(rooks).each do |r|
    moves += gen_rook_type_moves( white, r)
  end
  moves
end

#gen_rook_type_moves(white, piece, start_limit = 8) ⇒ Object



110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
# File 'lib/rubyknight/generator.rb', line 110

def gen_rook_type_moves white, piece, start_limit = 8
  moves = []
  rank = piece / 8
  file = piece % 8
  [-8,-1,1,8].each do |inc|
    limit = start_limit 
    trying = piece + inc
    while limit > 0 and
            trying >= 0 and trying <= 63 and
          (rank == (trying / 8) or
         file == (trying % 8)) do
      target = whats_at trying
      if !target
        moves << [piece, trying]
      elsif different_colors( white, target)
        moves << [piece, trying]
        break
      else
        break
      end
      trying += inc
      limit -= 1
    end
  end
  moves
end

#is_white(piece) ⇒ Object



237
238
239
# File 'lib/rubyknight.rb', line 237

def is_white piece
  piece <= WKING
end

#load(dmp) ⇒ Object

Load the board state from a string



59
60
61
62
63
# File 'lib/rubyknight.rb', line 59

def load dmp
  @bitboards = Marshal.load( dmp)
  @to_play = @bitboards.pop
  @history = @bitboards.pop
end

#mark_enpassant(last_piece, last_orig, last_dest) ⇒ Object



311
312
313
314
315
316
317
318
319
# File 'lib/rubyknight.rb', line 311

def mark_enpassant last_piece, last_orig, last_dest
  if last_piece == WPAWN and last_orig > 47 and last_orig < 56 and
    @bitboards[ENPASSANT] = ( 1 << last_orig-8)
  elsif last_piece == BPAWN and last_orig > 7 and last_orig < 16 and
    @bitboards[ENPASSANT] = ( 1 << last_orig+8)
  else
    @bitboards[ENPASSANT] = 0
  end
end

#move(orig, dest, promotion = nil, verify_legality = true) ⇒ Object



241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
# File 'lib/rubyknight.rb', line 241

def move orig, dest, promotion=nil, verify_legality = true
  piece = whats_at(orig)

  # Check Legality
   # Your piece?
  unless piece and 
       ((is_white(piece) and @to_play == WHITE) or
        (!is_white(piece) and @to_play == BLACK))
    raise IllegalMoveException, "Not your piece"
  end

  if verify_legality
    legal_moves = gen_legal_moves
    unless legal_moves.include? [orig, dest] or
              legal_moves.include? [orig, dest, promotion]
      raise IllegalMoveException, "Invalid move"
    end
  end
  
  captured = whats_at(dest)
  unplace_piece captured, dest if captured
  move_piece piece, orig, dest

  # handle castling
  # are we castling?
  if (piece == WKING or piece == BKING) and
     (dest - orig).abs == 2
    # yes, we are
    case dest
      when 62
        move_piece WROOK, 63, 61  
      when 58
        move_piece WROOK, 56, 59  
      when 2
        move_piece BROOK, 0, 3  
      when 6
        move_piece BROOK, 7, 5
    end
  end


  # mark no-longer-possible castles
  can_castle_was = @bitboards[CAN_CASTLE]
  if piece == WKING 
    @bitboards[CAN_CASTLE] &= ~(1|2)
  elsif piece == WROOK and orig == 56
    @bitboards[CAN_CASTLE] &= ~(1)
  elsif piece == WROOK and orig == 63
    @bitboards[CAN_CASTLE] &= ~(2)
  elsif piece == BKING
    @bitboards[CAN_CASTLE] &= ~(4|8)
  elsif piece == BROOK and orig == 0
    @bitboards[CAN_CASTLE] &= ~(4)
  elsif piece == BROOK and orig == 7
    @bitboards[CAN_CASTLE] &= ~(8)
  end

  if promotion
    unplace_piece piece, dest 
    place_piece promotion, dest
  end  

  mark_enpassant piece, orig, dest

  @history << Event.new(piece, orig, dest, captured, 
                        promotion, can_castle_was)
  @to_play = if @to_play==WHITE then BLACK
             else WHITE end
end

#move_piece(piece, orig, dest) ⇒ Object



232
233
234
235
# File 'lib/rubyknight.rb', line 232

def move_piece piece, orig, dest
  unplace_piece piece, orig  
  place_piece piece, dest
end

#num_pieces(piece) ⇒ Object



329
330
331
# File 'lib/rubyknight.rb', line 329

def num_pieces piece
  bits_to_positions(@bitboards[piece]).size
end

#piece_positions(piece) ⇒ Object



325
326
327
# File 'lib/rubyknight.rb', line 325

def piece_positions piece
  bits_to_positions(@bitboards[piece])
end

#place_piece(piece, *positions) ⇒ Object



216
217
218
219
220
221
222
# File 'lib/rubyknight.rb', line 216

def place_piece piece, *positions
  positions.each do |position|
    position = (1 << position)
    @bitboards[piece] |= position
    @bitboards[all_board_for(piece)] |= position
  end
end

#prune_king_revealers(player, moves) ⇒ Object

TODO: I am so slow, that I should die, probably in gen_moves



15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
# File 'lib/rubyknight/generator.rb', line 15

def prune_king_revealers player, moves
  kpiece = player==WHITE ? WKING : BKING
  moves.select do |to_try|
    move to_try[0], to_try[1], to_try[2], false
    next_moves = gen_moves @to_play
    king, = bits_to_positions(@bitboards[kpiece])
    ret = true
    next_moves.each do |m|
      if m[1] == king
        ret = false   
        break
      end
    end
    undo 1
    ret
  end
end

#prune_king_revealers_old(player, moves) ⇒ Object

broken?



34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
# File 'lib/rubyknight/generator.rb', line 34

def prune_king_revealers_old player, moves
  kpiece = player==WHITE ? WKING : BKING
  piecemod = player==WHITE ? BPAWN : 0
  moves.select do |to_try|
    move to_try[0], to_try[1], to_try[2], false
    king, = bits_to_positions(@bitboards[kpiece])
    dead_king = false
    rank = king / 8
    file = king % 8
    #check up and down for R or Q
    [-8,-1,1,8].each do |inc|
      limit = 8
      trying = king + inc
      while !dead_king and limit > 0 and
             trying >= 0 and trying <= 63 and
            (rank == (trying / 8) or
           file == (trying % 8)) do
        target = whats_at trying
        if target
           if (target == (WROOK+piecemod) or
               target == (WQUEEN+piecemod))
            dead_king = true
           end
           limit = 0
        else
          trying += inc
          limit -= 1
        end
      end
    end unless dead_king
    #check diagonals for Q, B
    [-9,-7,7,9].each do |inc|
      limit = 8
      trying = king + inc
      rank = trying / 8
      lastrank = king / 8
      while !dead_king and limit > 0 and
            trying >= 0 and trying <= 63 and
            (lastrank - rank).abs == 1 do
        target = whats_at trying
        if target
          if (target == (WBISHOP+piecemod) or
              target == (WQUEEN+piecemod))
            dead_king = true
          end
          limit = 0
        else
          lastrank = rank
          trying += inc
          rank = trying / 8
          limit -= 1
        end
      end
    end unless dead_king
    #check 2 P launch zones
    #check 8 N attack spots
    undo 1
    !dead_king
  end
end

#setup_startObject

Set the boards to the initial state



109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
# File 'lib/rubyknight.rb', line 109

def setup_start
  @to_play = WHITE
  @bitboards = Array.new LAST_BOARD+1, 0
  @bitboards[CAN_CASTLE] = 0x000F # 1111

  @history = History.new
  
  place_piece WPAWN, *(48..55).to_a
  place_piece WROOK, 56, 63
  place_piece WKNIGHT, 57, 62
  place_piece WBISHOP, 58, 61
  place_piece WQUEEN, 59
  place_piece WKING, 60

  place_piece BPAWN, *(8..15).to_a
  place_piece BROOK, 0, 7
  place_piece BKNIGHT, 1, 6
  place_piece BBISHOP, 2, 5
  place_piece BQUEEN, 3
  place_piece BKING, 4

end

#to_sObject

get a simple board notation



201
202
203
204
205
206
207
208
209
210
# File 'lib/rubyknight.rb', line 201

def to_s
  out = ""
  (0..63).each do |position|
    somethingthere = whats_at position
    if somethingthere then out << SYMBOLS[somethingthere]
    else out << '.' end
    out << "\n" if (position+1) % 8 == 0
  end
  out
end

#undo(num = 1) ⇒ Object

Roll back the last move, specify two to roll back a whole player



104
105
106
# File 'lib/rubyknight.rb', line 104

def undo num = 1
  num.times { _undo}
end

#unplace_piece(piece, *positions) ⇒ Object



224
225
226
227
228
229
230
# File 'lib/rubyknight.rb', line 224

def unplace_piece piece, *positions
  positions.each do |position|
    position = ~(1 << position)
    @bitboards[piece] &= position
    @bitboards[all_board_for(piece)] &= position
  end
end

#whats_at(position) ⇒ Object

find out the piece at a given location



180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
# File 'lib/rubyknight.rb', line 180

def whats_at position
  positionbit = (1 << position)
  if @bitboards[WALL] & positionbit > 0
    range = WPAWN..WKING
  elsif @bitboards[BALL] & positionbit > 0
    range = BPAWN..BKING
  else 
    return false
  end

  somethingthere = false
  range.each do |piece|    
    if (@bitboards[piece] & positionbit) > 0
      somethingthere = piece
      break 
    end
  end
  somethingthere
end

#white_to_play?Boolean

Is it white's turn?



44
45
46
# File 'lib/rubyknight.rb', line 44

def white_to_play?
  @to_play == WHITE  
end