Playing Jeopardy with Search Engines

Compiled by Taliesin Beynon (Special Projects, Wolfram Research)

We assume that a corpus of Jeopardy clues is stored in the following form:

Placeholder/@{"round #", "category", "clue", "answer", "winners", "losers", "players"}

The corpus we used contained over 200,000 Jeopardy clues and answers. We load the data:

data=<<"jeopardy-data.m";
Length[data]

We pick a random sample of clues from the complete list to be processed and used as input to various search engines:

sample=RandomSample[data,10000];

Here is an example of five such clues:

Human Performance

We count the raw data to get a set of lists of which contestants answered correctly, incorrectly, or not at all in each round:

right=Flatten[data[[All,5]]];
wrong = Flatten[data[[All,6]]];
present=Flatten[Cases[data[[All,7]],{_,_,_}]];

Because players can choose whether or not to buzz in on a clue, there are actually two measures of human performance: 

◦ win fraction:		the fraction of all rounds the contestant answered correctly
◦ correct fraction: 	the fraction of attempted rounds that were correct

WinFraction[person_]:= With[{
	rights = Count[right,person],
	wrongs = Count[wrong,person]},
	N[rights / (rights+wrongs)]];

CorrectFraction[person_]:=
	N[Count[right,person] / Max[Count[present,person],1]];

Having defined these measures, we determine the 150 most frequent contestants:

people = SortBy[Tally[present],Last][[-150;;-1,1]];

We then calculate rankings of the top players in these two measures:

fwin = WinFraction/@people;
fcor = CorrectFraction/@people;

We plot these measures for 150 of the most frequent contestants on a scatter diagram 
(mouse over the markers to see player names, and see if you can find Ken Jennings):

The human average over all contestants who have been on the show is 60%, whereas the top contestants average an accuracy of around 80%.

Pre-processing

We clean the clues to remove unnecessary formatting and punctuation:

CleanQuestion[str_String ] := 
	StringReplace[str, 
		Join[Thread[Characters["&*`~<>{}[];/\\,'.\"+-_?"] -> ""],
		{"\n" -> " ", RegularExpression["^\\([^\\])]+\\) +"] -> ""}]];

We then reformat the answers to remove comments and formatting and to transform certain English forms into their Boolean equivalents. For example, the following answer strings are rewritten as shown (a vertical bar means that either string will match)

Column[{
Framed @ "one of Spain, Italy, or France" ->Framed /@("Spain" | "Italy" | "France"),
Framed @ "J. (Edgar) Hoover" -> Framed/@("J Hoover" | "J Edgar Hoover"),
Framed@"an aardvark"-> Framed@"aardvark",
Framed@"Mrs Thatcher" -> Framed @ "Thatcher"},
BaseStyle->{13,FontFamily->"Helvetica"},Alignment->"->"]

Here is the corresponding code:

$SkipWords = "the" | "an" | "a" | "Dr" | "Mr" | "Mrs" | "Miss";
CleanAnswer[text_String] := StringReplace[
	StringTrim @ StripPunctuation @ text,
	{
		(* Strip HTML tags *)
		"<" ~~ Except[">"].. ~~ ">" -> "",
		(* Turn a commented word into an optional string *)
		"(" ~~ opt:WordCharacter.. ~~") " :> StringOptional[opt <> " "],
		(* Remove bracketed, multi-word comments *)
		"(" ~~ Except[")"].. ~~ ")" ~~ Whitespace.. -> "",
		(* Strip any initial stopwords *)
		StartOfString ~~ $SkipWords ~~ " " -> "",
		(* Convert spoken English list of alternatives into a StringExpression *)
		StartOfString ~~ Alternatives["one of"|"either of"|"either"|"any of"] ~~ 
			list:(Whitespace.. ~~ WordCharacter..)..  ~~ EndOfString :> 
			ToAlternatives[list],
		(* Convert list of alternatives of the form "a or b or c" into a StringExpression *)
		StartOfString ~~ first:WordCharacter.. ~~ rest:(" or " ~~ WordCharacter..).. ~~
			EndOfString :> Append[ToAlternatives[rest], first]
	}, 
	IgnoreCase -> True
];

ToAlternatives[words_] := Alternatives @@ Map[
	StringTrim, DeleteCases[StringSplit[words], "," | "or"]];

StripPunctuation[text_] := 
	StringReplace[text, {
		"*" -> "", "." -> "", "-" -> "", "," -> "", Whitespace.. -> " ", 
		"\"" -> "", "'" -> "", "&" -> "and"}];

The sampled clues and answers are then processed using these two functions:

sampleQ=CleanQuestion/@sampleQ;
sampleA=CleanAnswer/@sampleA;

Answer Composition

As an interesting experiment, we used our internal Wolfram|Alpha data curation pipeline to classify the content of the roughly 200,000 Jeopardy answers in the corpus. The following is a breakdown of those answers to Jeopardy clues that were deemed to be unambiguous by our system.

Searching

We assume that there exist two Mathematica functions to retrieve the textual results of web searches:

SearchFor["engine", "query"]

which returns the web page containing the results of searching for the given query on the given search engine, and

LuckySearchFor["engine", "query"]

which returns the web page containing the contents of the first hit on the given search engine. Needless to say, the LuckySearchFor function must be written carefully so as not to follow a link to a source of information about the Jeopardy game show itself.

The implementation of these functions is left as an exercise to the reader. Doing more than a few thousand searches will typically require non-trivial server infrastructure. Thanks to Mathematica’s extensive library of import functionality, there is however a reasonable starting point:

Import["URL", {"HTML", "Plaintext"} ]

Scoring

Scoring is performed simply by observing whether the correct answer occurs in the search engine’s results web page (or the page of the associated top hit).

The function TestMatch returns True if it finds the target string or string expression in the text string. TestMatch ignores capitalization and only recognizes the target string if it appears as an entire word or phrase.

TestMatch[text_String, ans_] := 
	!StringFreeQ[text, 
		WordBoundary ~~ ans ~~ WordBoundary, 
		IgnoreCase -> True];

An example: does Googling for “elephant” bring up the word “mammal” anywhere on the first page of results?

TestMatch[SearchFor["Google", "elephant"], "mammal"]

Clearly elephants didn’t speculate in the property bubble:

TestMatch[SearchFor["Google", "elephant"], "foreclosure"]

The function TestAccuracy does pairwise comparison using TestMatch between a list of search results and a list of target phrases. It returns the fraction that were successfully found.

TestAccuracy[answers_, correct_]:=
	Mean @ Boole @ MapThread[TestMatch,{answers, correct}];

Results

These results are derived from applying 10,000 randomly chosen Jeopardy clues to the major English-language search engines (including Wikipedia’s internal search page). The strings are left unquoted so that search engines need not find a literal match for the entire question.

In terms of the functions already defined, we compute the accuracies of each engine as follows:

engines = {"Ask", "Bing", "Blekko", "Google", "Wikipedia", "Yandex"};
Table[
	TestAccuracy[
		SearchFor[engine, #]& /@ sampleQ, 
		sampleA],
	{engine, engines}
]

For the first category, we insist that the answer appear in the first page of search results.

For the second category, we conduct an “I’m Feeling Lucky” style of search, where the answer is sought in the contents of the first hit from the results page.

One might expect the questions on Jeopardy to get harder in successive rounds. So it is perhaps a surprising fact that search algorithms only seemed to suffer a slight decline in their accuracy in later rounds. The sample size here is 1,000 questions per point, with clues from the Jeopardy, Double Jeopardy, and then Final Jeopardy rounds appearing on the horizontal axis.