From: Bob Sidebotham <bob.sidebotham@...>
Date: 2005-02-09T01:51:58+09:00
Subject: Re: [QUIZ] Solving Tactics (#18) (SOLUTION)

------=_Part_2860_15554074.1107881501231
Content-Type: text/plain; charset=US-ASCII
Content-Transfer-Encoding: 7bit
Content-Disposition: inline

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

------=_Part_2860_15554074.1107881501231
Content-Type: application/x-tar; name="tactics.tar.gz"
Content-Transfer-Encoding: base64
Content-Disposition: attachment; filename="tactics.tar.gz"

H4sIAGvtCEIAA+1be5PTRhLnb32KPqi7tTmvI+2Lq02oQAi5owqSHJBKXVHU1lga25OVNWZGsteE
fPfr7hm9vA/OawGVOqtgbevR089f94x6chHnKrZf3fmERxgehQ+Oj/EzjB4ch83P8rgThQfhQXRy
chxFd8IoPH5wdAeOPyVT5VHYXBiAOyM9uvG+j13/kx65t//Lp4+/f/H004yB9gxPjo6us/9JdByt
2T86Okb7h5+Gnfbxf27/11NlAf/NVmB1WuRKZ5BryKcS7r7S6UJlE3jtfOQuvCxGK/h3od7Dvegf
wyB4BnMjF0oXNuXHFzLBJ5HavHj/PsUfeiENHIawksJYEBMNSF7AE53lRqfwvchF8ESbuTaCR54J
lY2NmEmI9Wxe5Ph07zE8+f4JPFmN8MfJURj2h/AauZsbPcE7YSlsMBVZsq/nuZqp9ziqsFbORine
H+tEDmBpVJ5LHBhZACvT8T7eoSYZcSvNLEBSv8k4H8KLFYykzcHIWKcpniKeUJx8KnJQOSpGnyOJ
sVwimVhniSVdmSL7mmiMxAjVQPpD9rRJcHw9higs7x3CswzHwwFQqelqQDpnjaKSLI4U5OJcMoso
R4pOKWa6yHIigpJJooxPjIUyOIzIYiXx4kkYvvjXe9JGLK3VBq1C2hkJq2JQiRTEPxKcp/IUSXtT
wkgLk6B6shw1buE3jAKITiCWaWoHwXKq4inEIkN1gJzNcxTLwFihThLSPpI0UiSK+EhmKmc1CDyH
7mCRKzZmwOqOTvZHqLmsmKH9hvBPtK0tKc9TsUIboAYKS35GN+q5dL5ANINEkoFUJlHehO8HlSVq
oZJCpDBD97LOG84lsjiy0ixEy2hoCiMDYaQT8eD+fZRyrtH86B9eC/hT8YhDeCpQbtL3FOUgIlIR
BRDBUmUZ8Yh6SDVzWz7GGicll+HDyp6hGkh+4pnultmExGCmSHyWZWz0DCVbwUQtZBa02XGCiXSi
0X2nMxZJoy9JWE4lcTVwzzPJ8qGBY5VZz2xhZDIgljOde7vhv0QjI6j03DBnIk3ZYyutsFqDy7QB
nVGlKJMfYIzeie7wbLx2akDkOAoCwta8qSyGGmHOOUrxuTVdQm8kY1FYyRxl8iIPWFGxLtKEBsHg
/4lkXyqLga3GKBmd3kNapiHCGGXmKJzPUdgsL6UhaKo0VXIJH+USRxjCY8cKmcGgB6LaVlD5Z0K2
QZd2mnBOYom/KRIYSZnV9AJboJM501f4yf7AumSVYxgVac4Po+kcgRh9U3rlBmwwYsf7FVk2W2ga
AcGrQDxZyBQJPkW/ygvilR9suNMSozlw3IscddlUPA/FwCFlIknx+ZQvIDprM3MhxoyKLMABlMHB
PD7AxKikhgJvZApTXaurdGEmOlbG5gHqzOGkgwVDw4/InUizqNSBQ7GVlxPWNUA8BhhYDq44lMrI
LHE1RVXONPqJHKMYOYcTIwosEa4taUhw9itzi8oCyiA+EmNSJKcUFMTGRo3IniOMFuKV8YU87DQI
AO7Bz1WAs0YLYwiu6+BGU9/H0L/P4QaTQhiB2UF6dxswDfZQcpy26zqn/PXZj4yKRuaFQZfNG6HB
9zOJ6hk0AoIlnkvkmBWHXwEelSFz5sBUEgAmGj7Qzw98C2AcLs8cNj2ER+7LB2bbX0c37z16VI70
prr9LXz4UGacIZ7tVVcG6wP3h8RSHx4+hOc/vXrlnBz84SVsDPHI03/IWvA3yiwJmp9X3k/UA3cP
J0oj3xXovkkZcoSPdVATSjK2yznaJycvR9/A9IPXvJOguT0N2PPF9F6ApYuFv/bu/d6QniUkAf25
01Pi/Vu4+wP5/104xYKLA+DuH2UIoCPYYd8xymUXVTKymIMtJhOsI3ySEzDROqkTkJ0yXCZyhkkt
J77RjTMs5WIuPKrMiO5jlzgMZx9I1TnJ53As1uivVBI920PvjKfoPAg6GgghioxKIR7e4SwXfFjE
WR8pjRso9LBGWKBviwni8XgduQi5RypVOY/czortfFhdF8FCGCWpKBmTIWFCRQVVV8DuGwsrGVo1
XifeSov1lMtKWFtyeu4TAVfreIV7zdUYjsBIMZY3pQqovjR5XWG0cEhMDEVxBZnMBknJD/m8jsGp
KIYJTYmJUSri8/2RvuABKBUx7URLm+3hpyJjkHGoOu3hU4G8EFRm9BtMeNCSZMzzTC8tTPWy0hqe
NqsqQwYUdUP4rsgHXFE5+gMqcr260OmxRqfKhX5lsSxHckWE85bAeYvLGWj+IPhOj4av8IGRxttn
jyZY0adDVHjwpSc6u+PKo5z/+88z8rCh6Xaqe/P8/yA6itz6T3hyEB0cn+D9hyfh8W7+/zmOOneh
4b8ijNu7lM/QH/aCIE4RwuA13lZOIr/hX6env+BTp6f0/QmCAJcd9OMSNNZzDgJwqnrXJmAOYpaO
BEEYV/XXT72umrFRHabGSiZMpIfzg7lWWHkhpLtZJk4IyrxZTgunRYYFr6UZti4MYK7P9/f3uB6u
67Al8+bygyTUQ0BVYxLn235ZV5ESz6ri6p7jrkpgrmqc1xNUWV9b6WIP2RmL2NfbngLzN5JjKlv9
XHIIrzTcjcC+K0gCLuzuwkyKUoFYj6EZraewIpG4gPKpoEpphrKvznjRQpbkxAIRW2CKGNTP8xjD
wJ9ojww9PfJLQH2+wSW6M/QhkfaqWofqrkGrGAxHYRRFZ1Hrj68DNyQUhV0RQkodEYrCrghFZ2FX
hNqK2oZQS1FbEWoqajtCDUVtS6hS1NaESkVtT8grqgNCTlGdECJFdUMIKXVEKApLQh6xDjxi0SIJ
rVNiYqGpVb3aRBhHq3I4ESyo0tUNROzDDfzgFO4Sqt0GjK6gg0VTN3SQ0DV0NiVEjrMhglxHpy3d
FnRa0m0hWFu6bRhqSrctnVK6bQWrpNuaIS9dJ3SiMLydYGEL7LfUdJvYloJVxG5psfAWWfr6GNss
k33EpdfQfmMU2rxquCHoN8qsH4uxdvbZmFC4cRVzA0MNYtvHWHhVNjzcKhtuGqldZbGw2yzWkSOG
3Wafjjw67DZrdIT2YQPtbwv3HcB0m9jWMN0BvLaI3VJFTUjswIuaxDrAxQ7wLLwWz44+M55tPrG/
AYa6ShsNYl0EaxhuX5pdirGtQuz2tWt4nUNv6c+XZpkX5TyzXBlrOKCpehHYFUW6FCtbeiS3FpFT
ekqeiprNZKLca0cxpmYoJkSvbjZeagtvMXe7fj2qRW3rRZuS2v/gcFev/oWbzydvWCJrUtt+HSls
z5c2X5AMr5nj3oqlJrUOlrbCy3M4ioND6GkDhxcHfepGyUU2SeXNmOwiQFAMbRiXtS9uOXmv7b5u
/Futt2ym6RuXWzYJkJvXW9a98dbrLVdZfrM5QRclOGe8rkrwNlfbzgm6KsErrjqZE6xn9XvwI1VL
ci9NW70XrS4q127rGjzcqzbVaGfwdKoOKO3fi5Xv8mAi3ZtAS229vuOkeW1Ztvrwe7ZGQxu35cnE
8WRjI/J4yl0ezAD1GwyIxlQspOtp9J2MntgcoQfTJ70uRMns/n7O7T7U5WPrxg/KszbX1AHkukM8
A8ONEyzqt/1nTdOPU6shnsr4vOonXmpzbmvlVD0jiRwLZBN5anWzbcBRe2jqt1ZZ4UdwDcxGZAnZ
urSjHaIvgMhzGtJ3AcmLqaDXqQtZGYjeW6qZbHSTylSNpG+OSnUsiO2RTKn1hJr7Cu9aA9cqV75V
9K2sThPUFu1LnatfCbONuQvS2coT4feVcVzQ6EP4aUx9oobcgvksu2e4aYa7X2bUVeReFs+cOkvb
cPH2HOxUzEm2qsGT0xO3lCLD5YvPmyxxbYbqaMrgi+ErUKohyuGnF6WL9dLwqrWKNVGOPpMot5+n
1CSuxHwS47Apxssm8/lSQ4qIk08Zk/DnxmKEnYjhUOtKy1ZiMHhJ47PCr1TPCYsxT03kDsZcmz9J
oucUrOW83HJX2qai8XwN/55V3247k2yQ4G81HWoEpf9fug/nSx25U1XZ/9V16xcfH9n/dfjgwO3/
io7Dk4Mj2v91cIyXd/1fn+HwXV3O+tzsRNWe9wafjHm7j+/nL7dE+H09lLon0rh29XCvcSNveuHq
xaHA1xCtX/YbBjxKEDo8ffHz6/8M4Idfnj+HhxAOILz4AQ/XUf9Sxhq5cZ3vOL/kRnHqQJ7rnChy
apB1P9jabh+mcWnHz+PWpg/DQ5Qy0jg9P1Af1DhwJVBzS0xrn0P7fp7P+r7iuVHUKa2ZwkzzrrrL
G2xIA4xfLNlDiFB+PNXorceTj40RK4dsFxGXmf03pC/fDO9U9cRIqqUEte5Xe76oTXpQb3bxbcN2
LmPul2uxQc1sKlOkVPVe9sruf2+fdu8+VC3tQzTB2VpjP2P1o5IAf7pTl4jMTZHJtcd7frvAZaLc
wb/baPGn2GgBFAAL2ofgA9mtw5P3Sd7f2N57Vnfs+52owm29cRvTqiBs7/gqHaD250vbuiqjbORo
sHZuaCTtFoXfve3AR8ff3MIs/AWBC/4ISvW4eHS7WXmGuibrVTNuzydtVb0ipHw99lLOU0XTrcbu
PdpIoaTbl0H7SHnhjV6I8EZc9jn6Rd4c67SYZSVU0qYtV571wuHwsD9UGQnZe/O2X3mpHdDDpa++
cesvCFFUqLlP/OI+Q4IuXglz18vzkT8flefL39HbOiIwr9gPlU9y1D6kvaEWvvkGjuA+cdG6zBf4
PvzMMbwtLVX06nXy2lUBahXiuWGRqXdNMHnpIoBUUhFKfNboTbVR72nLbOqXOTDeRMobLBcqlvu0
j1f0m8armWES/UrD0XGl4rBPrnTh/U99gHcDgwKrYaIWM530jvpfw4UHAw+gb9RbEvUd/B3M/aPK
2ViKDfN/Wf8tp5p3G32B+i+Mjnz9h/cdHx1w/ffgwa7++xzH5b1rHW9e+9IC7o7dsTt2x+7YHbtj
d+yO3bE7quO/6N9XnABQAAA=
------=_Part_2860_15554074.1107881501231--