Master Mind, Part 2

November 20, 2009

We can calculate the maximum score for a given pool and probe like this:

(define (max-score pool probe)
  (apply max (map cdr
    (uniq-c string=? (sort string<?
      (map (lambda (p) (score p probe)) pool))))))

Then the minimax probe is determined by computing the maximum score over all possible probes, selecting the minimum. The tricky if implements Knuth’s “subject-to” requirement; if the probe is a new minimum, or if it equal to the current minimum, is a member of the pool, and the current minimum is not a member of the pool, keep it as the new minimum, otherwise loop to the next probe.

(define (minimax pool)
  (let loop ((min-probe '()) (min-size #e1e10) (ps probes))
    (if (null? ps) min-probe
      (let ((size (max-score pool (car ps))))
        (if (or (< size min-size)
                (and (= size min-size)
                     (member (car ps) pool)
                     (not (member min-probe pool))))
            (loop (car ps) size (cdr ps))
            (loop min-probe min-size (cdr ps)))))))

The other thing that we need before we can write the solver is a way to apply the result of a probe to the current pool, producing a new, smaller pool:

(define (apply-probe pool probe result)
  (filter (lambda (p) (string=? (score p probe) result)) pool))

Note that none of the functions shown above take the code word as an argument; there is no cheating! The solver needs to know the code word, of course, so it can determine the score for each probe:

(define (solver . args)
  (let ((code (if (pair? args) (car args) (fortune probes))))
    (let loop ((n 1) (pool probes))
      (let* ((probe (minimax pool))
             (result (score code probe)))
        (display probe) (display " ")
        (display result) (newline)
        (if (string=? (make-string num-pegs #\B) result) n
          (loop (+ n 1) (apply-probe pool probe result)))))))

As with the setter, the solver can either be given a code word or choose one at random. Here is a sample interaction with the solver:

> (solver '(3 6 3 2))
(1 1 2 2) B...
(1 3 4 4) W...
(3 5 2 6) BWW.
(1 4 6 2) BW..
(3 6 3 2) BBBB
5

The initial pool has 1296 entries. After the first probe, 1 1 2 2, there are 256 entries left, the second probe, 1 3 4 4, reduces the pool to 44 entries, the third probe, 3 5 2 6, reduces the pool to seven entries, and the fourth probe, 1 4 6 2, distinguishes between them. After the third probe, the seven entries in the pool are 3 6 3 2, 3 6 6 2, 4 5 6 2, 4 6 2 5, 5 5 3 2, 6 4 2 5, and 6 6 2 3. Note that none of those seven entries could distinguish the winner; the fourth probe, 1 4 6 2, comes from outside the current pool, demonstrating Knuth’s “subject to” rule.

The solver works equally well with eight colors and five pegs, though the large increase in the size of the search space, to 85 = 32768 possible codes, makes it slow:

> (solver '(3 6 3 2 1))
(1 1 2 3 4) WWW..
(2 2 5 4 3) WW...
(3 6 6 1 2) BBWW.
(3 6 7 2 1) BBBB.
(3 6 3 2 1) BBBBB
5

Because solver returns the number of probes, we can study its behavior. It takes 5801 probes to solve each possible puzzle once, an average of 4.476 probes per puzzle:

(let loop ((n 0) (ps probes))
  (if (null? ps) n
    (loop (+ n (solver (car ps))) (cdr ps))))

Knuth’s algorithm minimizes the worst-case solution in five probes. By comparison, Koyama and Loi give two algorithms that improve the average number of probes in their article “An Optimal Mastermind Strategy” in the Journal of Recreational Math. Volume 25, pages 251-256, 1993 (not available online); one algorithm uses 4.430 probes on average, but has a worst-case of six probes, the other uses 4.431 probes on average with a worst-case of five probes.

We re-used all the code from the previous exercise, and range, fold-right, make-list, filter, sum, uniq-c, rand, sort and cross from the Standard Prelude. The code is collected at http://programmingpraxis.codepad.org/tHXIIIfF, but you can’t run it, because it causes a timeout.

About these ads

Pages: 1 2

2 Responses to “Master Mind, Part 2”

  1. [...] about Programming from google blogs as of November 21, 2009 Master Mind, Part 2 « Programming Praxis – programmingpraxis.com 11/21/2009 Programming Praxis. A collection of etudes, updated [...]

  2. daniel said

    can i see the answer?

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 613 other followers

%d bloggers like this: