OSDN Git Service

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