Solving the AB Game by Brute Force

November 7, 2011

The AB game, a variant of Mastermind, is played with pencil and paper and with two people. One person chooses a four digit number in which no digit is repeated, say X, and the other person tries to guess it in as few moves as possible. After the guesser guesses some number, say Y, the other person gives information on how closely Y matched with X:

  • If some digit in Y coincides with a digit in X (in the same position), then the guesser scores an A.
  • If some digit in Y exists in X but is in the wrong place, then the guesser scores a B.

For instance, if X is 1234 and we guess 2674, we get an A and a B, because the 4 is in the right place, and the 2 is one of the right numbers but isn’t in the right place.

This proceeds until the guesser gets the exact number.

When humans (or at least beginners) play the AB game, they usually do some form of uncoordinated trial and error, which gets the right answer after some large number of moves. This takes anywhere from about 8 to possibly 30 guesses. When I played this game with a friend, I didn’t have a very systematic strategy, but I wondered if a computer program could solve the game, always entering the optimal guess.

A Bruteforce Solver

My first approach happened to work fairly well. Simply, the computer keeps track of a list of all possible numbers that the answer can be. At random, the computer guesses one of the numbers, and upon receiving feedback, eliminates every number in its list that doesn’t match that feedback. Quickly it eliminates whole swaths of combinations and arrives at the answer.

A typical session might go like this:

Guess 1: 6297. Score: 5040
b
Guess 2: 8512. Score: 1440
abb
Guess 3: 2315. Score: 83
bb
Guess 4: 5842. Score: 29
bb
Guess 5: 9581. Score: 13
ab
Guess 6: 8021. Score: 1

It took only 5 guesses for the computer to narrow down the choices to the only possible answer (8021).

A variant that is usually much harder for humans to solve is to allow the number chosen to have repeats. Although significantly trickier for humans to guess by trial and error, brute force doesn’t seem to be affected too much by it:

Guess 1: 1796. Score: 10000
b
Guess 2: 5881. Score: 3048
a
Guess 3: 0131. Score: 531
abb
Guess 4: 3311. Score: 15
aa
Guess 5: 3201. Score: 9
abb
Guess 6: 2011. Score: 1

The computer’s average of five or six is much better than a human can normally do! (although I haven’t researched possible human algorithms).

Optimal or Not?

At this point you may begin to wonder if this strategy is the optimal one. Unfortunately, it is not — and I only need one counterexample to demonstrate that.

Suppose that instead of four numbers, you were allowed to choose 4 letters from A to Z. You choose the combination ABCW. Now suppose that the computer ‘knows’ that the first three letters are ABC — that is, it has eliminated all other combinations except for ABCD, ABCE, …, ABCZ.

By the random guessing algorithm, the computer is forced to guess ABCJ, ABCP, etc, until it eventually hits on ABCW at random. This may take a very high number of guesses.

A smarter strategy would be to guess combinations of four unknown letters, say DEFG, then HIJK, etc. Instead of eliminating one letter, you eliminate four letters at a time. Although some guesses have no chance of being correct, the number of guesses required is fewer in the long run.

Source Code

I’ll put my somewhat unwieldy java code here for all to see:



import java.util.*;

public class ABSolver{
  
  // Does cc1 and cc2 together match the pattern?
  // If repeats are allowed, cc2 is matched against cc1.
  static boolean fits(char[] cc1, char[] cc2, int A, int B){

    int a = 0;
    int b = 0;
    for(int i=0; i<4; i++){
      if(cc1[i] == cc2[i]) a++;
      else{
        for(int j=0; j<4; j++){
          if(i != j && cc1[j] == cc2[i] && cc1[j]!=cc2[j]){
            b++;
            break;
          }
        }
      }
    }

    return a==A && b==B;
  }

  public static void main(String[] args){
    
    Random rand = new Random();
    Scanner scan = new Scanner(System.in);

    // Combinations that haven't been eliminated yet
    List<char[]> ok = new ArrayList<char[]>(10000);

    // Generate all possible combinations
    for(int i = 0; i <= 9999; i++){
      
      String i_s = Integer.toString(i);
      while(i_s.length() != 4) i_s = "0" + i_s;

      // Check for sameness
      char a = i_s.charAt(0);
      char b = i_s.charAt(1);
      char c = i_s.charAt(2);
      char d = i_s.charAt(3);
      boolean same = a==b || a==c || a==d || b==c || b==d || c==d;

      // Comment this line out if we're allowing repeats
      if(same) continue;

      char[] i_ia = i_s.toCharArray();
      ok.add(i_ia);

    }

    // Pick the first guess randomly
    char[] firstg = ok.get(rand.nextInt(ok.size()));
    char[] guess = null;

    int nguesses = 1;

    // Question answer cycle until we get it right
    while(true){

      // Ask for user response
      if(nguesses > 1){
        String ans = scan.nextLine();
        int A = 0;
        int B = 0;
        for(char cc : ans.toCharArray()){
          if(cc == 'a') A++;
          if(cc == 'b') B++;
        }

        if(A==4) return;

        // For each one check to see if it still fits
        List<char[]> ok_ = new ArrayList<char[]>(ok.size());
        for(char[] zhe : ok){
          if(fits(zhe, guess, A, B))
            ok_.add(zhe);
        }
        ok = ok_;
      }

      char[] nextguess = null;
      if(nguesses == 1)
        nextguess = firstg;
      else nextguess = ok.get(rand.nextInt(ok.size()));

      System.out.println("Guess " + nguesses + ": " + new String(nextguess)
                       + ". Score: " + ok.size());
      
      // we win!
      if(ok.size() == 1)
        return;

      guess = nextguess;
      nguesses++;
    }
    
  }
}

Some mathematical and algorithmic results on a simple puzzle game

July 5, 2010

I once came across this simple puzzle, or game.

You have a board of 7 squares in a single row, three black, and three red pieces. At the initialization of the game, the three black pieces are placed on the first (leftmost) three squares, and the three red pieces on the last (rightmost) three squares. This leaves one square in the middle.

The aim is to get all the red pieces onto the left side, and the black pieces on the right side, or in other words to reverse the position of all the pieces. This is done by executing a sequence of two possible moves:

One, a piece may move onto an empty square adjacent to it.

Two, a piece may hop over a piece of the opposite color adjacent to it, provided that the square on the other side of the second piece is empty.

Furthermore a move may only bring a piece closer to its destination; that is, it is not allowed to backtrack.

This particular instance of the problem (of three pieces each and seven squares) can be completed in 15 moves:

While this sequence completes the puzzle in 15 moves, it is not so obvious that this is the shortest sequence, that there is no shorter sequence that completes the puzzle in fewer than 15 moves. It is possible to prove a generalized result mathematically.

A formula for the number of moves

Let us generalize the game. We define an n-game to be an instance of the puzzle, with n pieces of each color separated by an empty square. For an n-game, the board contains 2n+1 squares.

Proposition: to complete an n-game, exactly n(n+2) moves are required.

In order for the n black pieces to completely trade places with the n red pieces, each black piece must hop over, or be hopped over by n red pieces.

Consider the pieces to be paired up as follows:

In the sequence of the game, each piece trades places with its partner. (Note that this is correct because the order of pieces of the same color cannot change).

It can be seen that the relative displacement between two members of a pair is 2(n+1). This is because each piece travels n+1 squares to get to its destination. In other words a piece travels 2(n+1) squares relative to its partner.

A move by either member of a pair adds a relative displacement of 1, while a hop adds a relative displacement of 2.

We have already shown that each pair must have, between them, n hops. This is equivalent to a relative displacement of 2n. Two additional moves are required to bring the relative displacement up to 2(n+1). Therefore, n+2 moves are required for a pair to exchange places.

As there are n pairs in the game, the total number of moves required to complete the game is n(n+2), as desired.

Implementation of a solver

Using the technique of a recursive depth-first search, it is a fairly easy programming exercise to write a solver for this puzzle. The solver produces the actual sequence of moves to complete an n-game.

The source code, in C:


#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// Number of tokens on each side
#define N 3

// Destination board
char endbd[2*N+1];

// Board representation
char bd[2*N+1];

// Moves found
char **mvs;

// Flag to indicate if recursion has finished
char cont = 1;

// Perform dfs given n byte array
void dfs(int nmvs){
    int i, l;
    char* tm = malloc(20);

    // Found, dump move list
    if(!memcmp(bd,endbd,N+1)){
        for(i=0;i<nmvs;i++) printf("%d. %s\n",i+1,mvs[i]);
        cont = 0;
    }

    if(!cont) return;

    // Check for 1-moves
    for(i=0;i<2*N;i++){
        if(bd[i]!=1) continue;

        // Try moving a square
        if(bd[i+1]==0){

            // Generate notation for piece move
            l=sprintf(tm,"%d -> %d",i+1,i+2);

            // Copy to move list
            mvs[nmvs]=malloc(l+1);
            strcpy(mvs[nmvs],tm);

            // Continue search
            bd[i]=0;
            bd[i+1]=1;
            dfs(nmvs+1);

            // Reset to previous state
            bd[i]=1;
            bd[i+1]=0;
        }

        // Try hopping
        if(i<2*N-1 && bd[i+1]==2 && bd[i+2]==0){
            l=sprintf(tm,"%d -> %d",i+1,i+3);
            mvs[nmvs]=malloc(l+1);
            strcpy(mvs[nmvs],tm);
            bd[i]=0;
            bd[i+2]=1;
            dfs(nmvs+1);
            bd[i]=1;
            bd[i+2]=0;
        }
    }

    // Check for 2-moves
    for(i=1;i<2*N+1;i++){
        if(bd[i]!=2) continue;
        if(bd[i-1]==0){
            l=sprintf(tm,"%d -> %d",i+1,i);
            mvs[nmvs]=malloc(l+1);
            strcpy(mvs[nmvs],tm);
            bd[i]=0;
            bd[i-1]=2;
            dfs(nmvs+1);
            bd[i]=2;
            bd[i-1]=0;
        }
        if(i>1 && bd[i-1]==1 && bd[i-2]==0){
            l=sprintf(tm,"%d -> %d",i+1,i-1);
            mvs[nmvs]=malloc(l+1);
            strcpy(mvs[nmvs],tm);
            bd[i]=0;
            bd[i-2]=2;
            dfs(nmvs+1);
            bd[i]=2;
            bd[i-2]=0;
        }
    }
}

int main(){

    // Board representation. 1's move right, 2's move left.
    // Initialize board here.
    int i;
    for(i=0;i<N;i++){
        bd[i]=1;
        endbd[i]=2;
    }
    bd[++i]=0;
    endbd[i]=0;
    for(;i<2*N+1;i++){
        bd[i]=2;
        endbd[i]=1;
    }

    mvs = malloc(1000*sizeof(char*));
    dfs(0);
    return 0;
}

For instance, the sequence of moves for n=3:

1. 3 -> 4
2. 5 -> 3
3. 6 -> 5
4. 4 -> 6
5. 2 -> 4
6. 1 -> 2
7. 3 -> 1
8. 5 -> 3
9. 7 -> 5
10. 6 -> 7
11. 4 -> 6
12. 2 -> 4
13. 3 -> 2
14. 5 -> 3
15. 4 -> 5

Follow

Get every new post delivered to your Inbox.

Join 61 other followers