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 require 'shogi_server/move'
  21
  22 module ShogiServer # for a namespace
  23
  24 class WrongMoves < ArgumentError; end
  25
  26 class Board
  27
  28   # Initial board setup.
  29   # The string ends with '+', not a line break.
  30   #
  31   INITIAL_HIRATE_POSITION = (<<-EOF).chomp
  32 P1-KY-KE-GI-KI-OU-KI-GI-KE-KY
  33 P2 * -HI *  *  *  *  * -KA *
  34 P3-FU-FU-FU-FU-FU-FU-FU-FU-FU
  35 P4 *  *  *  *  *  *  *  *  *
  36 P5 *  *  *  *  *  *  *  *  *
  37 P6 *  *  *  *  *  *  *  *  *
  38 P7+FU+FU+FU+FU+FU+FU+FU+FU+FU
  39 P8 * +KA *  *  *  *  * +HI *
  40 P9+KY+KE+GI+KI+OU+KI+GI+KE+KY
  41 +
  42 EOF
  43
  44   # Split a moves line into an array of a move string.
  45   # If it fails to parse the moves, it raises WrongMoves.
  46   # @param moves a moves line. Ex. "+776FU-3334Fu"
  47   # @return an array of a move string. Ex. ["+7776FU", "-3334FU"]
  48   #
  49   def Board.split_moves(moves)
  50     ret = []
  51
  52     rs = moves.gsub %r{[\+\-]\d{4}\w{2}} do |s|
  53            ret << s
  54            ""
  55          end
  56     raise WrongMoves, rs unless rs.empty?
  57
  58     return ret
  59   end
  60
  61
  62   def initialize(move_count=0)
  63     @sente_hands = Array::new
  64     @gote_hands  = Array::new
  65     @history       = Hash::new(0)
  66     @sente_history = Hash::new(0)
  67     @gote_history  = Hash::new(0)
  68     @array = [[], [], [], [], [], [], [], [], [], []]
  69     @move_count = move_count
  70     @teban = nil # black => true, white => false
  71     @initial_moves = []
  72     @ous = [nil, nil] # keep OU pieces of Sente and Gote
  73   end
  74   attr_accessor :array, :sente_hands, :gote_hands, :history, :sente_history, :gote_history, :teban
  75   attr_reader :move_count
  76
  77   # Initial moves for a Buoy game. If it is an empty array, the game is
  78   # normal with the initial setting; otherwise, the game is started after the
  79   # moves.
  80   attr_reader :initial_moves
  81
  82   # See if self equals rhs, including a logical board position (i.e.
  83   # not see object IDs) and sennichite stuff.
  84   #
  85   def ==(rhs)
  86     return @teban         == rhs.teban &&
  87            @move_count    == rhs.move_count &&
  88            to_s           == rhs.to_s &&
  89            @history       == rhs.history &&
  90            @sente_history == rhs.sente_history &&
  91            @gote_history  == rhs.gote_history &&
  92            @initial_moves == rhs.initial_moves
  93   end
  94
  95   def deep_copy
  96     return Marshal.load(Marshal.dump(self))
  97   end
  98
  99   def initial
 100     PieceKY::new(self, 1, 1, false)
 101     PieceKE::new(self, 2, 1, false)
 102     PieceGI::new(self, 3, 1, false)
 103     PieceKI::new(self, 4, 1, false)
 104     PieceOU::new(self, 5, 1, false)
 105     PieceKI::new(self, 6, 1, false)
 106     PieceGI::new(self, 7, 1, false)
 107     PieceKE::new(self, 8, 1, false)
 108     PieceKY::new(self, 9, 1, false)
 109     PieceKA::new(self, 2, 2, false)
 110     PieceHI::new(self, 8, 2, false)
 111     (1..9).each do |i|
 112       PieceFU::new(self, i, 3, false)
 113     end
 114
 115     PieceKY::new(self, 1, 9, true)
 116     PieceKE::new(self, 2, 9, true)
 117     PieceGI::new(self, 3, 9, true)
 118     PieceKI::new(self, 4, 9, true)
 119     PieceOU::new(self, 5, 9, true)
 120     PieceKI::new(self, 6, 9, true)
 121     PieceGI::new(self, 7, 9, true)
 122     PieceKE::new(self, 8, 9, true)
 123     PieceKY::new(self, 9, 9, true)
 124     PieceKA::new(self, 8, 8, true)
 125     PieceHI::new(self, 2, 8, true)
 126     (1..9).each do |i|
 127       PieceFU::new(self, i, 7, true)
 128     end
 129     @teban = true
 130   end
 131
 132   # Cache OU piece.
 133   # Piece#new will call back this method.
 134   #
 135   def add_ou(ou)
 136     if ou.sente
 137       @ous[0] = ou
 138     else
 139       @ous[1] = ou
 140     end
 141   end
 142
 143   # Set up a board with the strs.
 144   # Failing to parse the moves raises an StandardError.
 145   # @param strs a board text
 146   #
 147   def set_from_str(strs)
 148     strs.each_line do |str|
 149       case str
 150       when /^P\d/
 151         str.sub!(/^P(.)/, '')
 152         y = $1.to_i
 153         x = 9
 154         while (str.length > 2)
 155           str.sub!(/^(...?)/, '')
 156           one = $1
 157           if (one =~ /^([\+\-])(..)/)
 158             sg = $1
 159             name = $2
 160             if (sg == "+")
 161               sente = true
 162             else
 163               sente = false
 164             end
 165             if ((x < 1) || (9 < x) || (y < 1) || (9 < y))
 166               raise "bad position #{x} #{y}"
 167             end
 168             case (name)
 169             when "FU"
 170               PieceFU::new(self, x, y, sente)
 171             when "KY"
 172               PieceKY::new(self, x, y, sente)
 173             when "KE"
 174               PieceKE::new(self, x, y, sente)
 175             when "GI"
 176               PieceGI::new(self, x, y, sente)
 177             when "KI"
 178               PieceKI::new(self, x, y, sente)
 179             when "OU"
 180               PieceOU::new(self, x, y, sente)
 181             when "KA"
 182               PieceKA::new(self, x, y, sente)
 183             when "HI"
 184               PieceHI::new(self, x, y, sente)
 185             when "TO"
 186               PieceFU::new(self, x, y, sente, true)
 187             when "NY"
 188               PieceKY::new(self, x, y, sente, true)
 189             when "NK"
 190               PieceKE::new(self, x, y, sente, true)
 191             when "NG"
 192               PieceGI::new(self, x, y, sente, true)
 193             when "UM"
 194               PieceKA::new(self, x, y, sente, true)
 195             when "RY"
 196               PieceHI::new(self, x, y, sente, true)
 197             else
 198               raise "unkown piece #{name}"
 199             end
 200           end
 201           x = x - 1
 202         end
 203       when /^P([\+\-])/
 204         sg = $1
 205         if (sg == "+")
 206           sente = true
 207         else
 208           sente = false
 209         end
 210         str.sub!(/^../, '')
 211         while (str.length > 3)
 212           str.sub!(/^..(..)/, '')
 213           name = $1
 214           case (name)
 215           when "FU"
 216             PieceFU::new(self, 0, 0, sente)
 217           when "KY"
 218             PieceKY::new(self, 0, 0, sente)
 219           when "KE"
 220             PieceKE::new(self, 0, 0, sente)
 221           when "GI"
 222             PieceGI::new(self, 0, 0, sente)
 223           when "KI"
 224             PieceKI::new(self, 0, 0, sente)
 225           when "KA"
 226             PieceKA::new(self, 0, 0, sente)
 227           when "HI"
 228             PieceHI::new(self, 0, 0, sente)
 229           else
 230             raise "unkown piece #{name}"
 231           end
 232         end # while
 233       when /^\+$/
 234         @teban = true
 235       when /^\-$/
 236         @teban = false
 237       else
 238         raise "bad line: #{str}"
 239       end # case
 240     end # do
 241   end
 242
 243   # Set up a board starting with a position after the moves.
 244   # Failing to parse the moves raises an ArgumentError.
 245   # @param moves an array of moves. ex. ["+7776FU", "-3334FU"]
 246   #
 247   def set_from_moves(moves)
 248     initial()
 249     return :normal if moves.empty?
 250     rt = nil
 251     moves.each do |move|
 252       rt = handle_one_move(move, @teban)
 253       raise ArgumentError, "bad moves: #{moves}" unless rt == :normal
 254     end
 255     @initial_moves = moves.dup
 256   end
 257
 258   def have_piece?(hands, name)
 259     piece = hands.find { |i|
 260       i.name == name
 261     }
 262     return piece
 263   end
 264
 265   # :illegal and :outori do not change this instance (self).
 266   #
 267   def move_to(move)
 268     x0, x1, y0, y1, name, sente = move.x0, move.x1, move.y0, move.y1, move.name, move.sente
 269     if (sente)
 270       hands = @sente_hands
 271     else
 272       hands = @gote_hands
 273     end
 274
 275     if move.is_drop?
 276       piece = have_piece?(hands, name)
 277       return :illegal if (piece == nil || ! piece.move_to?(x1, y1, name))
 278       piece.move_to(x1, y1)
 279     else
 280       if (@array[x0][y0] == nil || !@array[x0][y0].move_to?(x1, y1, name))
 281         return :illegal
 282       end
 283       if (@array[x1][y1] && @array[x1][y1].name == "OU")
 284           return :outori
 285       end
 286
 287       # Change the state of this instance (self)
 288       if (@array[x0][y0].name != name && !@array[x0][y0].promoted)
 289         # the piece is promoting
 290         @array[x0][y0].promoted = true
 291         move.promotion = true
 292       end
 293       if (@array[x1][y1]) # capture
 294         move.set_captured_piece(@array[x1][y1])
 295         @array[x1][y1].sente = @array[x0][y0].sente
 296         @array[x1][y1].move_to(0, 0)
 297         hands.sort! {|a, b| # TODO refactor. Move to Piece class
 298           a.name <=> b.name
 299         }
 300       end
 301       @array[x0][y0].move_to(x1, y1)
 302     end
 303     @move_count += 1
 304     @teban = @teban ? false : true
 305     return true
 306   end
 307
 308   # Get back the previous move, which moved a name piece from [x0,y0] to
 309   # [x1, y1] with or without promotion. If the move captured
 310   # a piece, it is captured_piece, which is now in hand. The captured_piece
 311   # was promoted or unpromoted.
 312   #
 313   def move_back(move)
 314     if (move.sente)
 315       hands = @sente_hands
 316     else
 317       hands = @gote_hands
 318     end
 319
 320     piece = @array[move.x1][move.y1]
 321     if move.is_drop?
 322       piece.move_to(0, 0)
 323     else
 324       piece.move_to(move.x0, move.y0)
 325       piece.promoted = false if piece.promoted && move.promotion
 326       if move.captured_piece
 327         move.captured_piece.move_to(move.x1, move.y1)
 328         move.captured_piece.sente = move.sente ? false : true
 329         move.captured_piece.promoted = true if move.captured_piece_promoted
 330       end
 331     end
 332
 333     @move_count -= 1
 334     @teban = @teban ? false : true
 335     return true
 336   end
 337
 338   # def each_reserved_square
 339
 340   def look_for_ou(sente)
 341     if sente
 342       return @ous[0]
 343     else
 344       return @ous[1]
 345     end
 346   end
 347
 348   # See if sente is checked (i.e. loosing) or not.
 349   # Note that the method name "checkmated?" is wrong. Instead, it should be
 350   # "checked?"
 351   #
 352   def checkmated?(sente)
 353     ou = look_for_ou(sente)
 354     x = 1
 355     while (x <= 9)
 356       y = 1
 357       while (y <= 9)
 358         if (@array[x][y] &&
 359             (@array[x][y].sente != sente))
 360           if (@array[x][y].movable_grids.include?([ou.x, ou.y]))
 361             return true
 362           end
 363         end
 364         y = y + 1
 365       end
 366       x = x + 1
 367     end
 368     return false
 369   end
 370
 371   # See if sente's FU drop checkmates the opponent or not.
 372   #
 373   def uchifuzume?(sente)
 374     rival_ou = look_for_ou(! sente)   # rival's ou
 375     if (sente)                  # rival is gote
 376       if ((rival_ou.y != 9) &&
 377           (@array[rival_ou.x][rival_ou.y + 1]) &&
 378           (@array[rival_ou.x][rival_ou.y + 1].name == "FU") &&
 379           (@array[rival_ou.x][rival_ou.y + 1].sente == sente)) # uchifu true
 380         fu_x = rival_ou.x
 381         fu_y = rival_ou.y + 1
 382       else
 383         return false
 384       end
 385     else                        # gote
 386       if ((rival_ou.y != 1) &&
 387           (@array[rival_ou.x][rival_ou.y - 1]) &&
 388           (@array[rival_ou.x][rival_ou.y - 1].name == "FU") &&
 389           (@array[rival_ou.x][rival_ou.y - 1].sente == sente)) # uchifu true
 390         fu_x = rival_ou.x
 391         fu_y = rival_ou.y - 1
 392       else
 393         return false
 394       end
 395     end
 396
 397     ## case: rival_ou is moving
 398     rival_ou.movable_grids.each do |(cand_x, cand_y)|
 399       tmp_board = deep_copy
 400       s = tmp_board.move_to(Move.new(rival_ou.x, rival_ou.y, cand_x, cand_y, "OU", ! sente))
 401       raise "internal error" if (s != true)
 402       if (! tmp_board.checkmated?(! sente)) # good move
 403         return false
 404       end
 405     end
 406
 407     ## case: rival is capturing fu
 408     x = 1
 409     while (x <= 9)
 410       y = 1
 411       while (y <= 9)
 412         if (@array[x][y] &&
 413             (@array[x][y].sente != sente) &&
 414             @array[x][y].movable_grids.include?([fu_x, fu_y])) # capturable
 415
 416           names = []
 417           if (@array[x][y].promoted)
 418             names << @array[x][y].promoted_name
 419           else
 420             names << @array[x][y].name
 421             if @array[x][y].promoted_name &&
 422                @array[x][y].move_to?(fu_x, fu_y, @array[x][y].promoted_name)
 423               names << @array[x][y].promoted_name
 424             end
 425           end
 426           names.map! do |name|
 427             tmp_board = deep_copy
 428             s = tmp_board.move_to(Move.new(x, y, fu_x, fu_y, name, ! sente))
 429             if s == :illegal
 430               s # result
 431             else
 432               tmp_board.checkmated?(! sente) # result
 433             end
 434           end
 435           all_illegal = names.find {|a| a != :illegal}
 436           raise "internal error: legal move not found" if all_illegal == nil
 437           r = names.find {|a| a == false} # good move
 438           return false if r == false # found good move
 439         end
 440         y = y + 1
 441       end
 442       x = x + 1
 443     end
 444     return true
 445   end
 446
 447   # @[sente|gote]_history has at least one item while the player is checking the other or
 448   # the other escapes.
 449   def update_sennichite(player)
 450     str = to_s
 451     @history[str] += 1
 452     if checkmated?(!player)
 453       if (player)
 454         @sente_history["dummy"] = 1  # flag to see Sente player is checking Gote player
 455       else
 456         @gote_history["dummy"]  = 1  # flag to see Gote player is checking Sente player
 457       end
 458     else
 459       if (player)
 460         @sente_history.clear # no more continuous check
 461       else
 462         @gote_history.clear  # no more continuous check
 463       end
 464     end
 465     if @sente_history.size > 0  # possible for Sente's or Gote's turn
 466       @sente_history[str] += 1
 467     end
 468     if @gote_history.size > 0   # possible for Sente's or Gote's turn
 469       @gote_history[str] += 1
 470     end
 471   end
 472
 473   # Deep-copy sennichite stuff, which will later be available to restore.
 474   #
 475   def dup_sennichite_stuff
 476     return [@history.dup, @sente_history.dup, @gote_history.dup]
 477   end
 478
 479   # Restore sennihite stuff.
 480   #
 481   def restore_sennichite_stuff(history, sente_history, gote_history)
 482     @history, @sente_history, @gote_history = history, sente_history, gote_history
 483   end
 484
 485   def oute_sennichite?(player)
 486     return nil unless sennichite?
 487
 488     if player
 489       # sente's turn
 490       if (@sente_history[to_s] >= 4)   # sente is checking gote
 491         return :oute_sennichite_sente_lose
 492       elsif (@gote_history[to_s] >= 3) # sente is escaping
 493         return :oute_sennichite_gote_lose
 494       else
 495         return nil # Not oute_sennichite, but sennichite
 496       end
 497     else
 498       # gote's turn
 499       if (@gote_history[to_s] >= 4)     # gote is checking sente
 500         return :oute_sennichite_gote_lose
 501       elsif (@sente_history[to_s] >= 3) # gote is escaping
 502         return :oute_sennichite_sente_lose
 503       else
 504         return nil # Not oute_sennichite, but sennichite
 505       end
 506     end
 507   end
 508
 509   def sennichite?
 510     if (@history[to_s] >= 4) # already 3 times
 511       return true
 512     end
 513     return false
 514   end
 515
 516   def good_kachi?(sente)
 517     if (checkmated?(sente))
 518       puts "'NG: Checkmating." if $DEBUG
 519       return false
 520     end
 521
 522     ou = look_for_ou(sente)
 523     if (sente && (ou.y >= 4))
 524       puts "'NG: Black's OU does not enter yet." if $DEBUG
 525       return false
 526     end
 527     if (! sente && (ou.y <= 6))
 528       puts "'NG: White's OU does not enter yet." if $DEBUG
 529       return false
 530     end
 531
 532     number = 0
 533     point = 0
 534
 535     if (sente)
 536       hands = @sente_hands
 537       r = [1, 2, 3]
 538     else
 539       hands = @gote_hands
 540       r = [7, 8, 9]
 541     end
 542     r.each do |y|
 543       x = 1
 544       while (x <= 9)
 545         if (@array[x][y] &&
 546             (@array[x][y].sente == sente) &&
 547             (@array[x][y].point > 0))
 548           point = point + @array[x][y].point
 549           number = number + 1
 550         end
 551         x = x + 1
 552       end
 553     end
 554     hands.each do |piece|
 555       point = point + piece.point
 556     end
 557
 558     if (number < 10)
 559       puts "'NG: Piece#[%d] is too small." % [number] if $DEBUG
 560       return false
 561     end
 562     if (sente)
 563       if (point < 28)
 564         puts "'NG: Black's point#[%d] is too small." % [point] if $DEBUG
 565         return false
 566       end
 567     else
 568       if (point < 27)
 569         puts "'NG: White's point#[%d] is too small." % [point] if $DEBUG
 570         return false
 571       end
 572     end
 573
 574     puts "'Good: Piece#[%d], Point[%d]." % [number, point] if $DEBUG
 575     return true
 576   end
 577
 578   # sente is nil only if tests in test_board run
 579   # @return
 580   #   - :normal
 581   #   - :toryo
 582   #   - :kachi_win
 583   #   - :kachi_lose
 584   #   - :sennichite
 585   #   - :oute_sennichite_sente_lose
 586   #   - :oute_sennichite_gote_lose
 587   #   - :illegal
 588   #   - :uchifuzume
 589   #   - :oute_kaihimore
 590   #   - (:outori will not be returned)
 591   #
 592   def handle_one_move(str, sente=nil)
 593     if (str =~ /^([\+\-])(\d)(\d)(\d)(\d)([A-Z]{2})/)
 594       sg = $1
 595       x0 = $2.to_i
 596       y0 = $3.to_i
 597       x1 = $4.to_i
 598       y1 = $5.to_i
 599       name = $6
 600     elsif (str =~ /^%KACHI/)
 601       raise ArgumentError, "sente is null", caller if sente == nil
 602       if (good_kachi?(sente))
 603         return :kachi_win
 604       else
 605         return :kachi_lose
 606       end
 607     elsif (str =~ /^%TORYO/)
 608       return :toryo
 609     else
 610       return :illegal
 611     end
 612
 613     if (((x0 == 0) || (y0 == 0)) && # source is not from hand
 614         ((x0 != 0) || (y0 != 0)))
 615       return :illegal
 616     elsif ((x1 == 0) || (y1 == 0)) # destination is out of board
 617       return :illegal
 618     end
 619
 620     if (sg == "+")
 621       sente = true if sente == nil           # deprecated
 622       return :illegal unless sente == true   # black player's move must be black
 623       hands = @sente_hands
 624     else
 625       sente = false if sente == nil          # deprecated
 626       return :illegal unless sente == false  # white player's move must be white
 627       hands = @gote_hands
 628     end
 629
 630     ## source check
 631     if ((x0 == 0) && (y0 == 0))
 632       return :illegal if (! have_piece?(hands, name))
 633     elsif (! @array[x0][y0])
 634       return :illegal           # no piece
 635     elsif (@array[x0][y0].sente != sente)
 636       return :illegal           # this is not mine
 637     elsif (@array[x0][y0].name != name)
 638       return :illegal if (@array[x0][y0].promoted_name != name) # can't promote
 639     end
 640
 641     ## destination check
 642     if (@array[x1][y1] &&
 643         (@array[x1][y1].sente == sente)) # can't capture mine
 644       return :illegal
 645     elsif ((x0 == 0) && (y0 == 0) && @array[x1][y1])
 646       return :illegal           # can't put on existing piece
 647     end
 648
 649     move = Move.new(x0, y0, x1, y1, name, sente)
 650     result = move_to(move)
 651     if (result == :illegal)
 652       # self is unchanged
 653       return :illegal
 654     end
 655     if (checkmated?(sente))
 656       move_back(move)
 657       return :oute_kaihimore
 658     end
 659     if ((x0 == 0) && (y0 == 0) && (name == "FU") && uchifuzume?(sente))
 660       move_back(move)
 661       return :uchifuzume
 662     end
 663
 664     sennichite_stuff = dup_sennichite_stuff
 665     update_sennichite(sente)
 666     os_result = oute_sennichite?(sente)
 667     if os_result # :oute_sennichite_sente_lose or :oute_sennichite_gote_lose
 668       move_back(move)
 669       restore_sennichite_stuff(*sennichite_stuff)
 670       return os_result
 671     end
 672     if sennichite?
 673       move_back(move)
 674       restore_sennichite_stuff(*sennichite_stuff)
 675       return :sennichite
 676     end
 677
 678     return :normal
 679   end
 680
 681   # Return a CSA-styled string notation of the current position.
 682   #
 683   def to_s
 684     a = Array::new
 685     y = 1
 686     while (y <= 9)
 687       a.push(sprintf("P%d", y))
 688       x = 9
 689       while (x >= 1)
 690         piece = @array[x][y]
 691         if (piece)
 692           s = piece.to_s
 693         else
 694           s = " * "
 695         end
 696         a.push(s)
 697         x = x - 1
 698       end
 699       a.push(sprintf("\n"))
 700       y = y + 1
 701     end
 702     if (! sente_hands.empty?)
 703       a.push("P+")
 704       sente_hands.each do |p|
 705         a.push("00" + p.name)
 706       end
 707       a.push("\n")
 708     end
 709     if (! gote_hands.empty?)
 710       a.push("P-")
 711       gote_hands.each do |p|
 712         a.push("00" + p.name)
 713       end
 714       a.push("\n")
 715     end
 716     a.push("%s\n" % [@teban ? "+" : "-"])
 717     return a.join
 718   end
 719
 720   # Return a CSA-styled string notation of the initial position.
 721   #
 722   def initial_string
 723     tmp_board = self.class.new
 724     tmp_board.initial
 725     return tmp_board.to_s
 726   end
 727 end
 728
 729 end # ShogiServer