by Bob Sidebotham
There's a little pencil and paper game, Tactics, played on a 4x4 grid. The play starts with an empty grid. On each turn, a player can fill in one to four adjacent squares, either horizontally or vertically. The player who fills in the last square loses.
Here's a sample game to help clarify the above rules. The board position at the end of each play is shown (best viewed in a fixed-width font):
First player Second player
X X X X X X X X (Turn 1)
_ _ _ _ _ _ _ _
_ _ _ _ _ _ X _
_ _ _ _ _ _ X _
X X X X X X X X (Turn 2)
X X _ _ X X _ X
_ _ X _ _ _ X X
_ _ X _ _ _ X _
X X X X X X X X (Turn 3)
X X _ X X X X X
_ _ X X _ _ X X
_ _ X X _ _ X X
X X X X X X X X (Turn 4)
X X X X X X X X
X X X X X X X X
_ _ X X X _ X X
X X X X (Turn 5
X X X X Second
X X X X player
X X X X wins!)
Your task, should you choose to accept it, is to write a Ruby program which, given only these rules, determines whether the first or second player is bound to be the winner, assuming perfect play. It should do this in a "reasonable" amount of time and memory--it should definitely take under a minute on any processor less than 5 years old. Bonus points if you can make the case that your program actually gets the right answer for the right reason!
Quiz Summary
Tactics is a strange game to us chess players. I'm so use to considering going first to be an advantage that I was just sure it would be true here too. Wrong again. In Tactics, the second player can always force a win.
Though "why" this is true was part of the quiz, it hasn't really been answered to my satisfaction. I suspect it has to do with the moves remaining. The first player starts with the lead. The second player can always choose to respond with moves that keep the first player in the lead. If you're in the lead at the end of the game, you lose. Put another way, the second player can always add to the first player's move just the right amount of squares to keep the number of remaining moves optimal.
What does that have to do with the quiz? Not much. It's just a good example of the kinds of things I lose sleep over.
This quiz turned out to be a little tougher than I expected, though it really shouldn't be. A couple of people, including myself, posted about our failed attempts to build the entire move tree. You need to be a bit move clever than that.
Sea&Gull shaved the move tree in half and even came up with the right answer. I haven't been able to convince myself it's for the right reasons yet though, so I'm not going to look into that here.
The key optimization hit on by both solutions is simple: All squares are either on or off, thus ideal bit representation material. An empty board is just 0b0000_0000_0000_0000 and the final board is 0b1111_1111_1111_1111. To make a move, just "or" (|) it to the board. To see if a move is possible "and" (&) it to the board and check for a result of zero.
As Bob Sidebotham said in the README of his solution, there are only 2**16 (65536) possible positions and bit math is as fast as a computer gets. My machine needs about 4 seconds to get the answer with Bob's code. Let's look at that code now:
# The tactics board is represented as a 16-bit integer,
# 0's representing empty square; 1's representing filled squares.
EMPTY, FULL = 0, 0xFFFF
# Record a WIN or LOSS for potentially each of the 2**16 possible
# board positions. A position is recorded as a WIN (or LOSS) if
# that position represents a WIN (or LOSS) to a player prior to
# moving from that position.
WIN, LOSS = 1, 0
(@@position = Array.new(0x10000))[FULL] = WIN
# Create a new Tactics game, starting at the specified position.
def initialize( board = EMPTY,
possible_moves = Tactics.all_possible_moves )
@board = board
@possible_moves = prune_possible_moves(board, possible_moves)
end
# Play from the current position. If *any* move guarantees a win,
# then mark this position as a WIN and return it. Otherwise this
# position loses.
def play
@possible_moves.each do |move|
new_board = @board | move
if ( @@position[new_board] ||
Tactics.new(new_board, @possible_moves).play) == LOSS then
return @@position[@board] = WIN
end
end
@@position[@board] = LOSS
end
private
# Reduce the set of possible moves provided to the actual moves
# that are possible from the specified starting position.
def prune_possible_moves(board, possible_moves)
possible_moves.reject { |move| (board & move) != 0 }
end
# Compute all possible moves from an empty board.
def self.all_possible_moves
# Replicate the possibilities for a single row over each row and
# column of the grid.
(0..3).inject([]) do |moves, row|
[ 0b1000, 0b0100, 0b0010, 0b0001, 0b1100,
0b0110, 0b0011, 0b1110, 0b0111, 0b1111 ].each do |bits|
move = bits << 4 * row
moves << move << transpose(move)
end
moves
end.uniq
end
# Return the transposed board (horizontal to vertical, or vice-versa)
def self.transpose(board)
(0..15).inject(0) { |xboard, i|
q,r = i.divmod(4); xboard |= board[i] << q + r*4
}
end
end
I'm not going to insult everyone's intelligence by breaking down well commented code, but I do want to point out a few things. Note toward the top that FULL is set to 0xFFFF. 0xFFFF is just another way to say 0b1111_1111_1111_1111, which I mentioned earlier. Then on the second line of play(), you can see moves being made with |. prune_possible_moves() uses & and the check for zero to see what's possible at a given position.
The other point of interest is all_possible_moves(). This method builds up a list of all the moves that can be made, from the moves that can be made over a single row. That row of moves is bit shifted to cover the other rows and, with help from transpose(), rotated to cover the columns too. That's scary cool, isn't it?
Bob's actual solution, using the above library:
puts %(#{ Tactics.new.play == Tactics::WIN ? "First" :
"Second" } player wins.)
I'm assuming that speaks for itself. I'm not done showing off Bob yet though. Have a look at this beautiful set of unit tests:
require 'tactics.rb'
class TestTactics < Test::Unit::TestCase
# Test the play engine by trying various board positions that we
# know are winning or losing positions. Each of these is justified
# (no point in using ones that are just hunches on our part--'cause
# then what would we be verifying?).
def test_play
# Each position description is the position you're faced with
# just before playing. So "1 square loses" means that if it's
# your turn to play, and there's only one square available,
# you lose.
# 1 square loses (obviously)
assert_equal(Tactics::LOSS, Tactics.new(0b0111_1111_1111_1111).play)
assert_equal(Tactics::LOSS, Tactics.new(0b1011_1111_1111_1111).play)
assert_equal(Tactics::LOSS, Tactics.new(0b1101_1111_1111_1111).play)
assert_equal(Tactics::LOSS, Tactics.new(0b1110_1111_1111_1111).play)
assert_equal(Tactics::LOSS, Tactics.new(0b1111_0111_1111_1111).play)
assert_equal(Tactics::LOSS, Tactics.new(0b1111_1011_1111_1111).play)
assert_equal(Tactics::LOSS, Tactics.new(0b1111_1101_1111_1111).play)
assert_equal(Tactics::LOSS, Tactics.new(0b1111_1110_1111_1111).play)
assert_equal(Tactics::LOSS, Tactics.new(0b1111_1111_0111_1111).play)
assert_equal(Tactics::LOSS, Tactics.new(0b1111_1111_1011_1111).play)
assert_equal(Tactics::LOSS, Tactics.new(0b1111_1111_1101_1111).play)
assert_equal(Tactics::LOSS, Tactics.new(0b1111_1111_1110_1111).play)
assert_equal(Tactics::LOSS, Tactics.new(0b1111_1111_1111_0111).play)
assert_equal(Tactics::LOSS, Tactics.new(0b1111_1111_1111_1011).play)
assert_equal(Tactics::LOSS, Tactics.new(0b1111_1111_1111_1101).play)
assert_equal(Tactics::LOSS, Tactics.new(0b1111_1111_1111_1110).play)
# 2 squares in a row wins (because you can reduce to one square)
assert_equal(Tactics::WIN, Tactics.new(0b0011_1111_1111_1111).play)
assert_equal(Tactics::WIN, Tactics.new(0b1001_1111_1111_1111).play)
assert_equal(Tactics::WIN, Tactics.new(0b1100_1111_1111_1111).play)
assert_equal(Tactics::WIN, Tactics.new(0b1111_0011_1111_1111).play)
assert_equal(Tactics::WIN, Tactics.new(0b1111_1001_1111_1111).play)
assert_equal(Tactics::WIN, Tactics.new(0b1111_1100_1111_1111).play)
assert_equal(Tactics::WIN, Tactics.new(0b1111_1111_0011_1111).play)
assert_equal(Tactics::WIN, Tactics.new(0b1111_1111_1001_1111).play)
assert_equal(Tactics::WIN, Tactics.new(0b1111_1111_1100_1111).play)
assert_equal(Tactics::WIN, Tactics.new(0b1111_1111_1111_0011).play)
assert_equal(Tactics::WIN, Tactics.new(0b1111_1111_1111_1001).play)
assert_equal(Tactics::WIN, Tactics.new(0b1111_1111_1111_1100).play)
assert_equal(Tactics::WIN, Tactics.new(0b0111_0111_1111_1111).play)
assert_equal(Tactics::WIN, Tactics.new(0b1111_0111_0111_1111).play)
assert_equal(Tactics::WIN, Tactics.new(0b1111_1111_0111_0111).play)
assert_equal(Tactics::WIN, Tactics.new(0b1011_1011_1111_1111).play)
assert_equal(Tactics::WIN, Tactics.new(0b1111_1011_1011_1111).play)
assert_equal(Tactics::WIN, Tactics.new(0b1111_1111_1011_1011).play)
assert_equal(Tactics::WIN, Tactics.new(0b1101_1101_1111_1111).play)
assert_equal(Tactics::WIN, Tactics.new(0b1111_1101_1101_1111).play)
assert_equal(Tactics::WIN, Tactics.new(0b1111_1111_1101_1101).play)
assert_equal(Tactics::WIN, Tactics.new(0b1110_1110_1111_1111).play)
assert_equal(Tactics::WIN, Tactics.new(0b1111_1110_1110_1111).play)
assert_equal(Tactics::WIN, Tactics.new(0b1111_1111_1110_1110).play)
# 3 squares in a row wins (because you can reduce to one square)
assert_equal(Tactics::WIN, Tactics.new(0b0001_1111_1111_1111).play)
assert_equal(Tactics::WIN, Tactics.new(0b1000_1111_1111_1111).play)
assert_equal(Tactics::WIN, Tactics.new(0b1111_0001_1111_1111).play)
assert_equal(Tactics::WIN, Tactics.new(0b1111_1000_1111_1111).play)
assert_equal(Tactics::WIN, Tactics.new(0b1111_1111_0001_1111).play)
assert_equal(Tactics::WIN, Tactics.new(0b1111_1111_1000_1111).play)
assert_equal(Tactics::WIN, Tactics.new(0b1111_1111_1111_0001).play)
assert_equal(Tactics::WIN, Tactics.new(0b1111_1111_1111_1000).play)
assert_equal(Tactics::WIN, Tactics.new(0b0111_0111_0111_1111).play)
assert_equal(Tactics::WIN, Tactics.new(0b1111_0111_0111_0111).play)
assert_equal(Tactics::WIN, Tactics.new(0b1011_1011_1011_1111).play)
assert_equal(Tactics::WIN, Tactics.new(0b1111_1011_1011_1011).play)
assert_equal(Tactics::WIN, Tactics.new(0b1101_1101_1101_1111).play)
assert_equal(Tactics::WIN, Tactics.new(0b1111_1101_1101_1101).play)
assert_equal(Tactics::WIN, Tactics.new(0b1110_1110_1110_1111).play)
assert_equal(Tactics::WIN, Tactics.new(0b1111_1110_1110_1110).play)
# 4 squares in a row wins (because you can reduce to one square)
assert_equal(Tactics::WIN, Tactics.new(0b0000_1111_1111_1111).play)
assert_equal(Tactics::WIN, Tactics.new(0b1111_0000_1111_1111).play)
assert_equal(Tactics::WIN, Tactics.new(0b1111_1111_0000_1111).play)
assert_equal(Tactics::WIN, Tactics.new(0b1111_1111_1111_0000).play)
assert_equal(Tactics::WIN, Tactics.new(0b0111_0111_0111_0111).play)
assert_equal(Tactics::WIN, Tactics.new(0b1011_1011_1011_1011).play)
assert_equal(Tactics::WIN, Tactics.new(0b1101_1101_1101_1101).play)
assert_equal(Tactics::WIN, Tactics.new(0b1110_1110_1110_1110).play)
# 2x2 square loses (because your opponent can always reduce it to one
# square immediately after your move)
assert_equal(Tactics::LOSS, Tactics.new(0b0011_0011_1111_1111).play)
assert_equal(Tactics::LOSS, Tactics.new(0b1111_0011_0011_1111).play)
assert_equal(Tactics::LOSS, Tactics.new(0b1111_1111_0011_0011).play)
assert_equal(Tactics::LOSS, Tactics.new(0b1001_1001_1111_1111).play)
assert_equal(Tactics::LOSS, Tactics.new(0b1111_1001_1001_1111).play)
assert_equal(Tactics::LOSS, Tactics.new(0b1111_1111_1001_1001).play)
assert_equal(Tactics::LOSS, Tactics.new(0b1100_1100_1111_1111).play)
assert_equal(Tactics::LOSS, Tactics.new(0b1111_1100_1100_1111).play)
assert_equal(Tactics::LOSS, Tactics.new(0b1111_1111_1100_1100).play)
# 2x3 (or 3x2) rectangle wins (because you can reduce it to a 2x2)
assert_equal(Tactics::WIN, Tactics.new(0b0011_0011_0011_1111).play)
assert_equal(Tactics::WIN, Tactics.new(0b1001_1001_1001_1111).play)
assert_equal(Tactics::WIN, Tactics.new(0b1100_1100_1100_1111).play)
assert_equal(Tactics::WIN, Tactics.new(0b1111_0011_0011_0011).play)
assert_equal(Tactics::WIN, Tactics.new(0b1111_1001_1001_1001).play)
assert_equal(Tactics::WIN, Tactics.new(0b1111_1100_1100_1100).play)
assert_equal(Tactics::WIN, Tactics.new(0b0001_0001_1111_1111).play)
assert_equal(Tactics::WIN, Tactics.new(0b1000_1000_1111_1111).play)
assert_equal(Tactics::WIN, Tactics.new(0b1111_0001_0001_1111).play)
assert_equal(Tactics::WIN, Tactics.new(0b1111_1000_1000_1111).play)
assert_equal(Tactics::WIN, Tactics.new(0b1111_1111_0001_0001).play)
assert_equal(Tactics::WIN, Tactics.new(0b1111_1111_1000_1000).play)
# Now we'll play from an empty board. The purpose of this assertion
# is just to verify that we get the same answer that we get when
# the engine is started from scratch. In this case, we have done all
# the preceding plays--the results of which are stored in the engine.
assert_equal(Tactics::LOSS, Tactics.new(0b0000_0000_0000_0000).play)
# Also check that it works the same with the defaulted empty board.
assert_equal(Tactics::LOSS, Tactics.new.play)
# Continue with a few random assertions. No attempt to be exhaustive
# this time. This is deliberately located below the full play, above,
# to see that intermediate board positions that have been stored
# are accurate. Of course, this doesn't test very many of them.
# A 2x2 L shape. Trivially reducible to 1 square.
assert_equal(Tactics::WIN, Tactics.new(0b0011_0111_1111_1111).play)
assert_equal(Tactics::WIN, Tactics.new(0b1111_1011_1001_1111).play)
# A 2x3 L shape. Trivially reducible to 1 square.
assert_equal(Tactics::WIN, Tactics.new(0b0011_0111_0111_1111).play)
assert_equal(Tactics::WIN, Tactics.new(0b1111_1011_1000_1111).play)
# A 2x4 L shape. Trivially reducible to 1 square.
assert_equal(Tactics::WIN, Tactics.new(0b0011_0111_0111_0111).play)
assert_equal(Tactics::WIN, Tactics.new(0b1111_0111_0000_1111).play)
# A 3x4 L shape. Reducible to two lengths of two.
assert_equal(Tactics::WIN, Tactics.new(0b0001_0111_0111_0111).play)
assert_equal(Tactics::WIN, Tactics.new(0b0000_0111_0111_1111).play)
# A checkerboard. Wins as long as the number of open squares is even.
assert_equal(Tactics::WIN, Tactics.new(0b0101_1010_0101_1010).play)
assert_equal(Tactics::WIN, Tactics.new(0b1010_0101_1010_0101).play)
end
end
That's a flawless combination of code and comment logic, if you ask me. Very nice.
My thanks to Bob Sidebotham for sending in a thought provoking quiz and then showing us how it's done. Thanks for the free lessons, Bob.
Tomorrow's quiz is a choose your own difficulty problem so I expect to see all of you submitting solutions! :)
