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

maybe a more optimal solution is trying to score all 4 b’s before attempting to get any a’s?

LikeLike

Hey, it’s Robin. This game is actually one of my favorites; I used to play this a lot with my friends in high school. Then one day I came up with the question: Suppose you get a 3A0B on the first try. What’s the minimum number of trials you need to guarantee 4A?

This question was inspired by my challenge that an experienced player should be able to get the answer in 6 steps.

Me and a friend solved this in a brute-force approach; we basically considered all strategies. The optimal strategy involves three parts: sacrificing the numbers that are already known to be correct; sacrificing the positions of the known numbers even when they are being included; and never guessing the same number at the same position. I can’t exactly remember the optimal strategy, but I’d be interested to know if there is an optimal strategy for the game in general.

LikeLike