Information Theory in a Card Guessing Game

EE376A (Winter 2019)

by Albert Gural, Mackenzie Simper, Ernest So

Abstract

In this work, we explore tools in information theory to analyze a card guessing with feedback. Consider a card guessing game where the player knows the initial composition of a shuffled deck (e.g. 3 Jacks, 3 Queens, 3 Kings) and guesses the next card in the deck with the goal of maximizing the number of correct guesses until no cards remain. A dealer gives the player feedback on their guess, which may give the player information to use for the following guesses. We focus on incomplete feedback where the player is told whether their guess was correct. In this scenario, the player’s guess influences both the amount of information they know about the deck and the number of correct guesses. We will explore different strategies for this game and information theoretic ways to analyze it.

Outreach Event

For the outreach event at Lucille M. Nixon Elementary School, we wanted to teach kids about probability and how to think about strategies for guessing games. Since our project was about a card guessing game, we had them play the incomplete feedback game, and afterwards we explained how to implement an effective strategy to maximize the number of correctly guessed cards.

The kids played the card game with 3 Jacks, 3 Queens and 3 Kings with incomplete feedback. In the beginning we had the computer simultaneously play along with the kids using the optimal strategy. We created a modified version of the simulation that outputted the possible states along with their probabilities in a bar graph format for easy viewing. After a few kids, we changed the way we played the game with the kids to use the simulation to explain how the optimal strategy works.

We noticed that the kids and their parents easily forgot what cards they had previously guessed and what the results were (and then proceeded to guess randomly). To help them with this we decided to place each guessed card on the table: face up if they guessed correctly and face down if they guessed incorrectly. This made the game more visual. In addition, one of us would write down the guess they made so that they can see their incorrect guesses as well.

Second, we also realized how short we could keep the kids’ attention for. To address this, after they had finished guessing the deck, we would flip all the cards over and show how the computer simulation would play on the same deck. This gives us a chance to point out how the states evolve when a correct guess is made, and how the states split when an incorrect guess is made. Finally the bar graph was an easy visual way to show this how this information would be used to determine the next guess in a tractable way for the kids. An example case of the output we showed to the kids when the computer played the game is shown in below.

CPU opponent for outreach, showing internal state for teaching purposes

In the example above, we would point out that the CPU correctly guessed Jack, so now it knew there was a 100% chance of being in the (2,3,3) state. However, when it incorrectly guessed Queen, two possible states emerged: one where Jack was the correct card (1,3,3) and one where King was the correct card (2,3,2). We would also point out how because there were fewer Jacks to start with, the (1,3,3) state was less likely than the (2,3,2) state. When the CPU guessed the first card incorrectly, we would jump immediately into this “No” case. When the CPU guessed a sequence of card correctly, we would speed ahead until the first “No.” After showing an example of state splitting at a “No,” we would speed through the rest of the cards to get the final result, which we compared to the student’s scores

We recorded the results from the outreach, and we found that on average, the computer had a slight advantage compared to the kids. On average across 9 games, the kids guessed 3.222 cards correctly for the 9 card deck, and the computer guessed 3.889 cards correctly.

For more details, please see our project report below:

Simulation Code Link: https://github.com/agural/ee376-card-game

Leave a Reply