Matchmaking
Overview
Imagine our list of gladiators for a venue like a deck of cards. If you wanted to create random pairings, you could shuffle the deck and deal them off in twos — so after the shuffle, Player A v Player B, Player C v Player D etc.
The trouble we would have with this approach is that we could have up to 10,000 players in our deck! Trying to shuffle an array of players this big would burn through the gas limit for a single transaction in Solidity, so it isn't possible.
To get around this, we moved away from a "shuffle then deal" method to a "random draw" method. (Technically, the name of the algorithm we're using is called the Fisher–Yates shuffle.) Instead of shuffling our list of players, we divide the list into two piles so we have an "unmatched pile" and a "matched" pile, and we keep a cursor to keep track of what place separates the two lists.
When we want to create a match, we call Chainlink (which we're using for a trusted source of randomness) and ask for two random numbers. We then map the random number to a place in our list, essentially turning it into a "10,000-sided dice roll" (or however many players are in the list).
When we've chosen the two random slots, we pull out whichever players were at the indices from the list: this is our match-up. We then shuffle these two players from the "unmatched pile" to the "matched pile". Finally, we update our cursor, so that the next time around, we know that there are now 9,998 players in the "unmatched pile" and 2 in the matched pile.
Doing it this way allows us to create matches incrementally over a number of transactions and pick back up where we left off. Every permutation is equally as likely.
If we end up with an uneven number of players in an arena, one lucky player gets a by to the next round (so is marked as a win without having to fight).
Match Making — Technical Details
Random match-ups for daily battles is the crux of our game engine so we wanted to give an overview of how it works:
Draw not shuffle
As we mentioned in the overview in the Gitbook — we’re doing a “random draw” rather than a “shuffle the whole deck” approach to randomising who-faces-who in battle.
Since this is a core part of our game engine we wanted to share more technical details on how this works.
Fisher Yates Algorithm
We’re using the Fisher Yates algorithm to shuffle our list of gladiators. The main benefits of this is that it:
Allows us to shuffle the list in-place (without extra memory/gas overhead)
It allows us to split the shuffle across multiple transactions and pick up where we left off.
Broadly what we’re going to do is:
Divide the list into two sub-lists — the “unsorted group” (yellow) and the “sorted group” (green). At the start the entire list is the unsorted group and we have no-one in the sorted pile
Next we want to choose a position in the list at random, we take the gladiator in that slot and swap them with the last gladiator in the unsorted group (blue boxes, E swaps with J):
Finally, we move the cursor pointing at the end of the unsorted group one position to the left (as “E” has already been drawn and placed in the sorted section, we don’t want them shuffled again).
We then repeat this same process for the Cyber Stadium gladiator list.
If we have an odd number of players (e.g. let’s say our final list didn’t have player “E” on the end), then the last player without a match receives a by (i.e. they’re counted as a winner without the risk of fighting)
How do we pick the random position to swap?
We can’t have truly random numbers on-chain so we’re making use of Chainlink’s Verifiable Random Function (VRF), which is an Oracle that we can call out to in order to get a random number back into our contract.
We use this value to seed our own pseudo random number generator (PRNG), which provides a sequence of random numbers for us to use when we’re doing the draws.
(We initially wanted to call Chainlink once for each gladiator, but were hitting up against gas limitations, the PRNG gave us a more lightweight alternative to this).
What does our RNG look like?
Our PRNG is a "linear congruential generator" (LCG), which has the property that it won't repeat values until it's cycled through every possible value. This should make it good for us to pick random indices, as the space of possible values we have is quite large and then we're mapping that down to ~10k possible indices in the list.
The formula for producing the next random number in the sequence is:
(a * currentValue + c) % m
Where a, m and c are all constant values:
m is the modulo — i.e. the "space" of possible random numbers that we can output. For us, we're setting this to 2⁶⁴.
a is the multiplier — we've set this to 0xd1342543de82ef95 which is taken from a paper by Guy Steele (one of the creators of Java) & Sebastiano Vigna. The researches performed a “brute force”, exhaustive search to see what values of “a” produced good randomness for corresponding values of “m”
c is the increment — according to Donald Knuth, for the LCG to work, the main property that has to hold true is that it should be a "relative prime value" in the range 1 and m. (i.e. it's OK if it's not a true prime, so long as in the sequence 1..m, c's only factors are c and 1). The c value we've chosen is 1442695040888963407, which is a value used by Donald Knuth in MMIX, and which is a relative prime for 2⁶⁴.
So long as the PRNG produces "uniformly random" values (i.e. randomValue % listSize is as likely to produce any of the 10k values) it should be good enough for our shuffling.
Implementation
Since all the variables within our LCG are constants, you should be able to get the same outputs if you want to follow a day’s rolls and verify that we’re producing the random numbers we’d expect. E.g. to roll your own LCG in Python, the code would be:
m = 2**64
a = 0xd1342543de82ef95
c = 1442695040888963407
def next(current):
return (a * current + c) % m
Example
For a day's match-up for each venue, we'll call chainlink once & use that as the initial seed to the LCG. Then we'll call the LCG once for each player during the shuffle.
With the examples below, I started with a random dummy seed of 55372938631957857473204343793143656372836156694608278752362314866043812083413, so you should be able to follow along the logic using that initial value & produce the sample results.
Shuffle One
Shuffle Two
Shuffle Three
Shuffle Four
Shuffle Five
Shuffle Six
Shuffle Seven
Shuffle Eight
Shuffle Nine
Matches
Player One | Player Two |
D | A |
G | F |
B | H |
J | I |
C | E |
Verification
We tested this out with a Chi Squared Test, which is a test to verify if the observed output is within a tolerance of the expected output (i.e. how the numbers we rolled were distributed versus what you’d expect). To do this we generated a stream of 2¹⁷ values (i.e. 131,072) between 0 and 2¹⁶ (so the values ranged from 0–65,536) and checked that the distribution was within a significance level of 5%
Events
You can also replicate our results from on-chain, the following events will be emitted each day:
Match Making Contract:
event RequestSent(uint256 requestId);
With the request ID sent to Chainlink
event RequestFulfilled(uint256 requestId, uint256[] randomWords);
When we receive a response from Chainlink, with the random number they provided.
event NextRandomNumber(uint256 next, uint256 current, uint m, uint a);
For each “roll of the dice” you can see the number that was produced (next), the number that seeded that call (current)
event MatchupCreated(uint256 dayIndex, PlayState venue, uint256 playerOne, uint256 playerTwo, bytes32 battleId);
The match-ups as they’re emitted
If you read the list of gladiators in a venue once the contract locks, you should be able to produce the same verified match-ups using the events emitted.
Mitigations
The random seed is only requested from Chainlink after the Stadium contract has been locked. At that stage, it’s impossible for players to move gladiators between arenas until the battles have taken place and reopened again.
The PRNG is also re-seeded once per day and per venue.
Last updated
