Can You Beat a Computer at Rock-Paper-Scissors?: Computing Further 6–8

Rock, paper, scissors: two friends shake their fists, one, two, three, and show a fist, a flat hand or two fingers. Paper wraps rock, scissors cut paper, rock blunts scissors. It decides who bats first, who gets the window seat, who washes the plates.

It looks like pure luck. You choose, your friend chooses, and nobody can know what the other will show. But can a computer find out what you will show, before you show it? The computer below has already chosen its move when you choose yours, so it can’t peek. All it has is a list of what you played before.

Tap Rock, Paper or Scissors. Play at least 30 rounds, and try to be as random as you can. The green squares are rounds you won, the red ones rounds the computer won.

You

Round 1

Predictor

Predictor has chosen its move. Now choose yours.

You: 0
Draws: 0
Predictor: 0
Rounds: 0

Against:

What you played after each of your moves
	Rock	Paper	Scissors
After Rock	0	0	0
After Paper	0	0	0
After Scissors	0	0	0
In all	0	0	0

The row the computer read for its last move, its guess ringed

Suppose you really did choose at random, like rolling a die. In 30 rounds, how many would the computer win, on average?

Pick an answer to see why.

You need: for the blocks, variables and choices, from Grade 7. For the Python (from Grade 8), loops, lists and functions.

Try it

Thirty rounds against the predictor

Play 30 rounds against Predictor (or more: the longer you play, the more it learns). Then look at the table under the game. It counts what you played after each of your own moves: the row “After Rock” says how many times you followed a rock with a rock, a paper or a scissors.

a.Who is ahead after 30 rounds?
b.Look at the row of your favorite move. Is one number in it much bigger than the others?
c.Read the sentence under your buttons after a few rounds. What does the predictor look at to choose its move?

Against the counter and against Random

Press Counter. It is simpler: it counts only how many times you played each move in all (the row “In all”), guesses your favorite, and plays what beats it.

Then press Random. It chooses at random every time and looks at nothing.

Random has no pattern to find, and it doesn’t look at yours: however you play, you win, draw and lose about a third of the rounds each. You can’t beat it, but it can’t beat you either. So the only safe way to play is to be truly random. The predictor bets that you aren’t.

How it works

Each move beats one move and loses to the other. Going round the triangle below against the arrows, rock is beaten by paper, paper by scissors, and scissors by rock.

Figure 3.1 The three moves. Each arrow goes from a move to the move it beats.

People are not random

A die has no memory: each roll knows nothing of the last. People remember, and react to what just happened.

A story from science

Three hundred rounds in Zhejiang

In 2014, Zhijian Wang, Bin Xu and Hai-Jun Zhou, scientists at Zhejiang University in China, published a study of how people really play. They asked 360 students to play, in groups of six. Each group played 300 rounds, and in each round every student was paired at random with another of the six. A win scored more points than a draw, a loss scored none, and at the end the points were paid out in cash.
Counted in all, the moves were very nearly a third each: on average each player chose rock 36% of the time, paper 33% and scissors 32%. Looked at that way, the students seemed random. But the scientists also looked at what each player did after a round, and found habits:

after a win, a player more often played the same move again;
after a loss, a player more often switched to the move that beats the one that had just beaten them (lose with rock to paper, then play scissors). This showed in four groups out of five: those where a win was worth at least twice a draw.

The totals looked random; the habits were in what came after each round. The counter looks only at totals. The predictor looks at what comes after.

The table of nine counts

Here are eight moves a player made, in order:

R P R P S R P R

Look at each move and the one straight after it. After R came P, then after that P came R, and so on. There are seven pairs. Count them in a table: the row is the first move, the column the move that came next.

	then Rock	then Paper	then Scissors
After Rock	0	3	0
After Paper	2	0	1
After Scissors	1	0	0

The player’s last move was R. In the row “After Rock”, Paper has 3 and the others 0: three times out of three, this player followed a rock with paper. So the predictor guesses Paper, and plays Scissors, which beats it.

The table has nine counts, but each guess needs only one row: the row of the last move.

The same player now plays P, so their moves end R P. Which row does the predictor read, and what does it play?

Pick an answer to see why.

This is the same idea as the next-word model from Grade 8: count what came after each word, and guess the one that came most. A chatbot’s ancestor and a rock-paper-scissors predictor are cousins.

