[SUMMARY] Solving Tactics (#18)

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:

	class Tactics
	  # 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:

	require 'tactics'
	
	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 'test/unit'
	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!  :)