# \[QUIZ\] Solving Tactics (#18) **URL:** \ **Category:** ruby-talk\ **Created:** [4 February 2005 13:58 UTC](https://rubytalk.org/t/quiz-solving-tactics-18/16250 "2005-02-04T13:58:58Z")\ **Posts on this page:** 12\ **Page:** 1
**Author:** ![James\_Edward\_Gray\_II](https://avatars.discourse-cdn.com/v4/letter/j/ea5d25/32.png) [@James\_Edward\_Gray\_II](https://rubytalk.org/u/James_Edward_Gray_II)\ **Post date:** [4 February 2005 13:58 UTC](https://rubytalk.org/t/quiz-solving-tactics-18/16250/1 "2005-02-04T13:58:58Z")
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/](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! ---
**Author:** ![Sea\_Gull](https://avatars.discourse-cdn.com/v4/letter/s/e480ec/32.png) [@Sea\_Gull](https://rubytalk.org/u/Sea_Gull)\ **Post date:** [6 February 2005 23:45 UTC](https://rubytalk.org/t/quiz-solving-tactics-18/16250/2 "2005-02-06T23:45:12Z")
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" ---
**Author:** ![James\_Edward\_Gray\_II](https://avatars.discourse-cdn.com/v4/letter/j/ea5d25/32.png) [@James\_Edward\_Gray\_II](https://rubytalk.org/u/James_Edward_Gray_II)\ **Post date:** [8 February 2005 17:18 UTC](https://rubytalk.org/t/quiz-solving-tactics-18/16250/3 "2005-02-08T17:18:44Z")
Well, this quiz is tougher than it seems, isn't it? \ 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. ☹ James Edward Gray II [nonsolution.zip](https://rubytalk.org/uploads/short-url/sQHnZ6gsaolVF4rua7UiSffWY7Z.zip) (1.74 KB) ---
**Author:** ![James\_Edward\_Gray\_II](https://avatars.discourse-cdn.com/v4/letter/j/ea5d25/32.png) [@James\_Edward\_Gray\_II](https://rubytalk.org/u/James_Edward_Gray_II)\ **Post date:** [9 February 2005 15:23 UTC](https://rubytalk.org/t/quiz-solving-tactics-18/16250/4 "2005-02-09T15:23:43Z")
"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). ---
**Author:** ![Malte\_Harder](https://avatars.discourse-cdn.com/v4/letter/m/76d3ee/32.png) [@Malte\_Harder](https://rubytalk.org/u/Malte_Harder)\ **Post date:** [9 February 2005 13:19 UTC](https://rubytalk.org/t/quiz-solving-tactics-18/16250/5 "2005-02-09T13:19:05Z")
James Edward Gray II wrote: > Well, this quiz is tougher than it seems, isn't it? \ > > 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 ---
**Author:** ![Sea\_Gull](https://avatars.discourse-cdn.com/v4/letter/s/e480ec/32.png) [@Sea\_Gull](https://rubytalk.org/u/Sea_Gull)\ **Post date:** [9 February 2005 16:25 UTC](https://rubytalk.org/t/quiz-solving-tactics-18/16250/6 "2005-02-09T16:25:10Z")
James Edward Gray II 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). > > "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"? > **···** > > > On Feb 6, 2005, at 5:45 PM, Sea&Gull wrote: > > -- >    s&g ---
**Author:** ![James\_Edward\_Gray\_II](https://avatars.discourse-cdn.com/v4/letter/j/ea5d25/32.png) [@James\_Edward\_Gray\_II](https://rubytalk.org/u/James_Edward_Gray_II)\ **Post date:** [9 February 2005 16:37 UTC](https://rubytalk.org/t/quiz-solving-tactics-18/16250/7 "2005-02-09T16:37:11Z")
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. > > > > Or I misunderstand the meaning of "is bounded"? ---
**Author:** ![Ruth\_A\_Kramer](https://avatars.discourse-cdn.com/v4/letter/r/57b2e6/32.png) [@Ruth\_A\_Kramer](https://rubytalk.org/u/Ruth_A_Kramer)\ **Post date:** [10 February 2005 15:36 UTC](https://rubytalk.org/t/quiz-solving-tactics-18/16250/8 "2005-02-10T15:36:56Z")
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 > **···** > > On Feb 9, 2005, at 10:25 AM, Sea&Gull wrote: > > > Or I misunderstand the meaning of "is bounded"? ---
**Author:** ![Sea\_Gull](https://avatars.discourse-cdn.com/v4/letter/s/e480ec/32.png) [@Sea\_Gull](https://rubytalk.org/u/Sea_Gull)\ **Post date:** [11 February 2005 14:05 UTC](https://rubytalk.org/t/quiz-solving-tactics-18/16250/9 "2005-02-11T14:05:12Z")
Ruth A. Kramer wrote: > > 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. 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? 😉 > **···** > > > On Feb 9, 2005, at 10:25 AM, Sea&Gull wrote: > > -- >    s&g ---
**Author:** ![Ruth\_A\_Kramer](https://avatars.discourse-cdn.com/v4/letter/r/57b2e6/32.png) [@Ruth\_A\_Kramer](https://rubytalk.org/u/Ruth_A_Kramer)\ **Post date:** [11 February 2005 15:48 UTC](https://rubytalk.org/t/quiz-solving-tactics-18/16250/10 "2005-02-11T15:48:13Z")
Sea&Gull wrote: > 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 ---
**Author:** ![Sea\_Gull](https://avatars.discourse-cdn.com/v4/letter/s/e480ec/32.png) [@Sea\_Gull](https://rubytalk.org/u/Sea_Gull)\ **Post date:** [11 February 2005 17:45 UTC](https://rubytalk.org/t/quiz-solving-tactics-18/16250/11 "2005-02-11T17:45:11Z")
Ruth A. Kramer wrote: > Sea&Gull wrote: > > > 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. 😉 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 🙂 > **···** > > -- >    s&g ---
**Author:** ![Ruth\_A\_Kramer](https://avatars.discourse-cdn.com/v4/letter/r/57b2e6/32.png) [@Ruth\_A\_Kramer](https://rubytalk.org/u/Ruth_A_Kramer)\ **Post date:** [11 February 2005 19:45 UTC](https://rubytalk.org/t/quiz-solving-tactics-18/16250/12 "2005-02-11T19:45:33Z")
Sea&Gull wrote: > BTW, it's much harder for native english speakers to lern russian > than for russians to learn english 🙂 That's nice to hear--maybe I'm not as dumb as I think I am. 😉 Randy Kramer