[QUIZ] Solving Tactics (#18)

ruby-talk
1

Sea&Gull wrote:

I made one guess - count of possible wins of the first and
second player on the 4x4 board is in direct proportion to
count of their wins on the 4x2 board (due to the symmetry of
the 4x4 board and possible moves).

I have not managed to prove it mathematically,
so my program below may be totally wrong... :slight_smile:

That was a good try, Sea&Gull. Your attempt does have some of the
elements of the solution that I will post tomorrow. And it even gets
the right answer (well, alright, I mean, if it agrees with MY program
as to what the right answer is!). Your solution is partly on the right
track, in that you have:

1. Devised an efficient algorithm for actually playing games (using
bit operations).

2. Made an attempt at reducing the number of games that have to be
played in order to reach a solution.

Both of the above elements are critical to success. There's a couple
of things missing, though:

1. A solution that uses no other knowledge about the game than that
provided in the basic rules of play. Appealing to a mathematical
conjecture, whether true or not (and no matter how interesting) is not
allowed by these rules--unless the proof can somehow be contained
within the program itself. If someone came to me and said, "I can
prove that the second player can always win", and then wrote the
following ruby program:

  puts("Second player wins")

I'm afraid I'd have to disqualify him, too! But he might deserve some
points for chutzpah and simplicity, and getting an answer that agrees
with mine :slight_smile:

2. I suggested that there should be "bonus" points for making the case
that your program gets the right answer for the right reason. I'm
starting to think that this should have been a *requirement*.

<SPOILER>
I'll drop a big hint here: The board can be represented by a 16-bit
number. There are a HUGE number of games that can be played. BUT,
there are only a certain number of positions that can be arrived at
during play. And all of them are either winning positions or losing
positions.
</SPOILER>

Cheers,
Bob

2

Bob Sidebotham wrote:

Sea&Gull wrote:

I made one guess - count of possible wins of the first and
second player on the 4x4 board is in direct proportion to
count of their wins on the 4x2 board (due to the symmetry of
the 4x4 board and possible moves).

I have not managed to prove it mathematically,
so my program below may be totally wrong... :slight_smile:

That was a good try, Sea&Gull. Your attempt does have some of the
elements of the solution that I will post tomorrow. And it even gets
the right answer (well, alright, I mean, if it agrees with MY program
as to what the right answer is!).

I was lucky :)))

Your solution is partly on the right
track, in that you have:

1. Devised an efficient algorithm for actually playing games (using
bit operations).

2. Made an attempt at reducing the number of games that have to be
played in order to reach a solution.

Both of the above elements are critical to success. There's a couple
of things missing, though:

1. A solution that uses no other knowledge about the game than that
provided in the basic rules of play. Appealing to a mathematical
conjecture, whether true or not (and no matter how interesting) is not
allowed by these rules--unless the proof can somehow be contained
within the program itself.

Why?
The game "Tactics" is an informational _object_ of the
Universe. It has its own laws of life. Math helps
to _understand_ that laws, to express them _clearly_.

To code the program is the last stage. The first is to
_undestand_ the problem, to see how everything works.

If I would find some regularities in the life
cycle of the Tactics object and would prove
that they really exist (with help of math
and combinatorial theory in particular or
whatever else), I would undestand how it lives.
So I coud solve the quiz in a most effective way.

I would not come to you saying "Hey, I proved that
second player always win!". Instead of it I would
give you an algorithm which uses proved regularities.
If they really exist (my prove was correct), they
exist always and everywhere, not depending on how you found them.
Because they exist somewhere beyond, somewhere
on the informational field/sphere.

:slight_smile:

If someone came to me and said, "I can
prove that the second player can always win", and then wrote the
following ruby program:

  puts("Second player wins")

I'm afraid I'd have to disqualify him, too! But he might deserve some
points for chutzpah and simplicity, and getting an answer that agrees
with mine :slight_smile:

His/her program knows nothing about how the Tactics object lives.
So the disqualification of such a try would be well-taken :slight_smile:
But... it depends on the rules of the quiz ; )

2. I suggested that there should be "bonus" points for making the case
that your program gets the right answer for the right reason. I'm
starting to think that this should have been a *requirement*.

:wink:

<SPOILER>
I'll drop a big hint here: The board can be represented by a 16-bit
number. There are a HUGE number of games that can be played. BUT,
there are only a certain number of positions that can be arrived at
during play. And all of them are either winning positions or losing
positions.

I thought of that too... Is the count of free cells even or odd number?
Need to think again :slight_smile:

···

</SPOILER>

Cheers,
Bob

--
   s&g

3

I've enclosed my solution to the "Solving Tactics" quiz as an attached
gzipped tar file. The README from that file is reproduced, below.

Enjoy!
Bob

This is my solution to the "Solving Tactics" Ruby Quiz #18.

I previously solved this puzzled over 30 years ago on a Control Data
Corporation mainframe computer (A CDC Cyber 6400). The program was
hand-optimized assembler code, written as a self-assigned term
project. My best recollection is that it took a few seconds to run;
probably on the order of 10 seconds. Interestingly, my Ruby version
takes a similar amount of time on my fairly ancient 600MHz processor.

The basic idea is simple: a Tactics board contains just 16 cells,
which can be empty or filled. This readily admits to a representation
as a 16-bit number. Games can be played by using bit operations to
determine and play individual moves. The key observation is that there
are just 2**16 possible board positions. Each of these is either a
winning or losing position.

This solution implements a playing engine that can play from any given
board position. The algorithm is to see whether, from that position, a
win is ensured, or not. This is done by trying all the possible moves
from that position until a win is found. If a win is found, then the
starting position is marked as a losing position (because the next
play could win). Otherwise, if no win's are possible for the opponent
from this position, then the starting position is marked as a win. A
play is trivially determined to be a win or loss if has been marked as
such from a previous play. If that result has not been cached, then
the play engine is invoked recursively. Eventually, the algorithm will
terminate, because the cache is seeded with the information that an
entirely filled grid represents a loss. To determine whether the first
or second player is bound to win, simply invoke the play engine with
an empty board.

This takes a lot more effort to say in words, than to program in
code. The actual code described above is just this:

  # 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

The required result is determined by this separately provided program:

require 'tactics'
puts %(#{Tactics.new.play == Tactics::WIN ? "First" : "Second"} player wins.)

The Quiz writeup suggests that a good solution should demonstrate
convincingly that the answer given likely to be correct. I've chosen
to use unit tests for this purpose. The unit tests take advantage of
the play engine's ability to play from any board position to play a
variety of end games. In each case a proof is provided (in the
comments) of which player should win or lose, and the unit test
asserts that the play engine agrees with the proof's assertion. This
is a form of black-box testing that doesn't directly test (for
example) that the program even knows how to play every possible
move. But, indirectly, it provides strong evidence that this is likely
to be the case.

Bob.Sidebotham@gmail.com

tactics.tar.gz (3.63 KB)