Program it

With blocks: a computer that counts

This program is the counter, in blocks. Before each round it looks at its three counts, r, p and s, guesses your most played move, and sets mine to the move that beats it (rock beaten by paper, and so on). Then it asks your move, says its own, counts yours, and adds a win if its move beats yours. After 10 rounds it says how many it won.

Press Run and play 10 rounds (type R, P or S). Then press Test: it plays three players who always do the same thing.

What the program says and asks appears here.

r – no value

p – no value

s – no value

wins – no value

mine – no value

move – no value

Step	Block	r	p	s	wins	mine	move

Test	Should say	It said
Rock every time	I won 9 of 10
Scissors every time	I won 10 of 10
R, P, S in turn	I won 0 of 10

Press Run to start the program, or Step to do one block at a time.

Loading the blocks…

What you should see

In Python (from Grade 8): the game file

The programs below share a file the page keeps for you, rps.py: the rules, and some players to test against. A move is the string 'R', 'P' or 'S'. A player is a function choose_move(theirs, mine): theirs is the list of the other player’s moves so far, mine its own, and it gives back its next move.

Try it

Open the game file

Find the function beat. What does beat('S') give back? And what does most(2, 5, 1) give back?

rps.py

# rps.py: rock-paper-scissors for the programs on this page.# A move is 'R' (rock), 'P' (paper) or 'S' (scissors).# A player is a function like choose_move(theirs, mine): theirs is the list# of the other player's moves so far, mine its own, and it gives back its# next move.import random def beat(move):    # the move that beats this one    if move == 'R':        return 'P'    if move == 'P':        return 'S'    return 'R' def score(a, b):    # 1 if a beats b, 0 for a draw, -1 if b beats a    if a == b:        return 0    if beat(b) == a:        return 1    return -1 def most(r, p, s):    # the move counted most often (on a tie, the later of R, P, S)    if r > p and r > s:        return 'R'    if p > s:        return 'P'    return 'S' # Five players to test a program against def always_rock(theirs, mine):    return 'R' def in_turn(theirs, mine):    # rock, paper, scissors, rock, paper, scissors...    return ['R', 'P', 'S'][len(mine) % 3] def never_twice(theirs, mine):    # never the same move twice in a row: one of the other two, at random    if len(mine) == 0:        return random.choice(['R', 'P', 'S'])    last = mine[len(mine) - 1]    others = []    for m in ['R', 'P', 'S']:        if m != last:            others.append(m)    return random.choice(others) def win_stay_lose_shift(theirs, mine):    # after a win, the same move again; after a loss, the move that    # beats the one that just won; after a draw, any move at random    if len(mine) == 0:        return random.choice(['R', 'P', 'S'])    me = mine[len(mine) - 1]    them = theirs[len(theirs) - 1]    if score(me, them) == 1:        return me    if score(me, them) == -1:        return beat(them)    return random.choice(['R', 'P', 'S']) def at_random(theirs, mine):    return random.choice(['R', 'P', 'S']) def match(player1, player2, rounds):    # plays two players against each other for some rounds, each choosing    # before it sees the other's move; gives back [won, drawn, lost] for player1    moves1 = []    moves2 = []    result = [0, 0, 0]    for n in range(rounds):        a = player1(moves2, moves1)        b = player2(moves1, moves2)        moves1.append(a)        moves2.append(b)        s = score(a, b)        if s == 1:            result[0] = result[0] + 1        elif s == 0:            result[1] = result[1] + 1        else:            result[2] = result[2] + 1    return result

Answer

random.choice(['R', 'P', 'S']) picks one item of the list at random: that is how the players roll their dice.

Step 1: the counter

The counter counts the other player’s moves, then plays beat of the most common one. With nothing to count yet, it picks at random.

from rps import beat, mostimport random def choose_move(theirs, mine):    r = 0    p = 0    s = 0    for i in range(len(theirs)):        if theirs[i] == 'R':            r = r + 1        elif theirs[i] == 'P':            p = p + 1        else:            s = s + 1    if r + p + s == 0:        return random.choice(['R', 'P', 'S'])    return beat(most(r, p, s)) print(choose_move(['R', 'R', 'P'], ['S', 'P', 'P']))print(choose_move(['R', 'P', 'S', 'R', 'P', 'S'], []))

