A Simple Mind-Reading Machine

Just for fun, I decided to implement a "Mind Reading Machine" based on the work of Claude Shannon and D.W. Hagelbarger. If you’re not familiar with it, there’s a good summary of Shannon’s idea here (together with descriptions of some of his other inventions).

Essentially, it’s an algorithm that allows a computer to play a simple game against a human opponent. In each round of the game, the player has a free choice between two options – left/right, or heads/tails, for example. The algorithm attempts to "guess" which the player will choose. And, more often than not, the computer guesses correctly.

How does it work? Not by mind-reading, obviously, but by exploiting the fact that humans do not behave as "randomly" as they think they do. The computer maintains a very simple memory that records the pattern of results of the last two rounds – whether the player won or lost, whether they switched strategy, and then whether they then won or last the following round. The computer then uses this to choose its own best strategy based on the way the player behaved last time the current pattern occurred. If the computer loses twice in a row using the current strategy, it picks a random response in the next round.

There are ways to beat the algorithm (by ensuring that each time a pattern of plays comes up, you always behave the opposite way than you did last time), and I suspect there are many ways in which it could be improved (perhaps using Context-Tree Weighting, for example – but it’s a still an interesting experiment in its current form…

Here’s some C# code with a simple implementation of the algorithm – simply attach to an empty gameobject in a Unity scene (or the camera will do), and have a go at outwitting the computer by creating a "random" pattern using the left/right arrow keys:

using UnityEngine;
using System.Collections;

public class MindReader : MonoBehaviour {
     
    // Used to record play history
    int[,,] v;
    int lw1, lw2;
    int losingstreak;
    
    // The prediction of the player's next turn
    int prediction;
    
    // Keep track of scores
    int cpuScore, playerScore;

    string outText;
    
    // Use this for initialization
    void Start () {
        
        v = new int[2,2,2] { {{0,0},{0,0}}, {{0,0},{0,0}} };
        
        // No prior knowledge, so set initial prediction based on random coin flip
        prediction = flip ();
        
        // Set scores to 0
        cpuScore = playerScore = 0;
        
        // Won or lost last play and play before last
        lw2 = lw1 = 0;
        
         // Output
        outText = "";
        
    }
    
    void TakeTurn(int playerChoice) {

        // Display each player and computer's choices
        string outTextString = "You pressed " + playerChoice + ", " + "I guessed " + prediction + "\n";
         
        // Computer correctly guessed
        if(playerChoice == prediction) {
            cpuScore++;
            losingstreak = 0;
            outTextString += " I WIN!\n";
        }
         // Computer incorrectly guessed
        else {
            playerScore++;
            losingstreak++;
            outTextString += " YOU WIN!\n";
        }
        
        outText = outTextString;
         
        // Record latest scores in the matrix
        v[lw2,lw1,1] = (v[lw2,lw1,0] == playerChoice ? 1 : 0);
        v[lw2,lw1,0] = playerChoice;
        lw2 = lw1;
        lw1 = playerChoice;
        
        // If lost more than twice in present state, chose random strategy
        // Otherwise, keep same strategy
        prediction = v[lw2,lw1,1]==1 && losingstreak < 2 ? v[lw2,lw1,0] : flip();
    }
     
    // Simulate a coin flip to produce 50:50 chance of {0,1}
    int flip() {
        return Random.Range(0,2);
    }
    
    
    // Update is called once per frame
    void Update () {
    
         if(Input.GetKeyDown(KeyCode.LeftArrow)){
            TakeTurn(0);
        }
        if(Input.GetKeyDown(KeyCode.RightArrow)){
            TakeTurn(1);
        }    
    }
    
    void OnGUI() {
         GUIStyle style = new GUIStyle();
        style.fontSize = 36;
        
        GUI.Label(new Rect(0,0,Screen.width,100), outText, style);    
        GUI.Label(new Rect(0,100,Screen.width,200), "Player:" + playerScore + "CPU:" + cpuScore, style);
     }
    
}

There’s also a Java implementation of the same algorithm which you can try online at http://seed.ucsd.edu/~mindreader/

About these ads
This entry was posted in AI and tagged , , . Bookmark the permalink.

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