Skip to content

Happy Birthday Ken

September 15, 2017


It was just Ken’s birthday

Kenneth Regan’s birthday was just the other day.

I believe I join all in wishing him a wonder unbirthday today.

The idea of unbirthday is due to Lewis Carroll in his Through the Looking-Glass: and is set to music in the 1951 Disney animated feature film Alice in Wonderland. Here is the song:

MARCH HARE: A very merry unbirthday to me
MAD HATTER: To who?
MARCH HARE: To me
MAD HATTER: Oh you!
MARCH HARE: A very merry unbirthday to you
MAD HATTER: Who me?
MARCH HARE: Yes, you!
MAD HATTER: Oh, me!
MARCH HARE: Let’s all congratulate us with another cup of tea A very merry unbirthday to you!
MAD HATTER: Now, statistics prove, prove that you’ve one birthday
MARCH HARE: Imagine, just one birthday every year
MAD HATTER: Ah, but there are three hundred and sixty four unbirthdays!
MARCH HARE: Precisely why we’re gathered here to cheer
BOTH: A very merry unbirthday to you, to you
ALICE: To me?
MAD HATTER: To you!
BOTH: A very merry unbirthday
ALICE: For me?
MARCH HARE: For you!
MAD HATTER: Now blow the candle out my dear And make your wish come true
BOTH: A merry merry unbirthday to you!

Ken’s Work

Ken is best known for work in theory and in particular in almost all aspects of complexity theory. But I wanted—in the spirit of an unbirthday—to point out that Ken is quite active in many other areas of computer science research. Here is one example that is joint with Tamal Biswas: Measuring Level-K Reasoning, Satisficing, and Human Error in Game-Play Data. We discussed it before here.

The problem is that Ken and Tamal want to be able to study levels of play in chess but are stalled currently by issues Ken raised last May in this blog. I wish them well in making strides to better understand how to model game play in chess that captures the notion of levels.

For me the following game created by Ayala Arad and Ariel Rubinstein really helps me understand the kind of thing Ken and Tamal are interested in capturing.

You and another player are playing a game in which each player requests an amount of money. The amount must be (an integer) between 11 and 20 shekels. Each player will receive the amount he requests. A player will receive an additional amount of 20 shekels if he asks for exactly one shekel less than the other player. What amount of money would you request?

The point is there are levels of thinking that a player can naturally go through. Here is a quote from their paper that should give the flavor of what is going on: The choice of 20 is a natural anchor for an iterative reasoning process. It is the instinctive choice when choosing a sum of money between 11 and 20 shekels (20 is clearly the salient number in this set and “the more money the better”). Furthermore, the choice of 20 is not entirely naive: if a player does not want to take any risk or prefers to avoid strategic thinking, he might give up the attempt to win the additional 20 shekels and may simply request the highest certain amount.

Read the paper for how Arad and Rubinstein analyze the game. The trouble is that if you take a risk and select 19 then you at least have a chance to get the bonus 20: if you reason that your opponent is playing safe that is a great play. Of course if they reason the same way, then you lose one shekel. This type of “levels” of playing are central to many games including chess.

An example is that a move may have one refutation the computer at high depth can spot but otherwise bring higher returns than playing it safe with the computer’s “best” move. How can we judge when such moves can be expected to pay off? Risky opening `novelties’ have been tried many times in chess, and in one famous game where Frank Marshall had saved up a gambit for nine years, the human player José Capablanca did find the refutation at the board.

Open Problems

We all wish that Ken has many more birthdays and unbirthdays. We also hope he makes progress on his open problems about depth of thinking and levels of play. What should you select in the simple coin game?

Advertisements
No comments yet

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