8
$\begingroup$

Two bosses of different companies take turns delivering long speeches. Every speech much “claim” at least one unused square by uttering the corresponding buzzword(s) in the table below. Victory is obtained by forcing the opponent to claim three squares in a row, horizontally vertically or diagonally. If all squares are claimed and neither boss gets three in a row then the game ends in a draw.

(1) What is the proper result with perfect play on both sides?

(2) Does the result change if every speech must claim exactly one square? This is probably a simpler problem, but not really in the spirit of the game!

NOTE: this is an example of a zero-sum game. For those who are not in the loop, information on Buzzword Bingo is available at https://en.wikipedia.org/wiki/Buzzword_bingo – or if you are proactive you should be able to guess the rules. Would your answer to the above questions be scalable to larger grids?

enter image description here

$\endgroup$
  • $\begingroup$ Isn't this thing the same as tic-tac-toe??? $\endgroup$ – Lakshay Sura Jul 6 at 11:29
  • $\begingroup$ it's (1) misere, play to lose and (2) it is possible to take multiple squares on your turn $\endgroup$ – happystar Jul 6 at 11:49
  • $\begingroup$ Ok but does the part 2 implies that we have to take one square in each move???? $\endgroup$ – Lakshay Sura Jul 6 at 12:48
10
$\begingroup$

So, we are playing misère Tic-tac-toe with the option of taking more than one turn in a row. Seems quite interesting, so let's take a stab at it.

The flow of the narrative here is a bit messy, because the answer was not all written in one go. Since a full rewrite would be too time consuming, I've added some chapter breaks to give at least some structure to the text. Here's what's going to happen:

  1. Getting acquainted with the game, figuring out the best starting move
  2. Break down what we learned as explicit heuristics
  3. Analyse a particularly likely-seeming 4-move position
  4. Using that result, MiniMax our way back to the first move
  5. The Conclusion

So, here we go.


Getting acquainted with the game, figuring out the best starting move

At first glance, it seems that the centre must be avoided at all costs. Indeed, if you start at the centre, the opponent has a "mate-in-2":

enter image description here

(The starting player can play a second 3 at one of the 4s himself, but since he cannot take both, the result is still the same.)

Similarly, playing in a corner seems questionable:

enter image description here

Playing move 3 at either triangle instantly loses to the opponent leaving only the other triangle, and picking any other spot creates another unplayable square, which the opponent can leverage for an eventual win:

enter image description here enter image description here

Taking any additional squares in combination with these bad squares is only going to make things worse, so the best starting move must be to

play on a side. (Playing any two sides on the first move seems to lose.)

This agrees with the intuitive notion that you want your plays to create as few potentially losing connections as possible, and the sides are the only squares that are not on a diagonal.


Break down what we learned as explicit heuristics

From here the variations branch a bit, so let's establish some important heuristics first:

  1. In general, sides are better than corners, which are better than the centre. This is because of the number of possible losing lines going through the squares.
  2. Making an "open 2" (so that there's an empty square that only the opponent can play) is generally bad
    2.1. Conversely, forcing the opponent to make an "open 2" is good
  3. Blocking is mutual: if you block some of your opponent's lines, some of your lines are already blocked.
    3.1. Aggressive moves often leave a counter-attack possibility
    3.2. It's easier to defend than it is to attack.
  4. Playing several squares at once is generally bad unless you have a definite plan in mind.

Analyse a particularly likely-seeming 4-move position

In light of these, let's examine the most likely opening:

enter image description here

(If 3@4, then 4@3 wins, so this is the only plausible 4-sides opening.)

Looks like playing the 5th move in the "most blocked" corner gives a draw here:

enter image description here enter image description here

(Somewhat surprisingly, 5 at the centre also seems to draw.)


Using that result, MiniMax our way back to the first move

So unless we can find a more aggressive opening for the second player, the whole game is a draw. Let's list all the single-move candidates for 4:

enter image description here

Here are some examples of the strongest lines for both players:

enter image description here enter image description here enter image description here enter image description here enter image description here

So, this too seems to be a forced draw. Is there any way to play 2 in order to avoid it? Playing any side just rotates the position, playing in the centre loses (see first spoiler block), playing in a far corner loses (see second and third spoiler blocks) and playing in a near corner is a draw:

enter image description here enter image description here


The Conclusion

So unless I made a mistake somewhere, with optimal play from both sides

the game is a draw.

(Answer to question 2: with only one move allowed per turn, the result is the same.)

| improve this answer | |
$\endgroup$
  • $\begingroup$ By having mate in 2(which is a phrase I couldn't completely understand), aren't our opponent actually losing?? Didn't read full answer as I lost here in the illustration only. $\endgroup$ – Lakshay Sura Jul 6 at 12:56
  • $\begingroup$ @LakshaySura I edited the first diagram to include moves 3 and 4 too, the result should be easier to see now. $\endgroup$ – Bass Jul 6 at 13:07
  • $\begingroup$ That is really clever situation but doing so wouldn't the second player be creating a column and a row. Or are you really focusing on the phrase "Victory is obtained by forcing the opponent to claim three squares in a row, horizontally vertically or diagonally." especially the forcing part?? $\endgroup$ – Lakshay Sura Jul 6 at 13:10
  • $\begingroup$ @LakshaySura Huh? The second player doesn't have a 3-in-a-row in any of the diagrams, and since it's the starting player's turn, he won't be making one, either. $\endgroup$ – Bass Jul 6 at 13:16
  • $\begingroup$ Oh I really got it now pity that I am so confused. Thanks @Bass will work ahead some time later. By the way,+1 $\endgroup$ – Lakshay Sura Jul 6 at 14:23
1
$\begingroup$

Partial answer:

Second player cannot lose.

Because

The game is symmetric except for the center. First player taking the center as a first move is a losing move, as Bass has proven. Second player can all of mirror first player's moves radially except for the center. Furthermore, if a strategy exists where first player (from a symmetric position) benefits by taking the center, second player could have pre-empted that strategy by taking the center in addition to another space in their previous move.

Because of this,

We only need to look at strategies for second player.

Continuing from Bass's partial answer.

Before I get into the lines, I'll introduce to more critical boards.

Position A:

   | X |   
-----------
 X |   |   
-----------
   | O |   

Position B

   | X |   
-----------
 O |   |  
-----------
   | X |   

These positions are important because

They are winning boards for O!
In position A, O plays to the lower right corner. No matter which move X plays from that position, O can force them into completing a row.
In Position B, O plays to the right side, then plays back all of X's moves, rotated 90degrees, until X is forced to take the center and loses.

This means that

X loses if they play on two side squares.

I believe that this can be combined with Bass's answer to create a complete winning strategy for player 2, but I haven't exhaustively proven that yet.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Position A seems drawish (not certain if it's a draw, but haven't found anything) if it's O's turn to play. Playing at the lower right, as you suggest, leads to a win for X, who can take the top right and the right side, leading to the same situation (with colours reversed) as the second picture in the third spoiler block in my answer. $\endgroup$ – Bass Jul 6 at 23:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.