Super Smash Bros. Tourney

[elendiastarman]

In the game Super Smash Brothers Melee, Nintendo characters can be played against each other. It is possible to set up a tournament of 64 players where all players are computers. Each computer has a level that ranges from 1 to 9 (randomly chosen) where 1 is the easiest/weakest and 9 is the hardest/strongest. One can then pit the computers against each other and see who wins. Sometimes, a level 9 will not win; even a level 1 can win the tournament.

In this simulation, winners are chosen probabilistically according to a rule that figures in their respective strengths. Let p1 be the level of the first player of a 1 on 1, and let p2 be the level of the second player. The probability that player 1 wins is then ^p1/_(p1+p2) and likewise for player 2 only with p2 on the top instead of p1. The winner advances to the next level and the loser drops out. Levels remain the same at all times.

What is the probability that a level 9 will win?

What is the probability that a level 1 will win?

[rmillika]

I make it 0.333669262 that a level 9 will win and 0.000104453 that a level 1 will win. This was done in Excel so there will be rounding error. The sheet played each level against an even mix of levels to calculate the winning chance on the first round. For each round after that, it took the level distribution that came out of the prior round. The only checks were that the number of players was cut in half every round and that the results were reasonably monotonic.

[elendiastarman]

My Monte Carlo simulation done in python gives pretty much the same answer for level 9, but even a 1,000,000 tournament simulation hasn't given a level 1 win. Given that I've done it multiple times, I think one of our "programs" is flawed... :/ My program gave this as a result of one 1,000,000 tournament simulation:
[0, 92, 2337, 12022, 33761, 68517, 117765, 179275, 252147, 334084]. It seems that 9's win about 1/3 of the time and 8's about 1/4 of the time. An interesting consequence of the probability function is that it is easier for an 8 to win against a 9 than it is for a 1 to win against a 2, even though both pairs are separated by only one level. I believe this may be skewing it... Disregard the next two sentences... Plus, in a tournament where all players but one are level 9's and one is a level 1, there is a 1/1,000,000 chance that the level 1 will win. However, even in 10,000,000 tournaments, I haven't seen a single 1 win, which makes me think my program is flawed...

EDIT: D'oh! I was looking at the "0's", of which there are no players. In reality, I get an ~.0001063 chance for a 1 to win, which agrees with your result.

Code:

Code: Select all

from random import *

def fight(num1, num2):

    total = num1 + num2

    z = randint(1,total)

    if z > num1:
        return num2
    else:
        return num1

def tourney(levs):

    players = []

    levels = levs
    levelrange = [1,9]

    for i in xrange(0,2**levels):

        players.append(randint(levelrange[0],levelrange[1]))

#    print players
#    print ""

    for l in xrange(0,levels):

        winners = []

        for x in xrange(0,len(players)-1,2):

            p1 = players[x]
            p2 = players[x+1]

            winners.append(fight(p1,p2))

        players = winners
#        print winners
    return winners[0]

def montecarlo(times,levs):

    w = []

    for n in xrange(0,10):
        w.append(0)

    for i in xrange(0,times):
        win = tourney(levs)
        w[win] = w[win]+1

    w2 = []
    for j in w:
        w2.append((j*1.)/(times*1.))

    return [w,w2]

[rmillika]

My complete results are 1 wins 0.000104453, 2 wins 0.002418018, 3 wins 0.012064299, 4 wins 0.033487702, 5 wins 0.068734128, 6 wins 0.117823111, 7 wins 0.179552404, 8 wins 0.252146623, 9 wins 0.333669262. Note that the 8 probability is within 1/3 of a single win of yours. I think these agree pretty well.

[elendiastarman]

Sweet. Now tell me: how in the world do you do this in Excel?

[rmillika]

Here is the start of the sheet. Based on the preview, you will have to work on the spacing. The column headings should be clear, and the powers of 2 are the sum of the various Qty columns. Qty 1 is the average number of each level at round 1 = 64/9. Pwin1 is the probability that a character of that level wins his match. It considers the distribution of opponent levels. With the 1 under level being cell A2, the expression in C2 is:
=($A2/($A2+$A$2)*B$2+$A2/($A2+$A$3)*B$3+$A2/($A2+$A$4)*B$4+$A2/($A2+$A$5)*B$5+$A2/($A2+$A$6)*B$6+$A2/($A2+$A$7)*B$7+$A2/($A2+$A$8)*B$8+$A2/($A2+$A$9)*B$9+$A2/($A2+$A$10)*B$10)/B$11

The 64 at the bottom is a check that there are in fact 64 characters in that round. It is also used in the denominator of the win probability. Qty 2 is then just Qty 1 * Pwin 1, the quantity of characters of that level at round 2. Pwin2 is the probablity that a given character of that level wins round 2, given the distribution of opponents. The 32 shows that half the characters lost in the first round, as expected. The dollar signs let you copy this to all the other places. The sheet wrapped if I showed all the columns, but the idea should be clear.


[img]
Level Qty 1 Pwin 1 Qty 2 Pwin 2 Qty 3 Pwin 3 Qty 4
1 7.111111111 0.214329806 1.524123065 0.179976754 0.274306721 0.157107942 0.043095764
2 7.111111111 0.337750521 2.401781483 0.295011737 0.708553727 0.265470503 0.188100115
3 7.111111111 0.423292448 3.010079632 0.378653463 1.139777077 0.347058291 0.395569085
4 7.111111111 0.487466854 3.466430963 0.443217003 1.536381143 0.411374565 0.632028124
5 7.111111111 0.537904996 3.825102195 0.494945071 1.893215478 0.463648387 0.877786302
6 7.111111111 0.578819329 4.11604856 0.537494426 2.212353158 0.507100394 1.121885159
7 7.111111111 0.612789217 4.357612209 0.573198867 2.497778381 0.543857479 1.358435454
8 7.111111111 0.641507004 4.561827586 0.603637133 2.753688526 0.575394629 1.584457587
9 7.111111111 0.666139824 4.736994306 0.629923871 2.983945788 0.602773153 1.79864241
64 32 16 8

[/img]

[elendiastarman]

....wow....I had no idea that Excel could do such things! I'm amazed...

[Zkid]

Not that it affects the mathematics, but I just thought I'd point out that the probability of a player with higher level L1 beating a player with lower level L2 in Melee is much higher than L1 / (L1 + L2).