Output

PR

Against R, R, P it guesses rock and plays paper. Against two of each, most gives S (a tie goes to the later move), so it plays rock. That is why “R, P, S in turn” left the blocks counter without a single win: the counts are always nearly equal, and the guess is always a step behind.

Step 2: the predictor

To count what came after the last move, look at every move except the last. Where a move is the same as the last one, the move straight after it, theirs[i + 1], is what the player did next that time: count it.

from rps import beat, mostimport random def choose_move(theirs, mine):    if len(theirs) == 0:        return random.choice(['R', 'P', 'S'])    last = theirs[len(theirs) - 1]    r = 0    p = 0    s = 0    for i in range(len(theirs) - 1):        if theirs[i] == last:            after = theirs[i + 1]            if after == 'R':                r = r + 1            elif after == 'P':                p = p + 1            else:                s = s + 1    if r + p + s == 0:        return random.choice(['R', 'P', 'S'])    print('After', last, 'you played R', r, 'P', p, 'S', s)    return beat(most(r, p, s)) print(choose_move(['R', 'P', 'R', 'P', 'S', 'R', 'P', 'R'], []))

Output

After R you played R 0 P 3 S 0S

That is the eight moves from the table above, and the program reads the same row: after R came P three times, so it plays scissors. The loop stops at len(theirs) - 1, so theirs[i + 1] never goes past the end of the list.

Now play it. The game below calls choose_move from the program just above (as you have it: press Edit to change it) before every round, with your moves as theirs. What it prints appears under the game.

Press Start, then play. Your code should guess exactly as Predictor does. Then change it: what if it looks only at your last two rounds, or plays the move your habit points to, instead of the one that beats it?

You

Round 1

Your code

Your code has chosen its move. Now choose yours.

You: 0
Draws: 0
Your code: 0
Rounds: 0

Against:

What you played after each of your moves
	Rock	Paper	Scissors
After Rock	0	0	0
After Paper	0	0	0
After Scissors	0	0	0
In all	0	0	0

The row the computer read for its last move, its guess ringed

What your choose_move prints, and any error, appears here.

What your program shows

You can’t play a thousand rounds by hand, but match can. Here your predictor plays four players from rps.py, 1,000 rounds each. random.seed(1) makes the dice roll the same way every time you press Run, so your numbers match the ones here; change the 1 for another set of games.

from rps import beat, most, matchfrom rps import always_rock, in_turn, never_twice, at_randomimport randomrandom.seed(1) def choose_move(theirs, mine):    if len(theirs) == 0:        return random.choice(['R', 'P', 'S'])    last = theirs[len(theirs) - 1]    r = 0    p = 0    s = 0    for i in range(len(theirs) - 1):        if theirs[i] == last:            after = theirs[i + 1]            if after == 'R':                r = r + 1            elif after == 'P':                p = p + 1            else:                s = s + 1    if r + p + s == 0:        return random.choice(['R', 'P', 'S'])    return beat(most(r, p, s)) players = [always_rock, in_turn, never_twice, at_random]names = ['Always rock', 'Rock, paper, scissors in turn', 'Never the same twice', 'At random']for i in range(len(players)):    result = match(choose_move, players[i], 1000)    print(names[i] + ':', result[0], 'won,', result[1], 'drawn,', result[2], 'lost')

Output

Always rock: 998 won, 1 drawn, 1 lostRock, paper, scissors in turn: 998 won, 2 drawn, 0 lostNever the same twice: 489 won, 324 drawn, 187 lostAt random: 358 won, 323 drawn, 319 lost

(match(choose_move, players[i], 1000) hands the functions themselves to match: a function’s name without brackets is the function, which match then calls 1,000 times.)

A habit is a weakness. “Always rock” and “in turn”, which beat the counter, lose almost every round: after one or two rounds, every row of the table has the answer in it.
Trying hard to look random is a habit too. “Never the same twice” is what many people do when they try to be random. It makes every row of the table say “not this one”, and the predictor wins about half the rounds, not a third. (How the rest split between draws and losses changes a lot with the seed; Challenge ★★ fixes that.)
Only real randomness is safe. Against “At random”, nothing is learned: about a third each, as the choose at the start said. Change the seed and the three numbers wobble round 333, now one ahead, now another.

