5
$\begingroup$

This is a follow-up to my first Dots and Boxes question. It is just a little bit harder than the first one. Each one I post will be a bit harder than the previous one, and they will all be from games I have recently played.

In the following game of Dots and Boxes, it is your move.

enter image description here

Your opponent is a computer who will play perfectly. What is the best move, and why?

$\endgroup$
  • 1
    $\begingroup$ Dots and Boxes is a lovely strategy game, and I hope we'll see plenty more questions about it on this site! In anticipation of such, I've created a [dots-and-boxes] tag. $\endgroup$ – Rand al'Thor Mar 20 '15 at 1:56
3
$\begingroup$

The player can't win. Analysis to follow.

Interesting moves

Here I've marked the "safe" moves in blue. We will call them 1, 2, and 3 counter-clockwise starting from the left. The sacrifices I have marked in green. Let us call them A above and B below. Finally I have marked a move inside the lower right square in red.

First to address the red move.

Any move inside the square is bad:
Assumption - It is determinable whether the first person to make a move outside the square will win or lose.
Making a move inside the square gives the opponent the opportunity to decide who makes the first move outside the square. This is because they can either complete all the boxes in the square then move outside, or continue our line inside the 2x2 square to split it into 2 2x1 squares. In the latter case we are forced to make the first move outside the square (after completing the four boxes). Since our computer opponent is perfect, it will know whether it wants to make the first or second move outside, and will choose accordingly. We cannot give the computer that choice.

Which move to make.

We need to note that 2 is mutually exclusive with each of 1 and 3. Also, A and B are mutually exclusive. Any non-safe, non-sacrifice move will be as bad as the red move. Finally, A has interactions with our three safe moves. If A is played: with 3 on the board, 1 and 2 become starts to long chains (bad), and without 3 on the board 1 and 2 become sacrifices.

Unfortunately, all this combines in a way that appears bad for us.

If we make a move in one of the safe lines, the computer can play A leaving us with no good moves like so:
case 1: 1, A, complete the squares...in doing so we have played 2 and have no more valid moves (2 invalidates 3, and A invalidated B)
case 2: 2, A, complete the squares then no more valid moves (likewise 2 invalidates 3, and A invalidates B)
case 3: 3, A, complete the square then no more valid moves (A invalidates B, and 3 + A means 1 and 2 are starts to long chains)

So what if we start with a sacrifice? The computer can follow with a safe that leaves no good moves.
case A: A, complete the square then 3, no good moves (A invalidates B, and 3 + A means 1 and 2 are starts to long chains)
case B: B, complete the squares then 2, no good moves (B invalidates A, and 2 invalidates 1 and 3)

We're left with no way to win this, but the best move is probably 1 or 2 as that forces the computer to sacrifice 2 squares.

$\endgroup$
  • $\begingroup$ the 2nd or third line in the first row are both correct answers. you're on fire today, dmitch $\endgroup$ – JLee Mar 20 '15 at 3:23
  • $\begingroup$ @JLee Am I really? Both of these look like they may be wrong. $\endgroup$ – dmitch Mar 20 '15 at 4:23
  • $\begingroup$ When I played against my program, for all the blue lines in your answer, the computer responded with the top green line. Seems like the best we can do is 10. The computer will at least get 15. $\endgroup$ – Raziman T V Mar 20 '15 at 7:34
  • $\begingroup$ @Crazyiman You are right and dmitch you are correct in changing your answer. I wasn't sure who to mark as the accepted answer, but since Crazyiman found it first, I went with him. My apologies for getting this wrong. From now on I will check the answer with a computer first. $\endgroup$ – JLee Mar 20 '15 at 12:13
  • $\begingroup$ @JLee I wrote my edit 4 hrs before his answer and also before his comment $\endgroup$ – dmitch Mar 20 '15 at 17:49
1
$\begingroup$

The best you can win is 10 boxes. The computer always wins by getting at least 15 boxes.

enter image description here

In this image, playing any of the red edges gives you 10 boxes if the computer plays optimally. If you play the green edge, you get only 9 boxes. Playing any of the blue edges gives you even less, only 8.

The computation was done using the same code I used for the previous question. The computation was made easier since there are only 30 edges instead of 32.

$\endgroup$
  • 1
    $\begingroup$ I didn't write this in my analysis but without fully enumerating everything, I figured the computer would play 3 sacrifices and give us the entire lower right square for a total of $3*2 + 4 = 10$ boxes to us and the remaining 15 to it. Thank you for this proof. $\endgroup$ – dmitch Mar 20 '15 at 18:03
  • $\begingroup$ @crazyiman Wouldn't move number 2 from dmitch's answer get you 12 instead of 10? Seems like the computer would concede you a block of 2, you would concede a block of 9, he would concede you a block of 10, and you would concede the corner square of 4. $\endgroup$ – Trenin Mar 24 '15 at 15:08
  • $\begingroup$ @crazyiman This would be the same move as JonTheMon's answer. $\endgroup$ – Trenin Mar 24 '15 at 15:14
  • $\begingroup$ You are assuming greedy play. When you concede a block of 9 to the computer, it will just take 7 out of those and give you a block of 2, instead of 10. $\endgroup$ – Raziman T V Mar 24 '15 at 15:24
0
$\begingroup$

For a greedy strategy by both you and the opponent,

enter image description here

will set you up for the first chain (of five).

$\endgroup$
  • $\begingroup$ If you make that move, where do you think the computer will move? $\endgroup$ – JLee Mar 20 '15 at 0:33
  • $\begingroup$ One of the 3 spots to the left, i'd guess, to limit you to 2 boxes. $\endgroup$ – JonTheMon Mar 20 '15 at 1:18
  • $\begingroup$ Maybe you are not realizing that you must always go again immediately after you have made a box. $\endgroup$ – JLee Mar 20 '15 at 1:33
  • $\begingroup$ Yes, then you give the computer the 3 boxes, computer gives you 4, you give the 6, computer gives you the 10. Or, if you're leaving 2 spots open for each chain, you leave 8 boxes open but get the rest. $\endgroup$ – JonTheMon Mar 20 '15 at 1:35
  • 1
    $\begingroup$ Ok, I see how you are thinking about it now. You are missing a crucial strategy, not just for this board, but for all boards. $\endgroup$ – JLee Mar 20 '15 at 1:39

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.