Transcript Presentation - Carnegie Mellon University

Motivating the Human Oracle:
A Game to Solve Hard AI Problems
A Presentation by
Ian Graham and David Kitchin
Carnegie Mellon University
August 2, 2002
Credit where Credit is Due
This project would not have been possible
without the theoretical basis and
additional ideas provided by
Manuel Blum and Luis von Ahn.
Thanks!
What is a Hard AI Problem?
Describe this image.
What is a Hard AI Problem?
A hard AI problem can be defined as a
problem in artificial intelligence that has
gone unsolved for a long period of time,
even under intense research.
What is a Hard AI Problem?
In other words, a hard AI problem is a problem
which is solvable by humans but not readily
solvable by computers.
Hard AI Problems are Useful
If we query some source with a hard AI
problem and are presented with a valid
solution, we know that one of two
things has occurred:
 A human has answered the problem
 A program to solve the problem has
been created
Hard AI Problems are Useful
Given that a hard AI problem has been open
for a significant length of time, the odds of
encountering a program to solve it are very
small. Therefore, we’re probably talking with
a human.
(this idea should be somewhat familiar)
The CAPTCHA Idea
If we can create a program which
generates and grades hard AI
problems, then we have an
automated method of verifying
that our program is talking to a
human and not another
program.
The CAPTCHA Idea
CAPTCHA—Completely Automated Public
Turing Test to Tell Computers and
Humans Apart
“Public” signifies that all source code and
data are available to programs which
might be tested by the CAPTCHA
How to Defeat a CAPTCHA
Other than solving the relevant hard AI
problem, the only way for a program to
pass a CAPTCHA is to have access to a
“human oracle”—that is, it must be able to
query a human resource and use the
answer in its evaluation.
How to Defeat a CAPTCHA
Having a human directly pass a CAPTCHA is
obviously not a defeat.
However, if humans solve equivalent hard
AI problems either for another purpose or
completely unknowingly on a foreign
server, these answers might be used in a
program capable of bypassing the original
CAPTCHA.
How to Defeat a CAPTCHA
An example:
Assume that my company,
Spammers’R’We, needs to register
several thousand addresses at Hotmail,
and that Hotmail uses a CAPTCHA
which verifies that a human is
performing the registration by requiring
recognition of a specific word in a
distorted image.
How to Defeat a CAPTCHA
Spammers’R’We sets up a free newsgathering service with relatively little
overhead, requiring user registration to
read articles.
User registration seems to require
identification of a specific word in a
distorted image!
Augmenting the Abilities of
Computers
Any system which
produces a “human
oracle” provides an
extremely powerful
augmentation to the
computational
abilities of programs
which may use it.
Augmenting the Abilities of
Computers
Hard AI problems
become solvable
Computers have an
easier time with
elements such as
emotion, recognition
However…
Unlike computers, humans need a reason
to work.
Most people are unwilling to sit at a
terminal 24/7 and answer questions,
even if it would make things easier for
our computers.
A “human oracle” paid to sit and type all
day isn’t a revolutionary concept.
Motivation
What would
make me
solve hard AI
problems all
day?
Motivation
 Money
 Food/Water/Shelter
 Sense
 Fun
of self-worth
Fun as Motivation
Fun is cheap and easy.
There are no explicit bounds on the
amount of fun which may be given out
by any person or organization
How do we distribute fun?
Embedding a
Hard AI Problem in a Game
The most appealing method is to provide
a game whose playing results in the
solving of a hard AI problem.
Possible to produce a human oracle
without contributors knowing they are
resources!
Our Problem of Choice
General image description
Not only recognition of the contents of
an image, but also of descriptive or
emotional aspects, symbolic meanings,
and associations
Our Problem of Choice
Our goal:
To create a simple game program which
is entertaining for players, and which
receives images as input and returns
intelligent descriptions as output.
An Abortive Attempt
“Play our single-player image association game!
When you see an image, type the first thing
that comes to your mind as quickly as
possible! Receive no feedback! Just keep
typing! It’s fun!”
Some Concerns
Entertainment value
 “Cheating” (junk answers)

– “I think of ‘a’ when I see each image!”

‘Bots
– “Oh, just add a CAPTCHA!”
A Better Attempt
Let’s try a two-player game where
partners attempt to produce the same
description of a commonly-seen image,
without any communication between
players.
A Better Attempt
Players are challenged to “think in the
same way,” or to test how “in-tune”
their minds are.
A Better Attempt
Gameplay is extremely simple—there are
no points, players see no output from
each other until they have matched on
some description of the image and all
guesses are revealed
Addressing Concerns
Entertainment value
 “Cheating”

– Outside communication
– Junk answers

‘Bots
Demonstration
Breaking CAPTCHAs
Many visual CAPTCHAs require the user to
view an image (or set of images) and
make a text-based reply
These could be thwarted by the above
game with simple modification of the
instructions displayed to the user
More Constructive Applications
Construct a catalog of descriptions of
images on the WWW, for an extremely
intelligent search engine
Classify images based on mood, emotion,
association
“Hey, it’s like the Matrix.”
Players of a game participate of their own
free will.
However, in well-disguised human oracle
systems, contributors may not know
that they are being used as
computational resources, possibly in
pursuit of an unethical or illegal end
Do they have the right to know?
Quick Reference
Luis von Ahn, Manuel Blum, John
Langford. Telling Humans and
Computers Apart (Automatically).
 www.captcha.net
