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!
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...
# last_move_by - true for second player
# false for first player
def play( state, last_move_by, possible_moves )
possible_moves.delete_if { |m| state & m != 0 }
if state != END_GAME
possible_moves.each do |m|
play( state | m, ! last_move_by, possible_moves.clone )
end
elsif last_move_by # last move was by second player
$f += 1
else
$s += 1
end
end
play( NEW_GAME, true, POSSIBLE_MOVES )
puts "Wins of first == #{$f}\nWins of second == #{$s}",
"#{$f < $s ? 'First' : 'Second'} player is bounded to win"
Well, this quiz is tougher than it seems, isn't it? <laughs>
I played with it a little last night before I realized I was going about it all wrong. I'll show what I did wrong and leave it to Bob to educate us about how to do it right.
My problem is 100% efficiency. I was hoping to be able to generate the entire move tree for this game, expecting that the single piece and the small board might make this achievable. I tried to avoid repeating positions using rotation and mirroring of the board.
Unfortunately, I was lazy and didn't want to deal with binary math for rotation and mirroring, so I used Strings. I'm sure this is horribly inefficient. I was hoping to simply generate the move tree once, Marhsal it, and work off of that in the future. But after letting my tree builder run for hours, I had nothing to show for it.
Clearly, it's not the right approach. I should have been less lazy and got the data structure right to begin with. And the low number of positions probably makes the tree overkill.
Files in the zip:
tactics.rb -- My flawed library for dealing with positions.
play_tactics.rb -- A simple game implementation, with the opponent making random moves.
build_move_tree.rb -- A good reason to purchase some supercomputer time.
"direct proportion" means that the numbers should just increase with the bigger board, right? When I run your program, I get:
Wins of first == 64730
Wins of second == 55728
Second player is bounded to win
The first player has more wins. Why favor the other guy?
James Edward Gray II
···
On Feb 6, 2005, at 5:45 PM, 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).
Well, this quiz is tougher than it seems, isn't it? <laughs>
Unfortunately, I was lazy and didn't want to deal with binary math for rotation and mirroring, so I used Strings. I'm sure this is horribly inefficient. I was hoping to simply generate the move tree once, Marhsal it, and work off of that in the future. But after letting my tree builder run for hours, I had nothing to show for it.
I tried to build the tree too, I think there are 2^16/8 possible boards but my program needed more than a minute to generate the tree (and I thought marshaling it is kinda cheating ;))...
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).
"direct proportion" means that the numbers should just increase with the bigger board, right?
Something like that.
It is still unproved so it is just a guess.
When I run your program, I get:
Wins of first == 64730
Wins of second == 55728
Second player is bounded to win
The first player has more wins. Why favor the other guy?
Hmmm... As I understand "is bounded" means "has less possibilities".
My program shows that the second player wins more rarely than
the first (in _all_ possible games on the 4x2 board).
So it has less possibilities to win, so it is bounded to win.
Thanks for clearing it up for me. I just misunderstood the language.
James Edward Gray II
···
On Feb 9, 2005, at 10:25 AM, Sea&Gull wrote:
Hmmm... As I understand "is bounded" means "has less possibilities".
My program shows that the second player wins more rarely than
the first (in _all_ possible games on the 4x2 board).
So it has less possibilities to win, so it is bounded to win.
Your understanding of "is bounded" is technically/grammatically correct
but will tend to confuse people as there is an (American) idiomatic
expression: "bound to win" which means likely (or almost sure) to win.
So '"is bounded" to win' and 'bound to win' have essentially opposite
meanings.
I think saying something like "player two is less likely" to win is more
clear.
Your understanding of "is bounded" is technically/grammatically correct
but will tend to confuse people as there is an (American) idiomatic
expression: "bound to win" which means likely (or almost sure) to win. So '"is bounded" to win' and 'bound to win' have essentially opposite
meanings.
Ah! Thanks for clarifying.
I lost sight of that idiomatic meaning
I think saying something like "player two is less likely" to win is more
clear.
Not really per se. It's just that (in past lives) I have dealt with a
lot of non-native english speakers in technical situations and learned
(somewhat at least) some of the problems with language. (Also,
fortunately, found humor in some of them.
Not really per se. It's just that (in past lives) I have dealt with a
lot of non-native english speakers in technical situations and learned
(somewhat at least) some of the problems with language. (Also,
fortunately, found humor in some of them.
Me too Some years:) ago I have dealt with some native english
speakers learning russian. It was interesting to see how
the instrumentalities of the analytic language (english) may be
expressed by the instrumentalities of the other-type language (russian).
BTW, it's much harder for native english speakers to lern russian
than for russians to learn english
