shogi_server/board.rb

   1 ## $Id$
   2
   3 ## Copyright (C) 2004 NABEYA Kenichi (aka nanami@2ch)
   4 ## Copyright (C) 2007-2008 Daigo Moriwaki (daigo at debian dot org)
   5 ##
   6 ## This program is free software; you can redistribute it and/or modify
   7 ## it under the terms of the GNU General Public License as published by
   8 ## the Free Software Foundation; either version 2 of the License, or
   9 ## (at your option) any later version.
  10 ##
  11 ## This program is distributed in the hope that it will be useful,
  12 ## but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 ## MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 ## GNU General Public License for more details.
  15 ##
  16 ## You should have received a copy of the GNU General Public License
  17 ## along with this program; if not, write to the Free Software
  18 ## Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  19
  20 module ShogiServer # for a namespace
  21
  22 class Board
  23
  24   def initialize(move_count=0)
  25     @sente_hands = Array::new
  26     @gote_hands  = Array::new
  27     @history       = Hash::new(0)
  28     @sente_history = Hash::new(0)
  29     @gote_history  = Hash::new(0)
  30     @array = [[], [], [], [], [], [], [], [], [], []]
  31     @move_count = move_count
  32     @teban = nil # black => true, white => false
  33     @initial_moves = []
  34   end
  35   attr_accessor :array, :sente_hands, :gote_hands, :history, :sente_history, :gote_history, :teban
  36   attr_reader :move_count
  37
  38   # Initial moves for a Buoy game. If it is an empty array, the game is
  39   # normal with the initial setting; otherwise, the game is started after the
  40   # moves.
  41   attr_reader :initial_moves
  42
  43   def deep_copy
  44     return Marshal.load(Marshal.dump(self))
  45   end
  46
  47   def initial
  48     PieceKY::new(self, 1, 1, false)
  49     PieceKE::new(self, 2, 1, false)
  50     PieceGI::new(self, 3, 1, false)
  51     PieceKI::new(self, 4, 1, false)
  52     PieceOU::new(self, 5, 1, false)
  53     PieceKI::new(self, 6, 1, false)
  54     PieceGI::new(self, 7, 1, false)
  55     PieceKE::new(self, 8, 1, false)
  56     PieceKY::new(self, 9, 1, false)
  57     PieceKA::new(self, 2, 2, false)
  58     PieceHI::new(self, 8, 2, false)
  59     (1..9).each do |i|
  60       PieceFU::new(self, i, 3, false)
  61     end
  62
  63     PieceKY::new(self, 1, 9, true)
  64     PieceKE::new(self, 2, 9, true)
  65     PieceGI::new(self, 3, 9, true)
  66     PieceKI::new(self, 4, 9, true)
  67     PieceOU::new(self, 5, 9, true)
  68     PieceKI::new(self, 6, 9, true)
  69     PieceGI::new(self, 7, 9, true)
  70     PieceKE::new(self, 8, 9, true)
  71     PieceKY::new(self, 9, 9, true)
  72     PieceKA::new(self, 8, 8, true)
  73     PieceHI::new(self, 2, 8, true)
  74     (1..9).each do |i|
  75       PieceFU::new(self, i, 7, true)
  76     end
  77     @teban = true
  78   end
  79
  80   # Set up a board with the strs.
  81   # Failing to parse the moves raises an StandardError.
  82   # @param strs a board text
  83   #
  84   def set_from_str(strs)
  85     strs.each_line do |str|
  86       case str
  87       when /^P\d/
  88         str.sub!(/^P(.)/, '')
  89         y = $1.to_i
  90         x = 9
  91         while (str.length > 2)
  92           str.sub!(/^(...?)/, '')
  93           one = $1
  94           if (one =~ /^([\+\-])(..)/)
  95             sg = $1
  96             name = $2
  97             if (sg == "+")
  98               sente = true
  99             else
 100               sente = false
 101             end
 102             if ((x < 1) || (9 < x) || (y < 1) || (9 < y))
 103               raise "bad position #{x} #{y}"
 104             end
 105             case (name)
 106             when "FU"
 107               PieceFU::new(self, x, y, sente)
 108             when "KY"
 109               PieceKY::new(self, x, y, sente)
 110             when "KE"
 111               PieceKE::new(self, x, y, sente)
 112             when "GI"
 113               PieceGI::new(self, x, y, sente)
 114             when "KI"
 115               PieceKI::new(self, x, y, sente)
 116             when "OU"
 117               PieceOU::new(self, x, y, sente)
 118             when "KA"
 119               PieceKA::new(self, x, y, sente)
 120             when "HI"
 121               PieceHI::new(self, x, y, sente)
 122             when "TO"
 123               PieceFU::new(self, x, y, sente, true)
 124             when "NY"
 125               PieceKY::new(self, x, y, sente, true)
 126             when "NK"
 127               PieceKE::new(self, x, y, sente, true)
 128             when "NG"
 129               PieceGI::new(self, x, y, sente, true)
 130             when "UM"
 131               PieceKA::new(self, x, y, sente, true)
 132             when "RY"
 133               PieceHI::new(self, x, y, sente, true)
 134             else
 135               raise "unkown piece #{name}"
 136             end
 137           end
 138           x = x - 1
 139         end
 140       when /^P([\+\-])/
 141         sg = $1
 142         if (sg == "+")
 143           sente = true
 144         else
 145           sente = false
 146         end
 147         str.sub!(/^../, '')
 148         while (str.length > 3)
 149           str.sub!(/^..(..)/, '')
 150           name = $1
 151           case (name)
 152           when "FU"
 153             PieceFU::new(self, 0, 0, sente)
 154           when "KY"
 155             PieceKY::new(self, 0, 0, sente)
 156           when "KE"
 157             PieceKE::new(self, 0, 0, sente)
 158           when "GI"
 159             PieceGI::new(self, 0, 0, sente)
 160           when "KI"
 161             PieceKI::new(self, 0, 0, sente)
 162           when "KA"
 163             PieceKA::new(self, 0, 0, sente)
 164           when "HI"
 165             PieceHI::new(self, 0, 0, sente)
 166           else
 167             raise "unkown piece #{name}"
 168           end
 169         end # while
 170       when /^\+$/
 171         @teban = true
 172       when /^\-$/
 173         @teban = false
 174       else
 175         raise "bad line: #{str}"
 176       end # case
 177     end # do
 178   end
 179
 180   # Set up a board starting with a position after the moves.
 181   # Failing to parse the moves raises an ArgumentError.
 182   # @param moves an array of moves. ex. ["+7776FU", "-3334FU"]
 183   #
 184   def set_from_moves(moves)
 185     initial()
 186     return :normal if moves.empty?
 187     rt = nil
 188     moves.each do |move|
 189       rt = handle_one_move(move, @teban)
 190       raise ArgumentError, "bad moves: #{moves}" unless rt == :normal
 191     end
 192     @initial_moves = moves.dup
 193   end
 194
 195   def have_piece?(hands, name)
 196     piece = hands.find { |i|
 197       i.name == name
 198     }
 199     return piece
 200   end
 201
 202   def move_to(x0, y0, x1, y1, name, sente)
 203     if (sente)
 204       hands = @sente_hands
 205     else
 206       hands = @gote_hands
 207     end
 208
 209     if ((x0 == 0) || (y0 == 0))
 210       piece = have_piece?(hands, name)
 211       return :illegal if (piece == nil || ! piece.move_to?(x1, y1, name))
 212       piece.move_to(x1, y1)
 213     else
 214       if (@array[x0][y0] == nil || !@array[x0][y0].move_to?(x1, y1, name))
 215         return :illegal
 216       end
 217       if (@array[x0][y0].name != name) # promoted ?
 218         @array[x0][y0].promoted = true
 219       end
 220       if (@array[x1][y1]) # capture
 221         if (@array[x1][y1].name == "OU")
 222           return :outori        # return board update
 223         end
 224         @array[x1][y1].sente = @array[x0][y0].sente
 225         @array[x1][y1].move_to(0, 0)
 226         hands.sort! {|a, b| # TODO refactor. Move to Piece class
 227           a.name <=> b.name
 228         }
 229       end
 230       @array[x0][y0].move_to(x1, y1)
 231     end
 232     @move_count += 1
 233     @teban = @teban ? false : true
 234     return true
 235   end
 236
 237   def look_for_ou(sente)
 238     x = 1
 239     while (x <= 9)
 240       y = 1
 241       while (y <= 9)
 242         if (@array[x][y] &&
 243             (@array[x][y].name == "OU") &&
 244             (@array[x][y].sente == sente))
 245           return @array[x][y]
 246         end
 247         y = y + 1
 248       end
 249       x = x + 1
 250     end
 251     raise "can't find ou"
 252   end
 253
 254   # not checkmate, but check. sente is checked.
 255   def checkmated?(sente)        # sente is loosing
 256     ou = look_for_ou(sente)
 257     x = 1
 258     while (x <= 9)
 259       y = 1
 260       while (y <= 9)
 261         if (@array[x][y] &&
 262             (@array[x][y].sente != sente))
 263           if (@array[x][y].movable_grids.include?([ou.x, ou.y]))
 264             return true
 265           end
 266         end
 267         y = y + 1
 268       end
 269       x = x + 1
 270     end
 271     return false
 272   end
 273
 274   def uchifuzume?(sente)
 275     rival_ou = look_for_ou(! sente)   # rival's ou
 276     if (sente)                  # rival is gote
 277       if ((rival_ou.y != 9) &&
 278           (@array[rival_ou.x][rival_ou.y + 1]) &&
 279           (@array[rival_ou.x][rival_ou.y + 1].name == "FU") &&
 280           (@array[rival_ou.x][rival_ou.y + 1].sente == sente)) # uchifu true
 281         fu_x = rival_ou.x
 282         fu_y = rival_ou.y + 1
 283       else
 284         return false
 285       end
 286     else                        # gote
 287       if ((rival_ou.y != 1) &&
 288           (@array[rival_ou.x][rival_ou.y - 1]) &&
 289           (@array[rival_ou.x][rival_ou.y - 1].name == "FU") &&
 290           (@array[rival_ou.x][rival_ou.y - 1].sente == sente)) # uchifu true
 291         fu_x = rival_ou.x
 292         fu_y = rival_ou.y - 1
 293       else
 294         return false
 295       end
 296     end
 297
 298     ## case: rival_ou is moving
 299     rival_ou.movable_grids.each do |(cand_x, cand_y)|
 300       tmp_board = deep_copy
 301       s = tmp_board.move_to(rival_ou.x, rival_ou.y, cand_x, cand_y, "OU", ! sente)
 302       raise "internal error" if (s != true)
 303       if (! tmp_board.checkmated?(! sente)) # good move
 304         return false
 305       end
 306     end
 307
 308     ## case: rival is capturing fu
 309     x = 1
 310     while (x <= 9)
 311       y = 1
 312       while (y <= 9)
 313         if (@array[x][y] &&
 314             (@array[x][y].sente != sente) &&
 315             @array[x][y].movable_grids.include?([fu_x, fu_y])) # capturable
 316
 317           names = []
 318           if (@array[x][y].promoted)
 319             names << @array[x][y].promoted_name
 320           else
 321             names << @array[x][y].name
 322             if @array[x][y].promoted_name &&
 323                @array[x][y].move_to?(fu_x, fu_y, @array[x][y].promoted_name)
 324               names << @array[x][y].promoted_name
 325             end
 326           end
 327           names.map! do |name|
 328             tmp_board = deep_copy
 329             s = tmp_board.move_to(x, y, fu_x, fu_y, name, ! sente)
 330             if s == :illegal
 331               s # result
 332             else
 333               tmp_board.checkmated?(! sente) # result
 334             end
 335           end
 336           all_illegal = names.find {|a| a != :illegal}
 337           raise "internal error: legal move not found" if all_illegal == nil
 338           r = names.find {|a| a == false} # good move
 339           return false if r == false # found good move
 340         end
 341         y = y + 1
 342       end
 343       x = x + 1
 344     end
 345     return true
 346   end
 347
 348   # @[sente|gote]_history has at least one item while the player is checking the other or
 349   # the other escapes.
 350   def update_sennichite(player)
 351     str = to_s
 352     @history[str] += 1
 353     if checkmated?(!player)
 354       if (player)
 355         @sente_history["dummy"] = 1  # flag to see Sente player is checking Gote player
 356       else
 357         @gote_history["dummy"]  = 1  # flag to see Gote player is checking Sente player
 358       end
 359     else
 360       if (player)
 361         @sente_history.clear # no more continuous check
 362       else
 363         @gote_history.clear  # no more continuous check
 364       end
 365     end
 366     if @sente_history.size > 0  # possible for Sente's or Gote's turn
 367       @sente_history[str] += 1
 368     end
 369     if @gote_history.size > 0   # possible for Sente's or Gote's turn
 370       @gote_history[str] += 1
 371     end
 372   end
 373
 374   def oute_sennichite?(player)
 375     return nil unless sennichite?
 376
 377     if player
 378       # sente's turn
 379       if (@sente_history[to_s] >= 4)   # sente is checking gote
 380         return :oute_sennichite_sente_lose
 381       elsif (@gote_history[to_s] >= 3) # sente is escaping
 382         return :oute_sennichite_gote_lose
 383       else
 384         return nil # Not oute_sennichite, but sennichite
 385       end
 386     else
 387       # gote's turn
 388       if (@gote_history[to_s] >= 4)     # gote is checking sente
 389         return :oute_sennichite_gote_lose
 390       elsif (@sente_history[to_s] >= 3) # gote is escaping
 391         return :oute_sennichite_sente_lose
 392       else
 393         return nil # Not oute_sennichite, but sennichite
 394       end
 395     end
 396   end
 397
 398   def sennichite?
 399     if (@history[to_s] >= 4) # already 3 times
 400       return true
 401     end
 402     return false
 403   end
 404
 405   def good_kachi?(sente)
 406     if (checkmated?(sente))
 407       puts "'NG: Checkmating." if $DEBUG
 408       return false
 409     end
 410
 411     ou = look_for_ou(sente)
 412     if (sente && (ou.y >= 4))
 413       puts "'NG: Black's OU does not enter yet." if $DEBUG
 414       return false
 415     end
 416     if (! sente && (ou.y <= 6))
 417       puts "'NG: White's OU does not enter yet." if $DEBUG
 418       return false
 419     end
 420
 421     number = 0
 422     point = 0
 423
 424     if (sente)
 425       hands = @sente_hands
 426       r = [1, 2, 3]
 427     else
 428       hands = @gote_hands
 429       r = [7, 8, 9]
 430     end
 431     r.each do |y|
 432       x = 1
 433       while (x <= 9)
 434         if (@array[x][y] &&
 435             (@array[x][y].sente == sente) &&
 436             (@array[x][y].point > 0))
 437           point = point + @array[x][y].point
 438           number = number + 1
 439         end
 440         x = x + 1
 441       end
 442     end
 443     hands.each do |piece|
 444       point = point + piece.point
 445     end
 446
 447     if (number < 10)
 448       puts "'NG: Piece#[%d] is too small." % [number] if $DEBUG
 449       return false
 450     end
 451     if (sente)
 452       if (point < 28)
 453         puts "'NG: Black's point#[%d] is too small." % [point] if $DEBUG
 454         return false
 455       end
 456     else
 457       if (point < 27)
 458         puts "'NG: White's point#[%d] is too small." % [point] if $DEBUG
 459         return false
 460       end
 461     end
 462
 463     puts "'Good: Piece#[%d], Point[%d]." % [number, point] if $DEBUG
 464     return true
 465   end
 466
 467   # sente is nil only if tests in test_board run
 468   def handle_one_move(str, sente=nil)
 469     if (str =~ /^([\+\-])(\d)(\d)(\d)(\d)([A-Z]{2})/)
 470       sg = $1
 471       x0 = $2.to_i
 472       y0 = $3.to_i
 473       x1 = $4.to_i
 474       y1 = $5.to_i
 475       name = $6
 476     elsif (str =~ /^%KACHI/)
 477       raise ArgumentError, "sente is null", caller if sente == nil
 478       if (good_kachi?(sente))
 479         return :kachi_win
 480       else
 481         return :kachi_lose
 482       end
 483     elsif (str =~ /^%TORYO/)
 484       return :toryo
 485     else
 486       return :illegal
 487     end
 488
 489     if (((x0 == 0) || (y0 == 0)) && # source is not from hand
 490         ((x0 != 0) || (y0 != 0)))
 491       return :illegal
 492     elsif ((x1 == 0) || (y1 == 0)) # destination is out of board
 493       return :illegal
 494     end
 495
 496     if (sg == "+")
 497       sente = true if sente == nil           # deprecated
 498       return :illegal unless sente == true   # black player's move must be black
 499       hands = @sente_hands
 500     else
 501       sente = false if sente == nil          # deprecated
 502       return :illegal unless sente == false  # white player's move must be white
 503       hands = @gote_hands
 504     end
 505
 506     ## source check
 507     if ((x0 == 0) && (y0 == 0))
 508       return :illegal if (! have_piece?(hands, name))
 509     elsif (! @array[x0][y0])
 510       return :illegal           # no piece
 511     elsif (@array[x0][y0].sente != sente)
 512       return :illegal           # this is not mine
 513     elsif (@array[x0][y0].name != name)
 514       return :illegal if (@array[x0][y0].promoted_name != name) # can't promote
 515     end
 516
 517     ## destination check
 518     if (@array[x1][y1] &&
 519         (@array[x1][y1].sente == sente)) # can't capture mine
 520       return :illegal
 521     elsif ((x0 == 0) && (y0 == 0) && @array[x1][y1])
 522       return :illegal           # can't put on existing piece
 523     end
 524
 525     tmp_board = deep_copy
 526     return :illegal if (tmp_board.move_to(x0, y0, x1, y1, name, sente) == :illegal)
 527     return :oute_kaihimore if (tmp_board.checkmated?(sente))
 528     tmp_board.update_sennichite(sente)
 529     os_result = tmp_board.oute_sennichite?(sente)
 530     return os_result if os_result # :oute_sennichite_sente_lose or :oute_sennichite_gote_lose
 531     return :sennichite if tmp_board.sennichite?
 532
 533     if ((x0 == 0) && (y0 == 0) && (name == "FU") && tmp_board.uchifuzume?(sente))
 534       return :uchifuzume
 535     end
 536
 537     move_to(x0, y0, x1, y1, name, sente)
 538
 539     update_sennichite(sente)
 540     return :normal
 541   end
 542
 543   def to_s
 544     a = Array::new
 545     y = 1
 546     while (y <= 9)
 547       a.push(sprintf("P%d", y))
 548       x = 9
 549       while (x >= 1)
 550         piece = @array[x][y]
 551         if (piece)
 552           s = piece.to_s
 553         else
 554           s = " * "
 555         end
 556         a.push(s)
 557         x = x - 1
 558       end
 559       a.push(sprintf("\n"))
 560       y = y + 1
 561     end
 562     if (! sente_hands.empty?)
 563       a.push("P+")
 564       sente_hands.each do |p|
 565         a.push("00" + p.name)
 566       end
 567       a.push("\n")
 568     end
 569     if (! gote_hands.empty?)
 570       a.push("P-")
 571       gote_hands.each do |p|
 572         a.push("00" + p.name)
 573       end
 574       a.push("\n")
 575     end
 576     a.push("%s\n" % [@teban ? "+" : "-"])
 577     return a.join
 578   end
 579 end
 580
 581 end # ShogiServer