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