Of Math and Magic – The Tournament Simulator

Editor's Note: This article features equal parts code and results, shared in the form of a story. You can safely skip the code to see what happens with Chris's model, but if you want to see how it work it's there too. Enjoy!

Kate is preparing for the upcoming World Series of Rock-Paper-Scissors. She would normally employ a strategy of picking each round at random (and with an equal probability), but the organizers have decided to enact a new rule this year: You must pick one of rock, paper, or scissors, and throw the same object in every round of the competition. Since the organizer is throwing the tournament on its online platform, RPS Online , each match must have a winner and pairings that would normally end up as a draw are instead decided by flipping a coin.

The structure of the event is that three hundred players are allowed to join (otherwise, the servers might crash), and there are eight rounds of Swiss followed by a cut to a single-elimination Top 8. The only prize in the tournament goes to first, and it's the ability to strike one Magic article off the Internet (which Kate will greatly value). Knowing the value of the prize, Kate gets in contact with Chris. Once he hears Kate's dilemma he decides to construct a model to simulate the tournament and determine the best course of action for Kate to take in order to win the tournament.

The Model

Chris decides to build his model in MATLAB since it’s what most of his modeling work is in and it was the only language he had installed at the time he talked to Kate. Chris began by deciding what inputs into the model were needed and determined that the number of players, number of rounds, % of the field choosing each object, and the object-vs.-object percentages were needed, so he asked for the following input where Deck A was Rock, Deck B was Scissors, and Deck C was Paper. Chris assumed the field would be evenly split between the three objects to begin with:

players=300;
rounds =8;
DeckA = 1/3;
DeckB = 1/3;
AvsB = 1;
AvsC = 0;
BvsC = 1;

Once these inputs were taken in, Chris could create a matrix of matchup %s and a vector of what deck each participant played:

%Now let's creat the metagame based on what we inputted
DeckC=1-(DeckA+DeckB);
Decks=ones(players,1);
playersv=(1:1:players)';
%This is super ineffeicent, but I don't care
for i=floor(players*DeckA)+1:players
if i/players>DeckA+DeckB
Decks(i)=3;
else
Decks(i)=2;
end
end

Since Chris decides to use a Monte Carlo technique rather than a Markov Chain to reduce the time and effort needed to make the simulator, he decides to simulate the tournament ten thousand times in order to form an accurate picture of the results.

Once this is all set up, Chris just has to make a pairing algorithm and a way to find the result of each match in order to complete most of the project. Chris needs to make sure that when an odd number of players have a particular number of points to randomly pair one player up or down. The only thing not working in the final simulation is that there's no check to see if players play the same opponents multiple times, but someone after reading this article can choose to improve the simulator and e-mail Chris (chrism315 at gmail dot com) the updates to improve it for future work. In all seriousness, the pairing algorithm needs a lot of optimization (it’s a derangement with a special condition), so if you want to help out, please feel free. Source code will be available for download. I don’t have the time to optimize this further.

for i=1:rounds
%For each round, we need to group players by record and then pair them
lplayers = playersv;
lpoints=points;
%Group people with similar records
for j=1:i
loopgroup = [];
loopgroup=find(sum(lpoints,2)==(j-1)*3);
if size(loopgroup)/2~=floor(size(loopgroup)/2);
[loopgroup, lpoints] = oddplayers(loopgroup,lplayers, lpoints, j);
end
pairings(loopgroup,i)=pair(loopgroup);
end
lpoints = [];
points(:,i) = winner(Decks, pairings(:,i), Matches);
end
function [pairs] = pair(players)

count=size(players,1);
seed = randperm(count);
lpairs=zeros(count,1);
for i = 1:count
j=1;
while lpairs(i)==0
if i~=seed(j)
if lpairs(seed(j))==0
lpairs(i)=seed(j);
lpairs(seed(j))=i;
seed(j) = [];
end
j=j+1;
else
j=j+1;
end
end
end
pairs = players(lpairs);

