6
$\begingroup$

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$
  • 3
    $\begingroup$ The best move is not to play. How about a nice game of chess? $\endgroup$ – Nick2253 Mar 19 '15 at 20:44
5
$\begingroup$

enter image description here
Playing the first move in any of the blue spots will let you gain 8 squares with further optimal play, whatever the computer does. On the other hand, playing in any of the red spots will only let you win 6 squares with further optimal play.

Since there were exactly 32 empty spaces, I tried to push the ability of my computer and enumerate the best possible move starting from all $2^{32}$ states. For each state, the code finds the maximum number of squares you can get more than your opponent.

In a few minutes, the code found that the best result is -9. That is, whatever you do, you cannot win the game. Here is the code:

const long long lim=1ll<<32;
char best[lim];
//best[i] is the maximum number of extra squares you can win more than your opponent starting from state i
//A state is represented by a 32-bit bitmask. Edge i (defined below) has been already played iff bit i is 1

int main()
{
  //Number the empty positions from 0 to 31 from top to bottom, breaking ties from left to right
  //Every edge borders at most 2 boxes, and because of the state of the board, there exist at most 2 other edges whose existence is necessary to fill those boxes
  //Essentially, Adding edge i results in a box for you if match[i][0] and match[i][1] were already filled; and another box for you if match[i][2] and match[i][3] were already filled
  //if match[][] is 32 it means that current edge is at the boundary of the box and there is only one neighbouring box
  int match[32][4]={
    { 5, 0,32,32},{ 6, 1,32,32},{ 7, 2,32,32},{ 4, 3,32,32},
    { 3, 4, 8, 4},{ 0, 5,10, 5},{ 1, 6,11, 6},{ 2, 7,12, 7},
    { 4, 8, 9, 8},{ 8, 9,13, 9},{ 5,10,14,17},{ 6,11,15,11},
    { 7,12,15,18},{ 9,13,16,20},{10,17,32,32},{11,15,12,18},
    {19,16,13,20},{10,14,21,22},{23,18,12,15},{16,19,23,19},
    {25,20,13,16},{17,22,32,32},{24,22,17,21},{18,23,19,23},
    {22,24,26,30},{20,25,28,25},{29,26,24,30},{28,27,31,27},
    {25,28,27,28},{26,29,32,32},{24,26,32,32},{27,31,32,32}
  };

  for(long long i=lim-2;i>=0;i--)
  {
    best[i]=-25;
    for(int j=0;j<32;j++)
    {
      //If jth edge has already been played, you cannot play it at this move
      long long cur=(1ll)<<j;
      if((i&cur)!=0)continue;

      //Check how many boxes are filled by the current move
      long long mask=i^cur;
      int cnt=0;
      if((mask&(1ll<<match[j][0]))!=0 and (mask&(1ll<<match[j][1]))!=0)cnt++;
      if((mask&(1ll<<match[j][2]))!=0 and (mask&(1ll<<match[j][3]))!=0)cnt++;

      //If no boxes were filled in current move, you pass to opponent and they will do their best move
      //If at least one box was filled, you have to make another move
      char thismove;
      if(cnt==0)thismove=-best[mask];
      else thismove=cnt+best[mask];

      //Does playing this edge do better than any previously seen edges?
      if(thismove>best[i])best[i]=thismove;
    }
  }

  //Now let us consider the moves from the empty board
  //Playing edge j, the best you can do is -best[1ll<<j] since no box will be filled directly and the opponent will do their best
  for(int j=0;j<32;j++)
  {
    long long mask=(1ll)<<j;
    char thismove=-best[mask];
    printf("%d %d\n",j,(int)thismove);
  }
  printf("Best : %d\n",(int)best[0]);
  return 0;
}
$\endgroup$
  • 1
    $\begingroup$ There is an error in your code, because this position is a win for the next person to make a move. This is from an actual game that I played, and I won by a large margin. Maybe you are making some assumptions with your code that aren't accurate. I am now beginning to realize that this question requires someone to be very familiar with the game. $\endgroup$ – JLee Mar 19 '15 at 16:40
  • 1
    $\begingroup$ I am using an exhaustive search, so I am not making any assumptions I can think of. The code could be erroneous though, and I will be very grateful if you point any bug out. If you wish, I can modify this code so that you can play as player 1 against the computer. $\endgroup$ – Raziman T V Mar 19 '15 at 16:43
  • 1
    $\begingroup$ I have added comments so you can understand what is going on better. I do not know any general strategy for the game, which is why I did the full enumeration. Looping through every move does work since we know that both players are playing optimal. At each stage, you have only certain options. This turns the box to another state, from which if both players play optimally, the outcome is predetermined. Thus dynamic programming works, and it is a common technique used to figure out what happens in two player games. $\endgroup$ – Raziman T V Mar 19 '15 at 16:58
  • 1
    $\begingroup$ if no one answers this correctly in the next 2-3 days, I will post the answer, and then, we can play out the rest of this game with me going first, and see if you can supply moves (from a computer or whatever source) which will lead to a win. $\endgroup$ – JLee Mar 19 '15 at 17:07
  • 2
    $\begingroup$ You are right. I will check every problem like this from now on with a computer program beforeI post it! $\endgroup$ – JLee Mar 20 '15 at 12:10
