space and games

There are games (such as racing or DDR) in which players compete with one or more opponents, but the opponents do not interact. Each player performs individually, and receives some score for vis performance, and the player with the best score wins. I’ll call these “ordinal performance games.”

One might naively think that the best strategy is to ignore one’s opponents, and think only of maximizing one’s own score. After all, the players never interact, so your score depends only on your performance, right? That’s true, but the object is not to maximize your own score; it is to have a higher score than your opponents, and this depends on your opponent’s score as well.

For example, suppose we have a game with three player types, and possible scores of 1 through 5.

• Alf is consistently mediocre, always receiving a score of 3.
• Beth has adopted a risky strategy; she receives a score of 4 with probability 0.6 and a score of 1 with probability 0.4.
• Gam may succeed spectacularly, but usually plays poorly. He receives a score of 5 with probability 0.4 and a score of 2 with probability 0.6.

Suppose Alf and Beth play. Alf will always score 3. Beth has a probability of 0.6 of scoring 4, and thus winning, and a probability of 0.4 of scoring a 1, and thus losing. So p(Alf < Beth) = 0.6.

Suppose Beth and Gam play. Beth has a probability of 0.4 of scoring 1, in which case Gam is guaranteed to win. The other way for Gam to win is for Beth to score a 4 while Gam scores a 5; the probability of this is 0.4 * 0.6 = 0.24. Thus p(Beth < Gam) = 0.4 + 0.24 = 0.64.

Suppose Gam and Alf play. Gam can only win by scoring a 5, with probability 0.4. So p(Gam < Alf) = 0.6.

So Alf usually loses to Beth, who usually loses to Gam, who usually loses to Alf. This shows that your optimal strategy in an ordinal performance game can depend on your opponents.

On Overcoming Bias, Eli says:

I don’t think you could get up to 99.99% confidence for assertions like “53 is a prime number”. Yes, it seems likely, but by the time you tried to set up protocols that would let you assert 10,000 independent statements of this sort - that is, not just a set of statements about prime numbers, but a new protocol each time - you would fail more than once. Peter de Blanc has an amusing anecdote on this point, which he is welcome to retell in the comments.

Here’s the anecdote:

