Growing up, I loved playing sports video games. In particular, I liked playing the "manager" or "franchise" mode where I was able to select my team's players as part of a snake-format fantasy draft. When I learned to program, I became interested in building a simulated version of a snake draft because I wanted to see how teams would select players based on incentives I could tweak as part of the simulation parameters. I also was curious to see what kinds of teams would form if teams had to choose between real-life players and many new fictional, randomly-generated players.
With that said, this project implements a simulation of an fantasy-style NBA draft in Go.
The player package implements a representation of an individual player, either real or generated. Complete profiles of current NBA players are scraped (using Python) from the NBA2K Player Database. When first loaded, each current NBA player has a name, set of positions they can play, overall rating, and a set of attributes (such as pass accuracy, speed, and interior defense) that are aggregated into six composite category scores used in the popular NBA 2K video game franchise (see here for an example). The player package also has the capability of generating players with random names, position eligibility, and attributes. Once all real and generated players are pooled, the package computes Z-scores for each of the six composite category scores across the pool.
The depth chart package represents a single team's depth chart. Depth charts are used to keep track of starting players and backup players at each position on a team. As such, each depth chart instance maps each of the five positions in (PG, SG, SF, PF, C) to a ranked slice of players at that position. The depth chart simultaneously represents the team depth in a slightly different way, maintaining a slice of starting players, a pointer to a sixth-man, and a slice to the other reserves. The depth chart package assigns players to starting positions using a Hungarian algorithm to maximize overall ratings among position-eligible players. Given a depth chart with players slotted into positions as starters and reserves, the depth chart assigns playing time (minutes per game) to players based on their starting/sixth man/reserve status and other configurable parameters as part of the config package.
The team package represents a single NBA team in the draft. Each team has a name, a depth chart, and two sets of need weights stored on the team: categorical needs and positional needs. Categorical needs originate from the goal of teams having a balanced team. For example, as a team leans more heavily into an offensive identity, their defensive team needs will be more strongly weighted. Similarly, positional needs represent the team's goal to have a balanced number of players eligible across all positions. Both the categorical and positional needs are computed from the team’s depth chart. Teams' evaluations of players are based on categorical needs, positional needs, and players' overall rating (with some "scouting error" to model real-life mistakes such as these). The relative importance of each of these criteria is configurable as part of the config package. Overall, teams are able to set needs, evaluate players, and update depth charts with new players.
The draft package represents a snake draft over the player pool by 30 NBA teams. The draft consists of 15 rounds, since NBA teams are allowed to roster up to 15 players. Each round, each team evaluates every available player relative to their current team needs, and drafts their top evaluated player that is still available. At the end of the round, the draft order switches for the next round, and evaluation weights update slightly (positional needs slowly decrease over time as teams get additional depth at each position). The draft includes 3 implementations: one sequential, one bulk synchronous parallel (BSP) without work stealing, and one BSP with lock-free work stealing. In the sequential implementation, each team evaluates available players and selects a player before the next team does the same. In the BSP implementation without work stealing, at the beginning of each round, goroutines perform player evaluation in parallel for different subsets of teams, though player selection and end of round updates are still sequential. The BSP implementation with work stealing builds on this implementation by allowing goroutines to perform player evaluation for teams outside their queue once they have finished working on their subset of teams in their own queue. When the draft is complete, it outputs the results to a specified folder within the data directory, both as a list of team picks, and as a list of team depth charts.
The main package parses arguments on the number of additional random players to generate for the player pool, where to save the output in the data directory, which implementation (sequential vs parallel with or without work stealing) of the draft to use, and for parallel implementations, how many goroutines to use. It then simulates one draft according to those inputs.
As an example, here's the depth chart generated for the Atlanta Hawks in one example run (without any randomly generated players):
| Pos | Starter | Backup 1 | Backup 2 | Backup 3 |
|---|---|---|---|---|
| PG | Derrick White (84, Rd 2) | Cason Wallace (79, Rd 5) | Keon Ellis (76, Rd 6) | Nikola Topic (72, Rd 15) |
| SG | Alex Caruso (80, Rd 4) | Sion James (76, Rd 10) | Baylor Scheierman (71, Rd 14) | |
| SF | Ausar Thompson (82, Rd 3) | AJ Green (76, Rd 11) | Julian Strawther (74, Rd 13) | |
| PF | Jake LaRavia (78, Rd 7) | Kevin Love (73, Rd 9) | Dominick Barlow (71, Rd 12) | |
| C | Nikola Jokic (98, Rd 1) | Charles Bassey (72, Rd 8) |
The parallel draft implementations use BSP with two supersteps and two barriers. In the first superstep, each goroutine evaluates players for a subset of teams in parallel, and the goroutines reach the barrier when all teams have evaluated players in a given round. After synchronizing, the second superstep consists of the main goroutine sequentially drafting players and performing end-of-round overhead. Evaluating goroutines wait at the second barrier until this is complete, and then proceed with the next round's evaluation superstep.
This project design lends well to the BSP pattern of parallel programming due to dependency between the parallel superstep of each draft round and the sequential section of each round. I also considered using a map-reduce pattern where different subsets of players would be evaluated separately by different goroutines, but the need to normalize final evaluation scores per team over the full pool of players meant we would need an extra pass through the slice of players to do so, increasing latency due to the synchronization. Pipelines similarly don't make sense for this implementation because of the draft order.
It is important to mention that, with a mismatch between the number of goroutines and number of drafting NBA teams, load balancing in the BSP implementation is not optimal, since some goroutines will work on more teams than others. That said, the work-stealing implementation helps deal with this by allowing goroutines that are further along to take work from slower goroutines with more teams.
As mentioned earlier, in starting this project I was interested in reproducing the video games of my childhood, and seeing if I could achieve noticeable speedup for a realistic draft simulation. The results of my program (discussed below) were mixed. Speedup was only really noticeable when including tens of thousands of additional generated random players in my player pool, as it turned out that my sequential implementation was already pretty fast. I think that building a more time-intensive machine-learning based model might help draw out some of the differences between the sequential and parallel implementations, but I didn't have enough time to really delve into that. That said, the result with a larger player pool was cool to see, and I think would transfer well to fantasy drafts in a larger sport like soccer, where there are many, many players.
Optionally, you can reproduce the player rating scraping by obtaining an API key from 2KAPI, including it in the .env file, and running python scrape_2kratings.py. This will update data/input/nba2k_rosters.json.
To reproduce the draft simulation, run ./benchmark/benchmark-proj3.sh. This shell script runs 5 times for each sequential, parallel, and parallel with work stealing version of draft simulations, for generated random player counts of 0 (that is, only use real NBA players), 5000, 20000, 50000, and 100000 random generated players, with parallel combinations running separately for 2, 4, 6, 8, and 12 goroutines. The output data will be written to data/output while the benchmark results will be saved to benchmark/.
Alternatively, you can run a single draft by specifying the number of random players to generate, the name of the output folder within the data directory to save to, the mode (sequential vs. parallel vs parallelStealing), and for parallel implementations, the number of goroutines to use. For example, the following will run a parallel version of the draft with loaded NBA players and an additional 5000 generated random players, using 10 goroutines and saving to data/newOutput/:
go run simulator/simulator.go 5000 newOutput parallel 10
The following results were the fastest measured times per combination of inputs:
| Mode | Number of generated random players | Goroutines | Time (seconds) |
|---|---|---|---|
| sequential | 0 | 1 | 0.20 |
| sequential | 5000 | 1 | 2.52 |
| sequential | 20000 | 1 | 11.91 |
| sequential | 50000 | 1 | 30.34 |
| sequential | 100000 | 1 | 63.00 |
| parallel | 0 | 2 | 0.13 |
| parallel | 0 | 4 | 0.11 |
| parallel | 0 | 6 | 0.10 |
| parallel | 0 | 8 | 0.09 |
| parallel | 0 | 12 | 0.09 |
| parallel | 5000 | 2 | 1.37 |
| parallel | 5000 | 4 | 0.84 |
| parallel | 5000 | 6 | 0.64 |
| parallel | 5000 | 8 | 0.56 |
| parallel | 5000 | 12 | 0.49 |
| parallel | 20000 | 2 | 6.42 |
| parallel | 20000 | 4 | 3.65 |
| parallel | 20000 | 6 | 2.59 |
| parallel | 20000 | 8 | 2.22 |
| parallel | 20000 | 12 | 1.89 |
| parallel | 50000 | 2 | 16.57 |
| parallel | 50000 | 4 | 9.50 |
| parallel | 50000 | 6 | 6.63 |
| parallel | 50000 | 8 | 5.79 |
| parallel | 50000 | 12 | 4.86 |
| parallel | 100000 | 2 | 33.80 |
| parallel | 100000 | 4 | 19.58 |
| parallel | 100000 | 6 | 13.80 |
| parallel | 100000 | 8 | 12.06 |
| parallel | 100000 | 12 | 10.19 |
| parallelStealing | 0 | 2 | 0.13 |
| parallelStealing | 0 | 4 | 0.11 |
| parallelStealing | 0 | 6 | 0.10 |
| parallelStealing | 0 | 8 | 0.09 |
| parallelStealing | 0 | 12 | 0.10 |
| parallelStealing | 5000 | 2 | 1.37 |
| parallelStealing | 5000 | 4 | 0.81 |
| parallelStealing | 5000 | 6 | 0.63 |
| parallelStealing | 5000 | 8 | 0.54 |
| parallelStealing | 5000 | 12 | 0.48 |
| parallelStealing | 20000 | 2 | 6.38 |
| parallelStealing | 20000 | 4 | 3.60 |
| parallelStealing | 20000 | 6 | 2.58 |
| parallelStealing | 20000 | 8 | 2.20 |
| parallelStealing | 20000 | 12 | 1.87 |
| parallelStealing | 50000 | 2 | 16.50 |
| parallelStealing | 50000 | 4 | 9.34 |
| parallelStealing | 50000 | 6 | 6.69 |
| parallelStealing | 50000 | 8 | 5.74 |
| parallelStealing | 50000 | 12 | 4.80 |
| parallelStealing | 100000 | 2 | 33.92 |
| parallelStealing | 100000 | 4 | 19.45 |
| parallelStealing | 100000 | 6 | 13.87 |
| parallelStealing | 100000 | 8 | 12.03 |
| parallelStealing | 100000 | 12 | 10.19 |
Parallel implementation speedup
| Goroutines | |||||
|---|---|---|---|---|---|
| Generated Players | 2 | 4 | 6 | 8 | 12 |
| 0 | 1.5× | 1.8× | 2.0× | 2.2× | 2.2× |
| 5,000 | 1.8× | 3.0× | 3.9× | 4.5× | 5.1× |
| 20,000 | 1.9× | 3.3× | 4.6× | 5.4× | 6.3× |
| 50,000 | 1.8× | 3.2× | 4.6× | 5.2× | 6.2× |
| 100,000 | 1.9× | 3.2× | 4.6× | 5.2× | 6.2× |
Parallel implementation with work stealing speedup
| Goroutines | |||||
|---|---|---|---|---|---|
| Generated Players | 2 | 4 | 6 | 8 | 12 |
| 0 | 1.5× | 1.8× | 2.0× | 2.2× | 2.0× |
| 5,000 | 1.8× | 3.1× | 4.0× | 4.7× | 5.3× |
| 20,000 | 1.9× | 3.3× | 4.6× | 5.4× | 6.4× |
| 50,000 | 1.8× | 3.2× | 4.5× | 5.3× | 6.3× |
| 100,000 | 1.9× | 3.2× | 4.5× | 5.2× | 6.2× |
For (small) player pools without any generated random players, the parallel implementations plateau at around 2× speedup (0.20 seconds in the sequential implementation vs. around 0.09–0.13 seconds in parallel implementations). This is due to the tradeoff between parallelizing an already relatively fast task and the overhead corresponding to spawning goroutines. Parallelizing these runs is largely academic exercise since they all finish in under half a second.
For larger player pools (5000 or more generated players in addition to loaded players), both parallel implementations achieve steady increases in speedup with additional goroutines. Speedups are only limited by the sequential bottlenecks (discussed below) that remain in the program and the overhead associated with spawning goroutines.
Barring any limitations in hardware, the optimal number of goroutines would be 30, or 1 per drafting team. Any additional goroutine past 30 will not have any work to perform. If we were to test with 50 goroutines we would see a decrease in speedup relative to the 30 goroutine implementation due to the added overhead of additional goroutines without any work performed.
Curiously enough, the two parallel implementations are very similar in runtime. Based on the charts above, work stealing may be occurring, but given the relatively coarse tasks assigned per goroutine, there is not much room for optimization from work stealing. This makes sense to me, as task stealing would have been more helpful had I gone forward with a map-reduce pattern where different goroutines evaluated individual players.
One last observation I had was that the runs with 20,000 generated players slightly outperformed the 100,000 generated player runs in speedup. This came as a surprise to me, as I expected each additional player to increase speedup in the parallel implementations. My guess here is that, at this many players, we are running into issues with data fitting inside processor caches, requiring some additional overhead that cancels out the speedup over the sequential implementation.
The main hotspot is the section of each round where each team sets team needs and evaluates players. This is parallelized by splitting teams across goroutines. Meanwhile, the main sequential bottlenecks are the player selections and end-of-round overhead during each round, which must happen sequentially in order to follow standard draft logic. Similarly, the loading of players in the beginning of the draft and the outputting of results act as bottlenecks. If I had more time, it would be interesting to explore generating players in parallel or even writing the results using two goroutines for the two files, but both seemed like overkill in this case given the required synchronization overhead for the former and the small number of goroutines we could use for the latter.