[QUIZ] Solving Tactics (#18)

[Ruby Quiz]

The three rules of Ruby Quiz:

1. Please do not post any solutions or spoiler discussion for this quiz until
48 hours have passed from the time on this message.

2. Support Ruby Quiz by submitting ideas as often as you can:

http://www.rubyquiz.com/

3. Enjoy!

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

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!

 

[Sea&Gull]

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...

###############################################################

#!/usr/bin/ruby -w

NEW_GAME = 0b0000_0000
END_GAME = 0b1111_1111

POSSIBLE_MOVES = [ 1, 2, 3, 4, 6, 7, 8, 12, 14, 15, 16,
17, 32, 34, 48, 64, 68, 96, 112, 128,
136, 192, 224, 240 ]

# wins_of_first and wins_of_second
$f = $s = 0

# 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"

 

[Malte Harder]

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 )...

Up to now I had no time to optimize it ....

Malte

 

[James Edward Gray II]

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? 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

 

[Sea&Gull]

"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.


Or I misunderstand the meaning of "is bounded"?

 

[James Edward Gray II]

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.


Or I misunderstand the meaning of "is bounded"?

Thanks for clearing it up for me. I just misunderstood the language.

James Edward Gray II

 

[Ruth A. Kramer]

Or I misunderstand the meaning of "is bounded"?

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.

Out of curiosity, what is your native language?

regards,
Randy Kramer

 

[Sea&Gull]

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.

Ok, thanks

Out of curiosity, what is your native language?

Russian.
You are interested in linguistics?

 

[Ruth A. Kramer]

Russian.
You are interested in linguistics?

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. ;-)

regards,
Randy Kramer

 

[Sea&Gull]

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