Conversation with squallmage at 2006-07-28 23:46:54 on OneTrueCalculus (aim)
(23:47:19) OneTrueCalculus: oi
(23:47:23) SquallMage: oi
(23:47:33) OneTrueCalculus: how likely would you rate it that 81,241 is prime?
(23:47:59) SquallMage: very
(23:48:03) OneTrueCalculus: you can go ahead and calculate it if you want, or just give me a probability
(23:49:03) OneTrueCalculus: obviously this would be the subjective sort of probability
(23:49:11) SquallMage: yes.
(23:50:30) OneTrueCalculus: well?
(23:50:35) OneTrueCalculus: or are you busy calculating?
(23:50:38) SquallMage: I said ‘very’.
(23:50:42) OneTrueCalculus: ah
(23:50:46) SquallMage: Quantify that if you must, I’m too tired to.
(23:50:55) OneTrueCalculus: ok
(23:51:10) OneTrueCalculus: I won’t quantify it for you, since I don’t know how you are calibrated
(23:51:22) OneTrueCalculus: okay, how about 7?
(23:51:46) SquallMage: the probability of it’s primacy, or as a quantification of ‘very’?
(23:51:55) OneTrueCalculus: the probability of 7 being prime
(23:52:02) SquallMage: 7 is prime.
(23:52:08) OneTrueCalculus: with probability 1?
(23:52:18) SquallMage: Yes.
(23:52:41) OneTrueCalculus: so will you accept this deal? If you ever find out that 7 is not prime, you will give me $100.
(23:53:10) SquallMage: Only if you explain to me in detail what brought you to propose that deal to me.
(23:53:37) OneTrueCalculus: I am trying to swindle you out of your cash and/or teach you a valuable lesson
(23:54:09) OneTrueCalculus: also, I am trying to figure out how overconfident people are
(23:55:42) SquallMage: Well. I would make a deal with you that I would give you $100 if it were ever proven to me that it was possible in base-ten to generate the quantity 7 by multiplying together any two integers other than 1 and 7.
(23:55:55) OneTrueCalculus: okay
(23:56:05) OneTrueCalculus: I am only talking about the standard natural numbers. No weird groups or anything
(23:56:20) OneTrueCalculus: base 10
(23:56:24) SquallMage: No, ‘7 and 1′ is not different than ‘1 and 7′ also.
(23:56:32) OneTrueCalculus: of course not
(23:56:39) SquallMage: Just checking.
(23:56:42) OneTrueCalculus: I wouldn’t use a cheap technicality like that
(23:56:44) SquallMage: Since I’m a language bastard.
(23:56:49) SquallMage: And I completely would.
(23:56:54) OneTrueCalculus: okay
(23:57:13) OneTrueCalculus: If you even honestly feel that it was a cheap technicality, I wouldn’t expect you to pay me.
(23:57:22) SquallMage: Anyways.
(23:57:23) OneTrueCalculus: Under those conditions, will you accept my offer?
(23:57:33) SquallMage: Yes.
(23:57:37) OneTrueCalculus: Okay.
(23:57:44) SquallMage: Tell me how I owe you $100 now
(23:57:48) OneTrueCalculus: you don’t
(23:57:52) SquallMage: Good.
(23:57:56) OneTrueCalculus: now
(23:58:03) OneTrueCalculus: will you accept the same offer, but for 11 this time?
(23:58:05) SquallMage: Not for 81241
(23:58:34) OneTrueCalculus: i.e. if you ever find out that 11 is not prime, you will give me $100
(23:58:49) SquallMage: I would make that deal under equivalent conditions
(23:59:00) OneTrueCalculus: okay. I’m asking you to make that deal.
(23:59:44) SquallMage: I did say that I would.
(00:00:00) OneTrueCalculus: okay, thanks
(00:00:04) OneTrueCalculus: how about 13?
(00:00:20) SquallMage: Yes.
(00:00:48) SquallMage: 17 also, and 19, and 23.
(00:00:54) OneTrueCalculus: thanks.
(00:00:57) OneTrueCalculus: What about 27?
(00:01:02) SquallMage: No thanks.
(00:01:05) OneTrueCalculus: 29?
(00:01:11) SquallMage: sure.
(00:01:13) OneTrueCalculus: 31?
(00:01:17) SquallMage: Yep.
(00:01:20) OneTrueCalculus: 33?
(00:01:24) SquallMage: Nah.
(00:01:26) OneTrueCalculus: 37?
(00:01:29) SquallMage: Yah.
(00:01:31) OneTrueCalculus: 39?
(00:01:35) SquallMage: Nah.
(00:01:37) OneTrueCalculus: 41?
(00:01:42) SquallMage: Yah.
(00:01:45) OneTrueCalculus: 43?
(00:01:51) SquallMage: Yah.
(00:01:54) OneTrueCalculus: 47?
(00:02:06) SquallMage: Yah.
(00:02:09) OneTrueCalculus: 49?
(00:02:17) SquallMage: Nah.
(00:02:20) OneTrueCalculus: 51?
(00:02:28) SquallMage: Yah.
(00:02:36) OneTrueCalculus: Thank you. I win.
(00:02:48) SquallMage: You know I’ve been up since this time yesterday.
(00:02:51) OneTrueCalculus: You can donate your money to the Singularity Institute for Artificial Intelligence
(00:03:06) SquallMage: I’ll forward you their message of receipt.

I still haven’t published it, but it’s now on the arXiv.

In the Odyssey, Athena says to Telemachus:

It’s true few men are like their fathers. Most of them are worse. Only very few of them are better.

Athena was pretty sharp! Of course, “better” and “worse” are rather vague terms, but we can talk more precisely if we consider reproductive fitness, defined as the number of offspring one has. Then we can restate Athena’s theorem as:

The expected fitness of a random organism is ≤ the expected fitness of its parent.

Intuitively, one can reason as follows: the expected fitness of a random organism is the average fitness of the population. But the expected fitness of its parent is above average, because we already know that the parent has at least one child.

A rigorous proof is left as an exercise to the reader.

