OSDN Git Service

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