OSDN Git Service

Backported a5c94012656902e73e00f46e7a4c7004b24d4578: test/TC_logger.rb depeneded...
[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-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_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   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   # Return a CSA-styled string notation of the current position.
679   #
680   def to_s
681     a = Array::new
682     y = 1
683     while (y <= 9)
684       a.push(sprintf("P%d", y))
685       x = 9
686       while (x >= 1)
687         piece = @array[x][y]
688         if (piece)
689           s = piece.to_s
690         else
691           s = " * "
692         end
693         a.push(s)
694         x = x - 1
695       end
696       a.push(sprintf("\n"))
697       y = y + 1
698     end
699     if (! sente_hands.empty?)
700       a.push("P+")
701       sente_hands.each do |p|
702         a.push("00" + p.name)
703       end
704       a.push("\n")
705     end
706     if (! gote_hands.empty?)
707       a.push("P-")
708       gote_hands.each do |p|
709         a.push("00" + p.name)
710       end
711       a.push("\n")
712     end
713     a.push("%s\n" % [@teban ? "+" : "-"])
714     return a.join
715   end
716
717   # Return a CSA-styled string notation of the initial position.
718   #
719   def initial_string
720     tmp_board = self.class.new
721     tmp_board.initial
722     return tmp_board.to_s
723   end
724 end
725
726 end # ShogiServer