4
$\begingroup$

Most likely you wish to avoid connecting any dots that would allow your opponent (computer) to place a box. As such, you're left with individually choosing one of the following possibilities (marked with red):

enter image description here

All other possibilities will render a box for the opponent.

Possible play sequences are between the player P and computer C are:

  • P draws 1:

    C draws 3 or 4, since 2 would lead to a string of boxes for P;

    • C draws 3 would leave P with 4 (good outcome for P);
    • C draws 4 would leave P with 3 (good outcome for P).
  • P draws 2:

    • C draws 4 (bad outcome for P)
  • P draws 3:

    C draws 1 or 4, since 2 would lead to a string of boxed for P;

    • C draws 1 would leave P with 4 (good outcome for P);
    • C draws 4 would leave P with 1 (good outcome for P);
  • P draws 4:

    C draws 1 or 2 or 3;

    • C draws 1, leaving P to draw 3 (good outcome for P);
    • C draws 2, leaving P with no obvious choice (bad outcome for P);
    • C draws 3, leaving P to draw 1 (good outcome for P);

Summarizing these options and a perfect C-player (albeit greedy, perhaps), P drawing either 1 or 3 would be the best next move.

The above strategy seems somewhat greedy from the opponent, but it also seems logically best.

$\endgroup$
  • $\begingroup$ Nice explanation, and a near thorough answer, but you are missing something key. $\endgroup$ – JLee Mar 18 '15 at 3:47
  • $\begingroup$ @JLee: I guess this may depend on what you mean by "perfectly". $\endgroup$ – Werner Mar 18 '15 at 3:50
  • $\begingroup$ Assume that "perfectly" means that if the computer has a move that can force a win for itself, it will find it and choose that move every time. $\endgroup$ – JLee Mar 18 '15 at 3:55
  • 1
    $\begingroup$ Don't make it harder than necessary. This is the easy puzzle. :) Another hint: Your original assumption (first statement) in your answer is not always correct. So, when one concludes from a false assumption, all sorts of strange things can seem true. $\endgroup$ – JLee Mar 18 '15 at 12:56
  • 3
    $\begingroup$ A greedy algorithm does not produce the best results. $\endgroup$ – KSmarts Mar 18 '15 at 16:38
4
$\begingroup$

This is my first experience with Dots and Boxes, so please be kind if I am making some terrible mistakes. Per the wikipedia link:

An expert player tries to force their opponent to be the one to open the first long chain, because the player who first opens a long chain usually loses.

That is what we will try to do. Initial analysis shows four "safe" (will not enable the opponent to complete a box) moves, which Werner has conveniently Numbered 1-4. It is important to note that 1 and 3 are exclusive with 2 (ie if 1 gets played, 2 is no longer safe; whereas if 2 gets played, 1 and 3 are no longer safe). So the immediate assumption is to play either 1 or 3 as that removes 2, leaving two other safe moves (4 and 3 or 1) on the opponent's turn. We would get the last safe move, and the computer must open the long chains for us.

