Nash equilibriums

[David Schneider-Joseph]

Given the StarCraft competition results, there are two Nash equilibriums for which a random pairing can be expected to give even odds:

Equilibrium 1:
Skynet 14/29 of population
Aiur 11/29
UAlbertaBot 4/29

Equilibrium 2:
Skynet 15/34
Aiur 15/34
ItayUndermind 4/34

David

[David Schneider-Joseph]

This had an error: "equilibrium 2" can be invaded by UAlbertaBot. Only the first is a real equilibrium.

[David Schneider-Joseph]

For those who are curious, the computer program I wrote to figure this out is quite simple:

1. Create a system of linear equations out of the game history between bots, which satisfy the criteria that each bot has even odds against a random member of the population.
2. Find all possible solutions, of which there are 2^N (N = number of bots), since every bot may be either 0 or some other value.
3. Remove any solutions in which any bot < 0 (this implicitly removes solutions in which any bot > 1).
4. For any solutions in which a bot = 0, make sure that bot's win odds are <= 50%, otherwise remove that solution.

The only solution remaining after these four steps is "equilibrium 1".

[Dave Churchill]

While this calculation takes the bots win % against each other into
account, it's pretty much just a novelty, since it doesn't consider
the actual gameplay of StarCraft.

From an intuitive point of view, Nash equilibrium states "If each
player has chosen a strategy and no player can benefit by changing his
or her strategy while the other players keep theirs unchanged, then
the current set of strategy choices and the corresponding payoffs
constitute a Nash equilibrium."

So while this holds true for the strict win percentages, it is quite
false that choosing a different (StarCraft) strategy for one of the
bots would not improve its results.

Also, this tournament involved playing 1v1, so I'm not sure how your 3
players enter into a Nash equilibrium...

--
-------------------------------
Dave Churchill
cda...@cs.ualberta.ca
dave.ch...@gmail.com

That's the thing about people who say they hate computers. What they
really hate is lousy programmers.

[Dave Churchill]

I misunderstood what you were saying. Your game is in picking bots, I
thought you meant for StarCraft itself, apologies :)

[David Schneider-Joseph]

On Aug 21, 2011, at 10:38 PM, Dave Churchill wrote:

> While this calculation takes the bots win % against each other into
> account, it's pretty much just a novelty, since it doesn't consider
> the actual gameplay of StarCraft.
>
> From an intuitive point of view, Nash equilibrium states "If each
> player has chosen a strategy and no player can benefit by changing his
> or her strategy while the other players keep theirs unchanged, then
> the current set of strategy choices and the corresponding payoffs
> constitute a Nash equilibrium."
>
> So while this holds true for the strict win percentages, it is quite
> false that choosing a different (StarCraft) strategy for one of the
> bots would not improve its results.

Indeed, and I certainly wouldn't claim that. What I did was ask the question: suppose you had a population of AIs which regularly play each other one-on-one using one of the thirteen strategies that these bots use. If we let natural selection work over time to modify the proportional representation of each AI in the population, what would be a stable mix for this process to converge on? That's the question I answered, and no other. Identifying a Nash equilibrium always requires some definition of the set of possible strategies; I chose the set of these thirteen.

The related term "evolutionarily stable strategy" may evoke the right connotations here.

> Also, this tournament involved playing 1v1, so I'm not sure how your 3

> players enter into a Nash equilibrium…

I hope my explanation above addresses this point. However, separately, I have been giving quite some thought to a competition with greater than two players per game, in which non-zero-sum player interactions might add a great deal of depth. What are your thoughts on this?

[David Schneider-Joseph]

Oops, I sent this before seeing your follow-up. Well, my question about > 2 players per game stands. :)

[Dave Churchill]

My thoughts on analyzing 3 player starcraft: good luck ;)

[David Schneider-Joseph]

On Aug 21, 2011, at 11:47 PM, Dave Churchill wrote:

> My thoughts on analyzing 3 player starcraft: good luck ;)

Indeed, but my question is more about the viability of such a tournament than the ease with which the game can be analyzed.

David

[Dave Churchill]

I don't think its interesting from a human or ai point of view. King
making and luck are way too big of a factor to make it a 'good'
competitive game

On 8/22/11, David Schneider-Joseph <dav...@gmail.com> wrote:

[Mike Preuss]

Hi U guys,

very interesting computations, but I was just wondering if the equilibria can

be computed accurately on the existing data basis, and if this data is not

very much influenced by the actual choice of maps and starting positions.

Cheers, Mike

[David Schneider-Joseph]

No doubt there is a great deal of noise which could affect the exact proportions. However, I think the basic composition of the population should be fairly robust to small differences in results, given how dominant Skynet was and how Aiur only exists in the population because of its ability to challenge Skynet.

David

[Mike Preuss]

Ah yes, I see, yes, then the equilibrium description makes sense, however I find a domination relation more intuitive. It is not transitive in this case, interestingly, but this is probably exactly the case when a Nash equilibrium of more than one strategy exists.

[David Schneider-Joseph]

Over many games, those factors average out, especially if you have several rounds where the weakest competitors are eliminated, and with them their ability to kingmake. Real-time strategy's social element was one of the points explicitly called out in Michael Buro's challenge in 2003:

> RTS games offer a large variety of fundamental AI research problems, unlike other game genres studied by the AI community so far: … In RTS games groups of players can join forces and intelligence. How to coordinate actions effectively by communication among the parties is a challenging research problem.

There are compelling arguments that even the most primitive animal intelligence can be understood only in the context of a complex social environment consisting of shifting opportunities for competition and cooperation.