OSDN Git Service

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