function [newpairs, lpoints] = oddplayers(loopgroup,lplayers, lpoints, j)
%UNTITLED Summary of this function goes here
% Detailed explanation goes here
k = randelement(find(sum(lpoints,2)==(j)*3),1);
lpoints(k,:)=(j-1)*3;
newpairs = [loopgroup;k];
end
function [ results ] = winner(Decks, pairings, Matches)
%UNTITLED4 Summary of this function goes here
% Detailed explanation goes here
results = ones(size(pairings,1),1);
for i=1:size(pairings)
if results(i) == 1
player1 = i;
player2 = pairings(i);
deck1 = Decks(player1);
deck2 = Decks(player2);
result = rand;
if result < Matches(deck1, deck2) results(player1) = 3; results(player2)=0; else
results(player1)=0;
results(player2)=3;
end
end
end

Chris knows this will run all the Swiss rounds of the tournament, and the only thing left to do is to program two more functions: a way to rank players and cut to a Top 8 and a way to play the Top 8 out. Chris came up with the following.

%Player Ranking Time – Tiebreakers and everything
Top8 = PlayerRank(points, pairings);
%Let's play the top 8s
Winners = runtop8(Top8, Decks, Matches);
function [T8] = PlayerRank(points, pairings)
%UNTITLED3 Summary of this function goes here
% Detailed explanation goes here
MWP = sum(points,2)/(size(points,2)*3);
MWP = (MWP<1/3)*1/3+(MWP>=1/3).*MWP;
tiebreaker1 = sum(MWP(pairings),2)/size(points,2);
[points, players]=sort(sum(points,2), 'descend');
if points(8)==points(9);
spots=find(points==points(8));
tied=players(spots);
[~, playerst]=sort(tiebreaker1(tied), 'descend');
players(spots)=tied(playerst);
end
T8=players(1:8);
end
function [top8results] = runtop8(Top8, Decks, Matches)

Top81=[Top8(1) Top8(8) Top8(4) Top8(5)];
Top82=[Top8(2) Top8(7) Top8(3) Top8(6)];
Decks1=Decks(Top81);
Decks2=Decks(Top82);
pairs=[2; 1; 4; 3];
results1=winner(Decks1, pairs, Matches);
results2=winner(Decks2, pairs, Matches);

Top41=Top81(find(results1>0));
Top42=Top82(find(results2>0));
Decks3=Decks(Top41);
Decks4=Decks(Top42);
pairs2=[2;1];
results3=winner(Decks3, pairs2, Matches);
results4=winner(Decks4, pairs2, Matches);

Top2=[Top41(find(results3>0)) Top42(find(results4>0))];
Decks5=Decks(Top2);
results5=winner(Decks5, pairs2, Matches);
Winner=Top2(find(results5>0));
top4 = [Top81(find(results1>0)) Top82(find(results2>0))];
top8results=[top4 Top2 Winner];

end

Once this is done all that’s left is to come up with a way to keep track of results, which was fairly quick to throw together:

windecks=Decks([Top8' Winners]);
for i=1:nDecks
top8count(i)=top8count(i)+sum(windecks(1:8)==i);
top4count(i)=top4count(i)+sum(windecks(9:12)==i);
top2count(i)=top2count(i)+sum(windecks(13:14)==i);
wincount(i)=wincount(i)+sum(windecks(15)==i);
end

end
top8count/(8*tournaments)
top4count/(4*tournaments)
top2count/(2*tournaments)
wincount/tournaments

Running the Simulation

With the assumption that around a third of the field will play each object (this is the Nash equilibrium of the tournament, for what it’s worth), Chris generates the following results and shows them to Kate (for each set of results that is the % of the Top 8/4/2/winners made up by each object in rock-scissors-paper order):

top8count =
0.3392 0.3319 0.3288
top4count =
0.3416 0.3284 0.3300
top2count =
0.3434 0.3241 0.3325
wincount =
0.3384 0.3224 0.3392

Kate comments that it was pretty obvious that if the objects were chosen at equal rates that any object she chooses would be around the same. After this nonchalant observation, Kate reveals that through her dark power, she has obtained the metagame for the RPS tournament and that it will be forty percent rock, one-third scissors, with the remaining players on paper (around twenty-seven percent).

Before running the actual numbers, Kate and Chris discuss their thoughts. Kate thinks that rock will be the best choice, as it’s the most popular, so it would most likely be the best choice. Chris argues that paper will be the, “Best choice, not close,” as it has a win against the most popular object and its bad match is the least powerful. Chris and Kate continue to argue, but in order to make sure the matter is resolved Chris decides to run the simulator with the divined metagame. The results shock both Chris and Kate as they look to the screen:

top8count =
0.1357 0.3101 0.5543
top4count =
0.1070 0.4341 0.4588
top2count =
0.1046 0.5849 0.3105
wincount =
0.1333 0.7031 0.1636

While in shock to discover that scissors wins around 70% of the overall tournaments, Drew Levin randomly enters the room. He explains that, “Paper is going to Top 8 a bunch, and you have to win the tournament; ergo, you need to beat Paper reliably to win the only prize. Second is same as last, and Paper is the best Swiss foil, making Scissors the best Top 8 foil.” As Drew silently walks out, Kate decides that she will go with the numbers and choose scissors as her object for the event. (At the site, it’s determined that the organizer has the wrong number of rounds and there should be one more. Ghosts of former MOCS competitors who missed making Top 8 after going X–1 howl and scream for it to be changed, but their voices go unheard. Again.)

Kate sticks to the plan of scissors and is lucky to dodge rocks during the Swiss and makes it to the Top 8. She easily beats her Top 8 opponent Alex, who attempts to use two different objects simultaneously but, luckily, Drew comes back to deal with this situation as well. In the Top 4, she’s paired against Holly in the scissor mirror, but she wins the coin flip because she believed that she believed that she could. In the finals, she’s paired against an unknown young girl who is named after a precious stone. Kate and the girl decide to go and do something else, leaving Chris alone in the arena to claim the prize in lieu of both of them.

Choosing the Article – My 2012 Magical Year in Review

Razorverge Thicket
Chris is stunned at first after being left alone, but he reads some boggle comics, checks in with the motivational penguin, and talks to his real friends and realizes he doesn’t need people who don’t value him in his life. Chris moves on and proceeds to the task at hand.

First to mind is the articles not even worth considering wiping. In terms of Magic theory, Paulo Vitor Damo da Rosa wrote some greats this year, and basically any theory article by him (especially the one on lands) is worth reading and learning from. Craig Wescoe's 7 Exercises was another excellent theory article and something that should be emulated way more as a tool to teach more advanced ways to think about more advanced strategic decisions. The final excellent theory article was by Michael Flores and his take on Practical Leveled Thinking (which namedrops me, so it's even better!). Speaking of me, you should all read my Tiebreakers article.

More important than the theory and gameplay articles produced this year was the growth and slight maturing of the Magic community. The community was, in some cases, forced to become more accepting, and it saw many articles form community leaders on acceptance (and not being shitty human beings). My favorite article on inclusiveness is Chapin's Words Mean Things, and it's definitely well worth the read if you missed it earlier in 2012. My personal choice for article of the year, however, is Abe Sargent's And on That Day, Like Any Other for its rawness and reliability.

For more on my tournament simulator feel free to tweet at me with any questions about it.

-Chris Mascioli
@dieplstks on Twitter (Follow me!)

A Personal Bit

I returned from a seven-month trip to Scotland on November 1. During this trip I had my heart broken, but I was able to meet a ton of awesome new friends. I returned right after Hurricane Sandy to get to throw away basically everything I owned before leaving, as the storm had let around four feet of water into my house. In December I was diagnosed with adult ADHD and depression, and have been struggling against the side effects of the medication for most of the past month. On top of all this, my grandfather passed on December 24, so overall, 2012 has not been the best year.

<< Of Math and Magic – The Opening Hand

Comments

comments