3 # Library to support Trap the Cap play
8 # This program is free software: you can redistribute it and/or modify
9 # it under the terms of the GNU General Public License as published by
10 # the Free Software Foundation, either version 3 of the License, or
11 # (at your option) any later version.
13 # This program is distributed in the hope that it will be useful,
14 # but WITHOUT ANY WARRANTY; without even the implied warranty of
15 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 # GNU General Public License for more details.
18 # You should have received a copy of the GNU General Public License
19 # along with this program. If not, see <http://www.gnu.org/licenses/>.
22 # Version 1.1:: 07 Sep 2007
23 # * Changed format for showing moves via bases.
24 # * Raise error when moving via base without captured pieces
25 # * Raise error when moving onto a safe space with 3 or more
26 # pieces already there
27 # Version 1.2:: 10 Sep 2007
28 # * Incorporated changes in move legality above into
30 # Version 1.3:: 25 Mar 2008
31 # * Fixed bug to detect a winner, and also eliminate players
32 # that have no uncaptured pieces.
36 # Pieces can only capture pieces that they're on.
37 class InvalidCaptureError
< StandardError
40 # Moves can only be [1..6] spaces
41 class InvalidMoveError
< StandardError
44 # Game is won when only one player has uncaptured pieces
45 class GameWonNotice
< StandardError
49 # Each possible position for a piece is an object
50 # Each neighbour is another position object
52 attr_reader
:place # the name of this place
53 attr_accessor
:contains # the pieces it contains
54 attr_accessor
:neighbours # the positions that neighbour it
56 def initialize(place
, safety
, base
)
60 @neighbours = Array
.new
63 # is this position a safety one (i.e. no captures allowed)?
68 # Is this position a base?
87 attr_reader
:positions
88 attr_reader
:valid_moves
89 attr_reader
:distance_between
93 # A laborious procedure to create all the positions and tie them all together
94 def initialize(spokes
, spoke_length
, arc_length
)
95 # A hash of all positions, indexed by position names
97 @centre = Position
.new('ac' + spoke_length
.to_s
, false, false)
98 @positions['ac' + spoke_length
.to_s
] = centre
100 end_of_previous_arc
= nil
102 # Do each arc-spoke-base set
103 (?a
...(?a
+ spokes
)).each
do |arc_code
|
105 base
= Position
.new(arc
, false, true)
109 (1..arc_length
).each
do |arc_position
|
110 position_name
= arc
+ arc_position
.to_s
111 arc_place
= Position
.new(position_name
, arc_position
== 4, false)
112 arc_place
.neighbours
= []
113 @positions[position_name
] = arc_place
114 this_arc
<< arc_place
115 a1_corner
= a1_corner
|| arc_place
117 (0...arc_length
).each
do |arc_position
|
119 this_arc
[arc_position
].neighbours
<< this_arc
[arc_position
- 1]
121 if arc_position
< (arc_length
- 1)
122 this_arc
[arc_position
].neighbours
<< this_arc
[arc_position
+ 1]
127 this_spoke
= Array
.new
128 (1..(spoke_length
- 1)).each
do |spoke_position
|
129 position_name
= arc
+ "c" + spoke_position
.to_s
130 spoke_place
= Position
.new(position_name
, spoke_position
== 3, false)
131 spoke_place
.neighbours
= []
132 @positions[position_name
] = spoke_place
133 this_spoke
<< spoke_place
135 (0...(spoke_length
- 1)).each
do |spoke_position
|
136 if spoke_position
> 0
137 this_spoke
[spoke_position
].neighbours
<< this_spoke
[spoke_position
- 1]
139 if spoke_position
< spoke_length
- 2
140 this_spoke
[spoke_position
].neighbours
<< this_spoke
[spoke_position
+ 1]
144 # tie the spoke and arc together,
145 this_arc
[0].neighbours
<< this_spoke
[0]
146 this_spoke
[0].neighbours
<< this_arc
[0]
148 # tie the spoke to the centre, and
149 this_spoke
[-1].neighbours
<< @centre
150 @centre.neighbours
<< this_spoke
[-1]
152 # tie the base to the arc
153 base
= Position
.new(arc
, false, true)
154 @positions[arc
] = base
155 base
.neighbours
<< this_arc
[0]
156 this_arc
[0].neighbours
<< base
158 # record the ends of the arc for tying to adjacent arcs
159 if end_of_previous_arc
160 end_of_previous_arc
.neighbours
<< this_arc
[0]
161 this_arc
[0].neighbours
<< end_of_previous_arc
163 end_of_previous_arc
= this_arc
[-1]
167 # tie both ends of the rim together
168 a1_corner
.neighbours
<< end_of_previous_arc
169 end_of_previous_arc
.neighbours
<< a1_corner
184 # For each position, show its name and what it touches
187 @positions.keys
.sort
.each
do |position
|
188 out_string
<< sprintf("%s touches ", @positions[position
])
189 @positions[position
].neighbours
.each
do |neighbour
|
190 out_string
<< sprintf("%s, ", neighbour
)
192 out_string
<< sprintf("\n")
198 # Precompute the valid moves for this board, and the distances between each
200 def cache_valid_moves
201 # A hash of arrays. The has key is the name of a positions. The array
202 # element [i] stores the positions that are i spaces from here
203 @valid_moves = Hash
.new
204 # A hash of hashes. Given two names, return the shortest distance between
206 @distance_between = Hash
.new
207 @positions.each
do |place
, position
|
208 @valid_moves[place
] = Array
.new
209 @distance_between[place
] = Hash
.new
210 @valid_moves[place
][0] = [@positions[place
]]
211 @distance_between[place
][place
] = 0
212 # Find the shortest routes by Dijkstra's algorithm
214 closed_list
= [position
]
216 while not agenda
.empty
?
217 @valid_moves[place
][i
] = []
220 valid_extensions
= pos
.neighbours
.reject
{|new_position
| closed_list
.include?(new_position
) }
221 @valid_moves[place
][i
] += valid_extensions
222 valid_extensions
.each
{|ext
| @distance_between[place
][ext
.place
] ||= i
}
223 closed_list
+= valid_extensions
224 new_agenda
+= valid_extensions
235 # Each piece on the board is an object
238 attr_accessor
:position, :contains, :captured
240 def initialize(number
, position
, colour
)
249 @colour + @number.to_s
260 def move_to(new_position
)
261 @position = new_position
262 @contains.each
{|c
| c
.move_to(new_position
)}
265 # Caputre another piece
266 def capture(other_piece
)
267 if @position = other_piece
.position
268 @contains << other_piece
269 @contains += other_piece
.contains
270 other_piece
.contains
= []
271 other_piece
.captured
= true
273 raise(InvalidCaptureError
,
274 "Piece #{self.name} cannot capture #{other_piece.name}: different locations")
283 attr_reader
:piece, :destination
285 def initialize(piece
, destination
, via_base
= false)
287 @destination = destination
295 # Write a move to a string
296 # Note the inverse, String#to_move, is defined below
299 if @destination.base
?
300 @piece.to_s
+ " " + @destination.to_s
302 @piece.to_s
+ " " + piece
.colour
+ " " + @destination.to_s
305 @piece.to_s
+ " " + @destination.to_s
317 # A class to record each of the states previously found in a game.
318 # Note that this is a deep copy of the pieces and what they've captured, so
319 # you'll need to convert back
321 attr_accessor
:move, :player, :pieces_after_move
323 def initialize(move
, player
, pieces
)
326 @pieces_after_move = Hash
.new
327 pieces
.each
{|k
, p
| @pieces_after_move[k
] = p
.dup
}
328 @pieces_after_move.each_value
{|p
| p
.contains
= []}
329 # and now to make the captured pieces point to the copies
330 pieces
.each
do |k
, p
|
331 p
.contains
.each
do |captured_piece
|
332 @pieces_after_move[k
].capture(@pieces_after_move[captured_piece
.name
])
338 @move.to_s
== other
.move
.to_s
and
339 @player == other
.player
and
340 @piece_after_move == other
.pieces_after_move
346 # A game of Trap the Cap. It keeps a history of all previous states.
350 attr_reader
:current_player, :players
355 def initialize(players
= 6, spokes
= 6, spoke_length
= 6, arc_length
= 6,
357 @board = Board
.new(spokes
, spoke_length
, arc_length
)
361 when players
== 2 ; ['a', 'd']
362 when players
== 3 ; ['a', 'c', 'e']
363 when players
== 4 ; ['a', 'b', 'd', 'e']
364 when players
== 5 ; ['a', 'b', 'c', 'd', 'e']
365 when players
== 6 ; ['a', 'b', 'c', 'd', 'e', 'f']
367 @current_player = 'a'
368 @players.each
do |player
|
369 players_base
= @board.positions
[player
]
370 (1..pieces_each
).each
do |count
|
371 piece
= Piece
.new(count
, players_base
, player
)
372 @pieces[player
+ count
.to_s
] = piece
378 # Apply a single move to a game.
379 def apply_move
!(move
, player
= @current_player)
380 # Check the move is a valid one
381 raise(InvalidMoveError
, "Piece #{move.piece} does not exist") unless @pieces.has_key
?(move
.piece
.name
)
382 raise(InvalidMoveError
, "Player #{player} moving piece #{move.piece}") unless move
.piece
.colour
== player
383 raise(InvalidMoveError
, "Attempting to move captured piece #{move.piece}") if move
.piece
.captured
384 raise(InvalidMoveError
, "Attempting to move #{move.piece} onto or via base without captured pieces") if move
.via_base
? and move
.piece
.contains
.empty
?
385 if move
.destination
.safe
?
386 if (@pieces.find_all
{|k
, p
| p
.position
== move
.destination
}).length
>= 3
387 raise(InvalidMoveError
, "Attempting to move #{move.piece} onto safe position #{move.destination} when there are already three or more pieces there")
391 moved_distance
= board
.distance_between
[move
.piece
.position
.place
][player
] +
392 board
.distance_between
[player
][move
.destination
.place
]
394 moved_distance
= board
.distance_between
[move
.piece
.position
.place
][move
.destination
.place
]
396 raise(InvalidMoveError
, "Attempting to move piece #{move.piece} #{moved_distance} places (from #{move.piece.position} to #{move.destination})") if moved_distance
< 1 or moved_distance
> 6
399 move
.piece
.move_to(move
.destination
)
401 # Capture anything already there (unless it's a safe place or a base,
402 # or our own colour, or already captured)
403 unless move
.destination
.safe
? or move
.destination
.base
?
404 @pieces.each
do |name
, target_piece
|
405 if target_piece
.position
== move
.destination
and
406 target_piece
!= move
.piece
and
407 not move
.piece
.contains
.member
?(target_piece
) and
408 target_piece
.colour
!= player
and
409 not target_piece
.captured
410 move
.piece
.capture(target_piece
)
415 # If the move was via our base, drop all captured pieces
417 capturers_base
= board
.positions
[move
.piece
.colour
]
418 move
.piece
.contains
.each
do |captured_piece
|
419 captured_piece
.move_to capturers_base
420 captured_piece
.captured
= false if captured_piece
.colour
== move
.piece
.colour
422 move
.piece
.contains
= []
425 # Record the new stae
426 this_game_state
= GameState
.new(move
, player
, @pieces)
427 @history << this_game_state
429 # Retain only players that have uncaptured pieces.
430 # If there's only one player with uncaptured pieces, declare a win.
431 potential_players
= []
433 if (@pieces.values
.select
{|piece
| piece
.colour
== p
}).any
? {|piece
| not piece
.captured
}
434 potential_players
<< p
436 # potential_players << p if (@pieces.values.select {|p| p.colour == @current_player}).any? {|p| not p.captured}
438 if potential_players
.length
<= 1
439 raise(GameWonNotice
, "Game won by #{potential_players[0]}")
441 @players = potential_players
.sort
446 if @history.length
> 1
448 state_to_restore
= @history[-2]
449 @current_player = @history[-1].player
450 @pieces.each
do |name
, piece
|
451 copy_piece
= state_to_restore
.pieces_after_move
[name
]
452 piece
.position
= copy_piece
.position
453 piece
.captured
= copy_piece
.captured
455 copy_piece
.contains
.each
do |p
|
456 # piece.capture(@pieces[p.name])
457 piece
.contains
<< @pieces[p
.name
]
461 elsif @history.length
== 1
463 @current_player = 'a'
464 @pieces.each
do |name
, piece
|
465 piece
.position
= @board.positions
[piece
.colour
]
466 piece
.captured
= false
473 # Apply a list of moves in order
474 def apply_moves
!(moves
)
477 moved_distance
= board
.distance_between
[move
.piece
.position
.place
][@current_player] +
478 board
.distance_between
[@current_player][move
.destination
.place
]
480 moved_distance
= board
.distance_between
[move
.piece
.position
.place
][move
.destination
.place
]
482 self.apply_move
!(move
, @current_player)
483 next_player
! unless moved_distance
== 6
488 # Set the current player to be the next player
490 original_player
= @current_player
492 if @current_player == @players[-1]
493 @current_player = @players[0]
495 @current_player = @players[@players.index(@current_player) + 1]
497 end while (@pieces.values
.select
{|p
| p
.colour
== @current_player}).all
? {|p
| p
.captured
} and @current_player != original_player
502 # Return an array of all possible moves from this state, given the die roll
503 # and the active player
504 def possible_moves(die_result
, player
= @current_player)
506 @pieces.each
do |key
, piece
|
507 # only move current player's pieces, and only if they're not captured
508 if piece
.colour
== player
and (not piece
.captured
)
509 (@board.valid_moves
[piece
.position
.place
][die_result
]).each
do |destination
|
511 if (@pieces.find_all
{|k
, p
| p
.position
== destination
}).length
< 3
512 moves
<< Move
.new(piece
, destination
, false)
515 moves
<< Move
.new(piece
, destination
, false) unless destination
.base
?
518 # if we can move to our base (but not already on it), add moves via that...
519 if @board.distance_between
[piece
.position
.place
][player
] <= die_result
and
520 not piece
.position
.place
== player
and
521 not piece
.contains
.empty
?
522 distance_after_base
= die_result
- @board.distance_between
[piece
.position
.place
][player
]
523 (@board.valid_moves
[player
][distance_after_base
]).each
do |destination
|
525 if (@pieces.find_all
{|k
, p
| p
.position
== destination
}).length
< 3
526 moves
<< Move
.new(piece
, destination
, true)
529 moves
<< Move
.new(piece
, destination
, true)
539 def build_state_string
540 outstr
= "Current player = #{@current_player}\n"
541 @pieces.keys
.sort
.each
do |piece_name
|
542 if @pieces[piece_name
].captured
543 outstr
<< "Piece #{piece_name} captured, at #{@pieces[piece_name].position}\n"
545 outstr
<< "Piece #{piece_name} is at #{@pieces[piece_name].position}, holds #{(@pieces[piece_name].contains.collect{|c| c.name}).join(' ')}\n"
551 # Show the state of the board
553 puts build_state_string
554 # @pieces.keys.sort.each do |piece_name|
555 # if @pieces[piece_name].captured
556 # puts "Piece #{piece_name} captured, at #{@pieces[piece_name].position}"
558 # puts "Piece #{piece_name} is at #{@pieces[piece_name].position}, holds #{(@pieces[piece_name].contains.collect{|c| c.name}).join(' ')}"
572 # Given a set of lines from an input file, turn them into a Game object and
573 # a set of Move objects.
574 # Note the multiple return values.
576 def Game
.read_game(gamelines
)
577 gamelines
.each
{|l
| l
.chomp
!}
578 game
= Game
.new(gamelines
[0].to_i
, 6, 6, 6, 6)
580 gamelines
[1..-2].each
{|m
| moves
<< m
.to_move(game
)}
581 return game
, moves
, gamelines
[-1].to_i
588 # Extension to String class to convert a move-description string into a Move object.
589 # This is the inverse of the Move#to_s method
592 move_elements
= self.downcase
.split
593 piece_name
= move_elements
[0]
594 destination_name
= move_elements
[-1]
595 if destination_name
.length
> 2 and
596 destination_name
[-2,2] == game
.board
.centre
.place
[-2,2]
597 destination_name
= game
.board
.centre
.place
599 raise(InvalidMoveError
, "Invalid piece in move read") unless game
.pieces
.has_key
?(piece_name
)
600 raise(InvalidMoveError
, "Invalid destination in move read") unless game
.board
.positions
.has_key
?(destination_name
)
601 # Deal with the synonyms for the centre position
602 via_base
= (destination_name
.length
== 1 or move_elements
.length
> 2)
603 Move
.new(game
.pieces
[piece_name
], game
.board
.positions
[destination_name
], via_base
)
608 # Read a game description file and convert it into a Game object and set of Move objects.
609 # Note that Game.read_game method returns multiple values, so this one does too.
611 def IO
.read_game(filename
)
612 gamelines
= IO
.readlines(filename
)
613 return Game
.read_game(gamelines
)