But there is one other move on the board which, while not safe, will not open a long chain. The horizontal line on the second row in the middle column (the line between the two red squares in the second third image of JonTheMon's answer).

With this in mind, we must play 2. The computer will play 4, and we will follow with the line I mentioned in the previous paragraph. The computer will take its two squares, then be forced to open the first long chain leading to our win.

(edit: whoops forgot about one of the diagrams)

$\endgroup$
  • $\begingroup$ Good job. I will post a couple more of these, and each will get more difficult. This being your first experience with this game, I am impressed. $\endgroup$ – JLee Mar 19 '15 at 19:54
  • 2
    $\begingroup$ The problem with this is that the computer need not play greedy. In response to your second move, instead of taking the two squares, the computer can respond with the topmost horizontal line in that column. The computer does not get any squares in that move, but forces you into pretty much the position you were trying to force the computer into. $\endgroup$ – Raziman T V Mar 19 '15 at 21:17
  • 1
    $\begingroup$ I see. But even then, the argument remains same : The computer could "sacrifice" by choosing the third vertical line in the third row in this case. In general, there is no reason for the computer to take every single box it can in its current move. $\endgroup$ – Raziman T V Mar 19 '15 at 21:41
  • 1
    $\begingroup$ The issue is that you are making assumptions about what the computer will do. I played 2 as my first move, and the computer (the state enumeration code in my answer) responded with the second vertical line in the fourth row instead of 4. We could really put the issue to rest if we play each other over chat. $\endgroup$ – Raziman T V Mar 19 '15 at 22:40
  • 2
    $\begingroup$ I am of the feeling that JLee has made the same mistake. In games from nim to go, greedy rarely works and sacrifices have a lot of value. Going down the decision tree or finding some smarter mathematical invariant is the only way to be sure. I suspect that the further questions from JLee might have the same problem, I hope they choose to play against my code once. Can you please tell me how many boxes you are able to get if the computer plays the move I said? $\endgroup$ – Raziman T V Mar 20 '15 at 7:03
3
$\begingroup$

The goal of dots and boxes is to be the person that makes the last (and biggest) group of boxes. To that end, you need to figure out how many regions there are and which one is smallest.

Region boundaries

Here are your potential boundaries of regions.

And here is one example of how it could play out:

Example game

Here you have 6 regions, so you want to let the computer take the first (smallest) region so you can take the last (black) region.

Unfortunately, you're a bit stuck and can't win. There are about 5 regions to start with, but only 2 moves that don't affect the number of regions. So, either you have to start off by giving them the first region (so they get the last region), or if you merge 2 regions (top left, bottom left), the computer will give you the first region.

enter image description here

$\endgroup$
  • $\begingroup$ I like much of your logic about regions, and I like how you color-coded them, but there are errors in some of the statements, and you didn't answer the question. The goal of Dots and Boxes is to make more boxes than your opponent, and this does not necessarily mean getting the last group of boxes. Also, the last group of boxes is not necessarily the largest. $\endgroup$ – JLee Mar 18 '15 at 14:39
  • $\begingroup$ The answer to the original question is: there is no best move. Also, I don't know about you, but in general I don't want to give the biggest group of boxes to my opponent, and vice versa, so it ends up last. $\endgroup$ – JonTheMon Mar 18 '15 at 15:14
  • $\begingroup$ This is from a game I played last night, and did win by a large margin. Which move did I play? $\endgroup$ – JLee Mar 18 '15 at 15:50
  • $\begingroup$ On the right, there are 3 regions; on the left, there are 1-3 regions. There are 2 moves on the right, and 4 moves on the left that will decide things. Given that, and the fact that the opponent moves "last", you can't win. The opponent will always try to have 1 or 3 regions on the left. If you try to split it into 2, they'll split it to 3. If you go with 1 region, they'll leave it one region. $\endgroup$ – JonTheMon Mar 18 '15 at 17:59
  • 1
    $\begingroup$ @JLee Are you certain that your opponent was a perfect player? $\endgroup$ – KSmarts Mar 18 '15 at 18:21
2
$\begingroup$

This is an unwinnable position if the computer plays perfectly.

I need an even number of chains
I am player one, as an even number of moves has been made, and there are an even number of dots.

(This is known as the chain rule, and anyone who is unfamiliar with it should learn it as it is a key to winning dots and boxes. The number of squares already in chains means the winner of the chains battle in this game wins the majority of the squares by sacrificing two at the end of each of the chains they are given.)

The board is split in two with the left (green) and right (blue).

left and right sides

There are two chains on the left hand side of the board
We can assume that the two is played before any chains (of three or more) are given, since a large number of squares in the final chains wins the game overwhelmingly, so giving any chain allows the opponent to take all the other chains.

Giving a chain leaves a chain

I cannot stop the computer from making a single chain on the left of the board
If I try to split the left hand side into two chains, the computer can easily kill the other chain by splitting it into two twos.

Playing horizontally just below half way down allows the computer to kill the other chain.

If I try to kill both chains on the left, the computer makes the other, for example:

giving two top left allows a chain of three bottom left

Delaying doesn't help Given the first move on the left, the computer can make the top left chain long enough to leave the bottom left no alternative but to be joined to it or split.

giving two centre top leaves one chain on the left

The best I can do is 8

The best I can do is force the computer to give away an extra two by threatening to make two chains on the left.

I've numbered the moves made after taking free squares, with purple being me and pink being the computer.

best play

$\endgroup$
  • $\begingroup$ I'd love to know how you won that game. I usually find dabble unassailable on maximum settings, but I beat it at this game. $\endgroup$ – not my job Mar 23 '15 at 0:18

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.