Skip to content

Latest commit

 

History

History
108 lines (75 loc) · 3.07 KB

chessmm.rst

File metadata and controls

108 lines (75 loc) · 3.07 KB
Raw

Model: Chess Matchmaking Optimization (CHESS)

Description:

Chess players are rated using the Elo rating system, which assigns a (non-unique) number to each player based on their level of skill. The model simulates an online chess-matchmaking platform, which tries to match players of similar skill level.

The platform uses a search width x, which is the maximum allowable difference in Elo rating between two matched players. N players are drawn from a distribution of Elo ratings and arrive (independent of their rating) according to a stationary Poisson process with rate λ. When a player arrives, and there is an existing, unmatched player with Elo rating within x of the first player's Elo rating, they are matched. If not, then the player waits for an opponent with an appropriate Elo rating to arrive.

Sources of Randomness:

1. To create the Elo distribution, first generate a normal distribution with mean 1200 and standard deviation $\frac{1200}{\sqrt(2)*\text{erfcinv}(\frac{1}{50})}$, where erfcinv is the inverse complementary error function. This results in a distribution where the 1st percentile is at 0, and the 99th percentile is at 2400. Next, truncate the distribution at 0 and 2400. 2. A stationary Poisson process with rate λ for arrivals.

Model Factors:

  • elo_mean: Mean of normal distribution for Elo rating.

    • Default: 1200.0

  • elo_sd: Standard deviation of normal distribution for Elo rating.

    • Default: 1200 / (np.sqrt(2) * special.erfcinv(1 / 50))

  • poisson_rate: Rate of Poisson process for player arrivals.

    • Default: 1.0

  • num_players: Number of players.

    • Default: 1000

  • allowable_diff: Maximum allowable difference between Elo ratings.

    • Default: 150.0

Responses:

  • avg_diff: The average Elo difference between all pairs.
  • avg_wait_time: The average waiting time.

References:

Original author of this problem is Bryan Chong (March 15, 2015).

Optimization Problem: Minimize Average Elo Difference (CHESS-1)

Decision Variables:

  • allowable_diff

Objectives:

Minimize the average Elo difference between all pairs of matched players.

Constraints:

Maximum allowable difference is between 0 and 2400.

The average waiting time is  ≤ δ.

Problem Factors:

  • budget: Max # of replications for a solver to take.
    • Default: 1000
  • upper_time: Upper bound on wait time.
    • Default: 5.0

Fixed Model Factors:

  • N/A

Starting Solution:

  • initial_solution: (150,)

Random Solutions:

First draw x from a normal distribution with mean 150 and standard deviation 50, then set x = min (max (x, 0), 2400).

Optimal Solution:

Unknown

Optimal Objective Function Value:

Unknown