Zhan Shen, a fellow student, mentioned this really cool game last week in his practice thesis defense on insurance theory. Zhan talked a bit about applications of an asymmetric version of the game (with different army sizes). His defense is today.

I’m working on a paper on this topic, but I figured I would post about it now and clear up some confusion.

Let’s say we have an agent interacting with an environment. The agent sends the environment some number (an action), and the environment sends the agent some number in response (a perception).

When we have an infinite set of hypotheses, the expected utility of some action is determined by an infinite series. It’s important for that series to converge, or else we won’t (in general) be able to compare the expected utilities of two different actions.

Given the following assumptions:

• We have some finite set of data about the environment.
• We assign a nonzero probability to all computable hypotheses consistent with our data.
• Either this probability distribution is computable, or it is bounded below by some positive computable function.
• Our utility function is determined by our perceptions, and is unbounded.
• Either this utility function is computable, or it is bounded below in absolute value by some unbounded computable function.

…then it follows that our expected utilities do not converge.

This seems like a pretty strong reason to stick with bounded utility functions. It certainly seems much more plausible to me now than it did before that my utility function is bounded (to the extent that I can be said to have a utility function).

But we shouldn’t jump to conclusions. Here are some reasons why the above might not apply:

• You might have an uncomputable utility function.
• You might have a utility function which is not determined solely by your perceptions.
• You might assign a probability of zero to some hypotheses which are consistent with your data.

In Decision Theory, agents make decisions which maximize the expected value of a utility function. A utility function for a Chess or Go player might be: “1 if I win, -1 if I lose, 0 if I draw.”

Because we have to work with limited computational resources, we can’t search the entire game tree when we play games like Chess and Go. In this case, we would like a way to approximate the expected utility of a node in the game tree, using local properties of that node. I’m calling such an approximation a “board evaluator.” Board evaluators have been used with some success in Computer Chess.

A move suggester is something that looks at a situation and returns a list of moves, possibly with numerical values attached; higher values are preferred. We can sum the values returned by several different move suggesters, and select the move with the highest value. When a mosquito lands on your arm and you twitch, you may be using something like a move suggester.

More formally, we can define a move suggester as something which takes two adjacent nodes in the game tree and estimates the change in expected utility, compared to a board evaluator, which estimates the expected utility of a single node. So a board evaluator takes a node as its argument, while a move suggester takes an edge in the game tree.

Board evaluators have a major advantage over move suggesters: they allow us to use search algorithms such as minimax.

So it would be nice to have a way to build a board evaluator out of move suggesters. I know of three ways to do this:

• The naive method, as I’ll call it, considers the sequence of moves used to reach the position. We evaluate each move, and sum these values to estimate the value of the current position. Because we are adding up many terms, we will usually accumulate a significant error.
• Playout Analysis uses move suggesters to continue play from a given position until the game is finished. Then we determine who won the game. We can perform many randomized iterations of this analysis, and take some sort of average; this average is then used as the value of the original position.
• Tewari, developed by Honinbo Dosaku in the 17th century, works by permuting the sequence of moves used to reach a board position. The naive method is applied to each such permutation, and we average these values.

I’d be interested in examples of these methods (particularly Tewari) being used to analyze real-world decision problems.

*** Sol has joined #milky_way
<Sol>      2, 3, 5, 7, 11, 13, 17, 19
<Vega>     god, another n00b
<Sol>      ne1 wanna trade with me?
<Castor>   ok, you gotta build a starship first
<Sol>      how do i do that
<Vega>     Nova c:
<Castor>   nova c
<Procyon>  Nova c
*** Sol has quit GRC (timed out)
<Vega>     hahaha

I like this format for human names:

Where:

• G is a given name.
• Y is a Y-Chromosomal Name, which is inherited from the father.
• M is a Mitochondrial Name, which is inherited from the mother.

This makes it easy to trace Y chromosomes and mitochondria, which are passed on directly from father to son and from mother to child, respectively. Optionally, girls could drop the Y-chromosomal name, since they do not inherit Y chromosomes.

The letters of the alphabet, A to Z, just hanging out. These letters prefer to be near letters which occur in similar contexts.