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