OSDN Git Service

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