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