The predictor knows nothing about rock-paper-scissors strategy. It only counts, and the counts are enough, because players have habits and habits show up in counts. Much of what is called artificial intelligence works the same way: a model learns from what happened before and guesses what comes next.

A story from science

Machines that read minds at Bell Labs

In the 1950s, two engineers at Bell Telephone Laboratories in the United States built machines to play a guessing game called matching pennies against people: each player secretly chooses heads or tails, and one of them wins when the two match. Claude Shannon, the engineer of the next-word story in Grade 8, wrote about his in a short memo in 1953, “A Mind-Reading (?) Machine”. His colleague David Hagelbarger described his machine, SEER, a “sequence extrapolating robot”, in 1956. Neither machine could see its opponents. Like your predictor, they looked only for patterns in the choices people had already made, and guessed that the patterns would repeat. Hagelbarger’s machine is reported to have won 5,218 of 9,795 games: a little over half, in a game where guessing at random wins exactly half.

A story from science

A tournament for programs

In 1999 Darse Billings, a computer scientist at the University of Alberta in Canada, ran the First International RoShamBo Programming Competition (RoShamBo is another name for the game). Programs played each other in matches of 1,000 rounds. A program that plays at random can never lose a match by much, but it can never win one by much either. So the entrants were told in advance that some programs in the field would be weak on purpose. They were subtler than “always rock”: one, Switch A Lot, switched moves nearly every time, much like “Never the same twice”; another played the digits of π. To win, a program had to find and punish weaknesses like these, and not get caught itself.
The winner, Iocaine Powder by Dan Egnor, won all 25 tournaments that were run. It kept several predictors at once (one counting the other program’s moves, as your counter does; one finding the latest few moves earlier in the game and what came next, a longer version of your predictor; and one that plays at random, in case it was being beaten) and played whichever had been doing best so far. For each it also asked: what if the other program is predicting me?

Going further still

Beat the predictor. Once you know its rule, the predictor is as predictable as “always rock”: work out what it will play, and play what beats that. Try it by hand in the first game: next it reads the row of your last move. Challenge ★★★ makes a program do it.

The habit it misses. Run this, the habit from the Zhejiang study taken to the extreme: after a win, the same move; after a loss, the move that beats the winner.

from rps import beat, most, match, win_stay_lose_shiftimport randomrandom.seed(1) def choose_move(theirs, mine):    if len(theirs) == 0:        return random.choice(['R', 'P', 'S'])    last = theirs[len(theirs) - 1]    r = 0    p = 0    s = 0    for i in range(len(theirs) - 1):        if theirs[i] == last:            after = theirs[i + 1]            if after == 'R':                r = r + 1            elif after == 'P':                p = p + 1            else:                s = s + 1    if r + p + s == 0:        return random.choice(['R', 'P', 'S'])    return beat(most(r, p, s)) result = match(choose_move, win_stay_lose_shift, 1000)print('Win-stay, lose-shift:', result[0], 'won,', result[1], 'drawn,', result[2], 'lost')

Output

Win-stay, lose-shift: 492 won, 13 drawn, 495 lost

The predictor gets no better than even. This player’s next move depends on whether it won or lost, which the predictor never looks at.

A robot that doesn’t need to guess. At the University of Tokyo, Masatoshi Ishikawa’s laboratory built a robot hand that wins every round. It doesn’t predict anything: a high-speed camera sees what shape your hand is making within about a thousandth of a second, as you start to show it, and the robot makes the winning shape almost at the same moment. Fast enough to look fair, but it isn’t.

Challenges

★ The judge (blocks)

Finish the program so that it says who wins: Player 1 wins, Player 2 wins or Draw. Then press Test.

What the program says and asks appears here.

a – no value

b – no value

Test	Should say	It said
R and S	Player 1 wins
S and R	Player 2 wins
P and P	Draw
P and R	Player 1 wins
R and P	Player 2 wins
S and P	Player 1 wins
S and S	Draw

Press Run to start the program, or Step to do one block at a time.

Loading the blocks…

Hint

Answer

★★ The best reply (Python, from Grade 8)

“Never the same twice” makes a row like Rock 0, Paper 5, Scissors 5. The predictor guesses one of the two and plays what beats it, but half the time the player plays the other, and then the predictor can lose. Is there a move that never loses here?

