uLisp - Bulls & Cows game

Bulls & Cows game

This program plays Bulls & Cows, a traditional pencil and paper game of logical deduction in which each player tries to guess the other player's code. The Lisp version can be played with codes of three or four digits, but becomes too slow with codes longer than this.

To play with five digits you can substitute the main bullcow function for one written in ARM or RISC-V assembler. This illustrates the benefits of an application written partly in uLisp, and partly in machine code using the uLisp ARM or RISC-V assembler. It's more convenient to write the flow of control and user interface in uLisp, taking advantage of the string handling and list processing functions. The core function, to calculate the score between two numbers, can be written in assembler to make the program respond quickly, even with long code numbers.

This program was first published on the uLisp forum.

Introduction

Bulls & Cows is a traditional pencil and paper game which became popular in the form of a colour peg version called Mastermind, originally marketed by Invicta Plastics, and subsequently by Hasbro. In this version the codes are numbers of between two and five digits. In this Lisp version the game simultaneously let's you guess its code, and also plays against you, trying to guess your code.

Playing Bulls & Cows

In the pencil and paper version of the game two players begin by each thinking of a code, typically consisting of four digits. The players then take turns in making inspired guesses at the others player's code. The guesser is given the following information about the guess:

The number of Bulls; digits correct and in the correct position (bull's-eyes).
The number of Cows; digits correct but not in the right position.

The first player to guess the other player's code is the winner.

As an example, here's a sample game (the player's code was 2745):

Guess: 1389 - Reply: 0 Bulls, 0 Cows.
Guess: 1234 - Reply: 0 Bulls, 2 Cows.
Guess: 1759 - Reply: 1 Bull, 1 Cow.
Guess: 1785 - Reply: 2 Bulls, 0 Cows.
Guess: 2745 - Reply: 4 Bulls!

Playing the game

To play the game call the function play with the length of the codes; for example:

 (play 4)

Here's a sample game. My code was "1234" and the computer's code was "8217":

> (play 4)
[1] Your guess: 1234 Score: 11   My guess: 2396 Score: 02
[2] Your guess: 5678 Score: 02   My guess: 3002 Score: 02
[3] Your guess: 3456 Score: 00   My guess: 4123 Score: 04
[4] Your guess: 1782 Score: 04   My guess: 1234 Score: 40
I win!
[5] Your guess: 7218 Score: 22
[6] Your guess: 8217 Score: 40
You got it!

The program

Representing the guess and code

To make it easier to write the machine-code version of the bullcow routine the guess and code are each represented as binary-coded-decimal numbers. For example, the code "1234" is represented as the hexadecimal number #x1234.

The utility bcd converts a decimal number to binary-coded-decimal:

(defun bcd (n)
  (cond
   ((zerop n) 0)
   (t (+ (mod n 10) (* 16 (bcd (truncate n 10)))))))

The utility printn prints a hexadecimal number with a specified number of digits:

(defun printn (n d)
  (cond
   ((= n 0) nil)
   (t (printn (1- n) (truncate d 16)) (princ (mod d 16)))))

For example:

> (printn 5 #x1234)

prints:

The utility incbcd increments a number in binary-coded-decimal, skipping over hexadecimal numbers that don't represent a valid bcd number:

(defun incbcd (n)
  (cond
   ((< (logand n #xf) 9) (1+ n))
   (t (ash (incbcd (ash n -4)) 4))))

For example:

(incbcd #x1909)

returns 6416, which is #x1910.

The bullcow function

The main function used by the program is bullcow, which calculates the score between a guess and a code. This needs to be as efficient as possible because it will be called hundreds of times when the computer is trying to solve the player's code. The score is returned as a two-digit hexadecimal number, bulls followed by cows. For example:

(bullcow 4 #x1234 #x4324)

gives #x12.

The obvious way to implement bullcow would be to compare every digit in the guess with every digit in the code, or a total of 16 comparisons in the four-digit game.

However, there's a more efficient way that only requires four comparisons, using a 10-element array spectrum to count the number of occurrences of each digit in the guess and code:

If the digits in the same position match, a bull is counted. Otherwise each digit in the guess increments the corresponding element of spectrum, and each digit in the code decrements the corresponding element of spectrum.

If incrementing leaves the element zero or negative it means it must have been positive from a matching digit in the code, and so a cow is counted. Likewise, if decrementing leaves the element zero or positive it must have been negative from a matching digit in the guess, and so another cow is counted.

Here's the bullcow routine:

(defun bullcow (digits guess code)
  (let ((score 0))
    (dotimes (i 16) (setf (nth i *spectrum*) 0))
    (dotimes (d digits)
      (let ((da (mod guess 16))
            (db (mod code 16)))
        (cond
         ((= da db) (incf score 16))
         (t 
          (when (<= (incf (nth da *spectrum*)) 0) (incf score))
          (when (>= (decf (nth db *spectrum*)) 0) (incf score))))
        (setq guess (truncate guess 16))
        (setq code (truncate code 16))))
    score))

Computer guess

The strategy used by the computer to guess the player's code is, at each turn, to make a guess that is consistent with all the player's answers to the computer's previous guesses. This is a candidate for the player's code. If it's not actually the correct answer, it will have reduced the number of possible candidates.

Here's the routine that chooses the computer's next guess:

(defun computer-choose (digits start try guesses replies)
  (let ((s (ash 1 (* digits 4))))
    (loop
     (setq try (mod (incbcd try) s))
     (when (= try start) (return nil))
     (when
         (every*
          (lambda (guess reply) (= (bullcow digits try guess) reply))
          guesses replies)
       (return try)))))

The routine sets try to the next number that hasn't been tried. The call to every* then checks whether that is a possible answer; if not, the routine loops and tries another.

If the routine returns to the starting number, start, the player must have given an incorrect reply.

The every* function is a simplified version of the Common Lisp every function. It takes a function and two lists, and returns t only if the function called with successive pairs of arguments is true:

(defun every* (fun a b)
  (cond
   ((or (null a) (null b)) t)
   ((null (funcall fun (car a) (car b))) nil)
   (t (every* fun (cdr a) (cdr b)))))

For example:

> (every* > '(5 6 7 8) '(1 2 3 4))
t

but:

> (every* > '(5 6 7 8) '(2 4 6 8))
nil

Other routines

The other routines are player-guess, which prompts the player to make a guess at the computer's number, and computer-guess, which displays the computer's next guess and reads the reply.

The main program play runs the game until both players have guessed the other player's code.

To keep the program as brief as possible there's no checking of the player's input, but it would be easy to add this.

Here's the whole uLisp Bulls & Cows program: Bulls & Cows program.

This will run in uLisp, or any standard version of Common Lisp.

Machine-code version of the bullcow routine

The Lisp version of the game is reasonably fast with four-digit codes, but becomes very slow with codes of five digits. We can use the assembler built in to the ARM or RISC-V versions of uLisp to replace the bullcow routine with an equivalent machine-code version.

For the ARM version see ARM assembler examples.

For the RISC-V version see RISC-V assembler examples.

Once you assemble the machine-code version the game will use this for the bullcow function, and you should see a dramatic speedup.

Previous: Simple maze game

Next: Mini text adventure game