Solving the AB Game by Brute Force

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++;
    }
    
  }
}