Write best_reply(r, p, s): given how often the other player has played rock, paper and scissors, give back the move that would have scored most against them, counting each win as 1 and each loss as −1. If two moves score the same, either is right.

def best_reply(r, p, s):    # r, p, s: how many times the other player played rock, paper, scissors    # give back 'R', 'P' or 'S': the move that scores most against them    return 'R' print(best_reply(0, 5, 5))

Paper 5, Scissors 5 best_reply(0, 5, 5) Should give 'S' Yours —
Rock 5 best_reply(5, 0, 0) Should give 'P' Yours —
Rock 2, Paper 5, Scissors 4 best_reply(2, 5, 4) Should give 'S' Yours —

Tests passed: — / 10
Challenge: ★★ solved

Write your best_reply in the program above (Edit), then check it.

A test your function gets wrong, anything it prints, and any error appear here.

Hint

Answer

★★★ Beat the predictor (Python, from Grade 8)

Your program now plays against the predictor. The program below has it as predictor, with beat and most from rps.py copied in. Write choose_move(theirs, mine) so that it wins: here theirs is the predictor’s moves so far and mine yours.

import random def beat(move):    if move == 'R':        return 'P'    if move == 'P':        return 'S'    return 'R' def most(r, p, s):    if r > p and r > s:        return 'R'    if p > s:        return 'P'    return 'S' def predictor(theirs, mine):    if len(theirs) == 0:        return random.choice(['R', 'P', 'S'])    last = theirs[len(theirs) - 1]    r = 0    p = 0    s = 0    for i in range(len(theirs) - 1):        if theirs[i] == last:            after = theirs[i + 1]            if after == 'R':                r = r + 1            elif after == 'P':                p = p + 1            else:                s = s + 1    if r + p + s == 0:        return random.choice(['R', 'P', 'S'])    return beat(most(r, p, s)) def choose_move(theirs, mine):    # theirs: the predictor's moves so far; mine: yours    # give back the move that beats the predictor's next move    return 'R' print(choose_move(['P', 'R', 'S'], ['R', 'P', 'R']))

Play it against the predictor here, then check it below.

Press Play 100 rounds. Then try your code against Counter and Random too.

Your code

Round 0

Predictor

Press Play 1 round, or Play 100 rounds.

Your code: 0
Draws: 0
Predictor: 0
Rounds: 0

Against:

What your code played after each of its moves
	Rock	Paper	Scissors
After Rock	0	0	0
After Paper	0	0	0
After Scissors	0	0	0
In all	0	0	0

The row the computer read for its last move, its guess ringed

What your choose_move prints, and any error, appears here.

You played R, P, R choose_move(['P', 'R', 'S'], ['R', 'P', 'R']) Should give 'R' Yours —
You always played rock choose_move(['P', 'P', 'P', 'P'], ['R', 'R', 'R', 'R']) Should give 'S' Yours —
You played R, P, S in turn choose_move(['S', 'P', 'R', 'S', 'P', 'R', 'S'], ['R', 'P', 'S', 'R', 'P', 'S', 'R']) Should give 'R' Yours —

Tests passed: — / 8
Challenge: ★★★ solved

Write your choose_move in the program above (Edit), then check it.

A test your function gets wrong, anything it prints, and any error appear here.

Hint

Answer

Questions

Which player can the predictor in this topic not beat over many rounds?

Pick an answer to see why.

A player’s moves so far are S S R S S R S. What does the predictor play next? Show the row it reads.

Answer

Why did the counter win none of 10 rounds against “R, P, S in turn”?

Pick an answer to see why.

In the Zhejiang study, the totals were close to a third each, but the players still had habits. Explain how both can be true, with an example.

Answer

Quiz yourself on this unit →

Where to go next

Grade 7, How Machines Learn: a model trained on examples, tested on new ones. Your predictor trains on every round you play.
Grade 8, Generative AI: the next-word model, which counts what comes after each word, as your predictor counts what comes after each move.
Grade 8, Searching and Sorting: lists and their positions, which the predictor walks through.
How do you always win at Nim? A game where, unlike this one, there is a perfect strategy, and it is written in binary.
How does a computer roll a die? Where a computer’s random numbers come from, and why random.seed(1) gives the same games every time.
Can a machine learn a game by itself? Matchboxes full of beads learn tic-tac-toe from their wins and losses. (Coming soon.)