Difference between revisions of "TCEC Swiss Tournament System"

From TCEC wiki
Jump to: navigation, search
m (STEP 5: Add notes on color balance)
(Playing order within a round)
 
(9 intermediate revisions by 2 users not shown)
Line 1: Line 1:
TCEC Swiss Tournament System is a variant of the [https://en.wikipedia.org/wiki/Swiss-system_tournament Swiss tournament format]. It is completely deterministic with a reasonably simple rule set, resembling the [https://web.archive.org/web/20070706122207/http://www.sjakk.no/nsf/monradsystem_index.html Monrad system]. It can be played with any number of participants and any number of rounds. Rounds are either single or double rounds. It is designed to be played with 40-50 engines over 10-25 rounds. It is recommended to have an even number of engines.
+
TCEC Swiss Tournament System is a variant of the [https://en.wikipedia.org/wiki/Swiss-system_tournament Swiss tournament format]. It is completely deterministic with a reasonably simple rule set, resembling the [https://web.archive.org/web/20070706122207/http://www.sjakk.no/nsf/monradsystem_index.html Monrad system]. It can be played with any number of participants and any number of rounds. Rounds are either single or double rounds. It is designed to be played with 40-50 engines over 10-25 rounds.
  
 
= General structure =
 
= General structure =
Line 16: Line 16:
 
* Tiebreakers (e.g., number of black games DESC, SB, r-mobility score)
 
* Tiebreakers (e.g., number of black games DESC, SB, r-mobility score)
  
= Initial seeding =
+
Recommendations:
 +
* Even number of players
 +
* When single rounds format is used, it is recommended to have an odd number of rounds for color balancing. There is no such recommendation for double rounds format.
 +
* Number of rounds should generally be at most the number of players divided by 2 (approximately). If more rounds are desired, then it may be preferable to use a round-robin tournament format, instead.
 +
* For player seeding, use either:
 +
** Group seeding. Use an even number of groups. Group size 7 would pair 1st-8th, 2nd-9th etc. If this is desirable, use number_of_groups = round_to_even(number_of_players / 7)
 +
** Random seeding
 +
 
 +
= Seeding =
  
 
Every player is assigned a unique seeding number. This determines the pairing order in the first round and is used as a secondary ordering criterion in the following rounds.
 
Every player is assigned a unique seeding number. This determines the pairing order in the first round and is used as a secondary ordering criterion in the following rounds.
 +
 +
The following seeding procedures are defined:
 +
* '''Random seeding'''.
 +
* '''Group seeding'''. The procedure is as follows:
 +
** Order the players by strength, for example by Elo rating or last known results (highest first).
 +
** Divide the players into N groups: Group A = strongest players, Group B = next strongest, etc. If the division is not even, then the stronger groups should have one more player than the weaker groups.
 +
*** '''Note:''' The number of groups should be even. Group size 6/7 is likely good for TCEC.
 +
*** For example: 11 players into 4 groups: Groups A-C have 4 players and D has 3 players
 +
** For increasing seeding numbers, first pick a player from group A, then from group B, then from group C, etc, and reiterate from group A until every player has been seeded. Pick always the strongest unseeded player from a group
 +
*** For example: 11 players in 4 groups. S1=A1, S2=B1, S3=C1, S4=D1, S5=A2, ... (S<n> = seed n, A1 is strongest player in group A)
  
 
Notes:
 
Notes:
* Equal distance seeding may be used to promote the expected top encounters to the later rounds of the tournament
+
* Equal distance seeding may be used to promote the expected top encounters as late as possible
 +
* Random seeding also works
 
* The 1st round pairing is: seed2-seed1, seed4-seed3, seed6-seed5, ...
 
* The 1st round pairing is: seed2-seed1, seed4-seed3, seed6-seed5, ...
  
Line 59: Line 78:
 
Notes:
 
Notes:
 
* White game difference for player ''p'' = WGD(''p'') = (games played by player ''p'' with the white pieces) - (games played by player ''p'' with the back pieces)
 
* White game difference for player ''p'' = WGD(''p'') = (games played by player ''p'' with the white pieces) - (games played by player ''p'' with the back pieces)
* The [https://en.wikipedia.org/wiki/Blossom_algorithm Blossom algorithm] can be used to determine efficiently whether there exists a viable pairing. Create a graph where the players are represented by vertices and the allowed pairings are represented by non-directional edges. That is, edge ''p0-p1'' exists iff:
+
** WGD(p) is unaffected by the possible round removals in the encounter history
** Players ''p0'' and ''p1'' have not met (as per the encounter history); and
+
* The [https://en.wikipedia.org/wiki/Blossom_algorithm Blossom algorithm] can be used to determine efficiently whether there exists a viable pairing. Create a graph where the players are represented by vertices and the allowed pairings are represented by non-directional edges. That is, edge ''p1-p2'' exists iff:
** The color balancing conditions between ''p0'' and ''p1'' are met. That is: |WGD(p1) + WGD(p2)| <= 2
+
** Players ''p1'' and ''p2'' have not met (as per the encounter history); and
 +
** The color balancing conditions between ''p1'' and ''p2'' are met. That is: |WGD(p1) + WGD(p2)| <= 2
 
* When there are an even number of players (i.e., no BYE rounds), then the color balancing conditions ensure that every player has white game difference +1 or -1 after an odd number of rounds.
 
* When there are an even number of players (i.e., no BYE rounds), then the color balancing conditions ensure that every player has white game difference +1 or -1 after an odd number of rounds.
  
Line 69: Line 89:
 
* Pick the first unpaired player by the pairing order. Mark the player as paired. This player is called the first-of-pair.
 
* Pick the first unpaired player by the pairing order. Mark the player as paired. This player is called the first-of-pair.
 
* Pick the highest-ranked unpaired player as the second-of-pair that maintains the following criteria:
 
* Pick the highest-ranked unpaired player as the second-of-pair that maintains the following criteria:
** The pair has not met before (encounter history removal applies)
+
** The pairing condition is met (see STEP 3); and
 
** The viability of the round pairing is maintained (see STEP 3)
 
** The viability of the round pairing is maintained (see STEP 3)
  
Line 88: Line 108:
  
 
Notes:
 
Notes:
* For a pair (''p1'', ''p2''):
+
* '''Single rounds.''' For any pair (''p1'', ''p2''):
 
** If WGD(''p1'')=0 and WGD(''p2'')=0, then after the round: |WGD(''p1'')| + |WGD(''p2'')| = 2
 
** If WGD(''p1'')=0 and WGD(''p2'')=0, then after the round: |WGD(''p1'')| + |WGD(''p2'')| = 2
 
** In any other case, after the round: |WGD(''p1'')| + |WGD(''p2'')| <= 2
 
** In any other case, after the round: |WGD(''p1'')| + |WGD(''p2'')| <= 2
 
** In other words, every player always has at most 2 more games with one color than with the other color.
 
** In other words, every player always has at most 2 more games with one color than with the other color.
* Further, after an even number of games by player ''p'', WGD(p) is even. Similarly, after an odd number of games, WGD(p) is odd. Thus, after an odd number of rounds without BYE: |WGD(''p'')|=1 for every player.
+
** Further, after an even number of games by player ''p'', WGD(p) is even. Similarly, after an odd number of games, WGD(p) is odd. Thus, after an odd number of rounds without BYE: |WGD(''p'')|=1 for every player.
 +
* '''Double rounds.''' WGD(p)=0 for all players before and after the round.
  
 
= Playing order within a round =
 
= Playing order within a round =
Line 99: Line 120:
 
* '''Double rounds.''' The single round schedule is executed twice. That is, the second encounter with reversed colors is after every pair has played once.
 
* '''Double rounds.''' The single round schedule is executed twice. That is, the second encounter with reversed colors is after every pair has played once.
  
[[Category:TCEC Swiss]]
+
[[Category:TCEC Swiss|Swiss]]
 +
 
 +
= Python script for group seeding =
 +
 
 +
<pre>
 +
#!/usr/bin/python3
 +
 
 +
import math
 +
 
 +
num_groups = 6
 +
 
 +
engines = [
 +
    'Stockfish',
 +
    'LCZero',
 +
    'KomodoDragon',
 +
    ...
 +
]
 +
 
 +
num_engines = len(engines)
 +
print("number of engines:", num_engines)
 +
print("number of groups: ", num_groups)
 +
print()
 +
 
 +
groups = { }
 +
 
 +
for a in range(0, num_groups):
 +
    groups[a] = [ ]
 +
 
 +
# assign engines to groups
 +
engine = 0
 +
for group in range(0, num_groups):
 +
    group_size = math.ceil((num_engines - engine) / (num_groups - group))
 +
    for i in range(0, group_size):
 +
        groups[group].append(engines[engine])
 +
        engine = engine + 1
 +
 
 +
# create seeding order
 +
rank = 0
 +
seed = 1
 +
 
 +
while seed <= num_engines:
 +
    for group in range(0, num_groups):
 +
        print(f'# (' + chr(group + 65) + str(rank + 1) + ")  " + groups[group][rank])
 +
        seed = seed + 1
 +
        if seed > num_engines:
 +
            break
 +
    rank = rank + 1
 +
</pre>

Latest revision as of 12:04, 15 June 2023

TCEC Swiss Tournament System is a variant of the Swiss tournament format. It is completely deterministic with a reasonably simple rule set, resembling the Monrad system. It can be played with any number of participants and any number of rounds. Rounds are either single or double rounds. It is designed to be played with 40-50 engines over 10-25 rounds.

General structure

There are P players and N rounds. The format is either single round or double round.

At the beginning of every round, the pairs are determined. See pairing below.

In the single round format, every pair plays once per round. Thus, there are ⌊P/2⌋ games (rounded down). In the double round format, every pair plays twice per round and the number of games is 2*⌊P/2⌋ per round. The second game is with reversed colors.

In case of an odd number of players, one player per round receives a BYE. The BYE games are scored as wins.

After all the rounds have been played, the tournament is complete. The final ranking of players is determined as per the following criteria: (priority order)

  • Score (DESCending)
  • Number of received BYEs (ASCending, less is better)
  • Tiebreakers (e.g., number of black games DESC, SB, r-mobility score)

Recommendations:

  • Even number of players
  • When single rounds format is used, it is recommended to have an odd number of rounds for color balancing. There is no such recommendation for double rounds format.
  • Number of rounds should generally be at most the number of players divided by 2 (approximately). If more rounds are desired, then it may be preferable to use a round-robin tournament format, instead.
  • For player seeding, use either:
    • Group seeding. Use an even number of groups. Group size 7 would pair 1st-8th, 2nd-9th etc. If this is desirable, use number_of_groups = round_to_even(number_of_players / 7)
    • Random seeding

Seeding

Every player is assigned a unique seeding number. This determines the pairing order in the first round and is used as a secondary ordering criterion in the following rounds.

The following seeding procedures are defined:

  • Random seeding.
  • Group seeding. The procedure is as follows:
    • Order the players by strength, for example by Elo rating or last known results (highest first).
    • Divide the players into N groups: Group A = strongest players, Group B = next strongest, etc. If the division is not even, then the stronger groups should have one more player than the weaker groups.
      • Note: The number of groups should be even. Group size 6/7 is likely good for TCEC.
      • For example: 11 players into 4 groups: Groups A-C have 4 players and D has 3 players
    • For increasing seeding numbers, first pick a player from group A, then from group B, then from group C, etc, and reiterate from group A until every player has been seeded. Pick always the strongest unseeded player from a group
      • For example: 11 players in 4 groups. S1=A1, S2=B1, S3=C1, S4=D1, S5=A2, ... (S<n> = seed n, A1 is strongest player in group A)

Notes:

  • Equal distance seeding may be used to promote the expected top encounters as late as possible
  • Random seeding also works
  • The 1st round pairing is: seed2-seed1, seed4-seed3, seed6-seed5, ...

Round pairing

STEP 1

Pairing starts by ranking the players by:

  • Score (DESC; i.e., the top player has the highest score)
  • Seed (ASC)

This ranking is called the pairing order.

Notes:

  • Every round (incl. the first round) uses the same pairing ordering scheme.
  • The ranking for pairing is different to final ranking.

STEP 2

In case of an odd number of players, the player to receive the BYE is determined as follows. Order the players by:

  • Number of received BYEs (DESC)
  • Pairing order (ASC)

The bottom player receives the BYE.

That is, the worst-performing player that has not yet received a BYE receives one. If every player has already received a BYE, then the worst-performing player that has received a single BYE receives one. And so on.

STEP 3

Determine whether there exists a viable pairing for the round. If no viable pairings exist, remove the earliest round in the encounter history. Repeat this as necessary until a viable pairing exists. The removals are permanent, i.e., they carry over to the following rounds.

Players p1 and p2 are allowed to be paired if all of the below conditions are met:

  • The players have not yet met as per the encounter history
  • The color balancing conditions:
    • If either player has white game difference +2, then the other player must have white game difference of at most 0.
    • If either player has white game difference -2, then the other player must have white game difference of at least 0.

Notes:

  • White game difference for player p = WGD(p) = (games played by player p with the white pieces) - (games played by player p with the back pieces)
    • WGD(p) is unaffected by the possible round removals in the encounter history
  • The Blossom algorithm can be used to determine efficiently whether there exists a viable pairing. Create a graph where the players are represented by vertices and the allowed pairings are represented by non-directional edges. That is, edge p1-p2 exists iff:
    • Players p1 and p2 have not met (as per the encounter history); and
    • The color balancing conditions between p1 and p2 are met. That is: |WGD(p1) + WGD(p2)| <= 2
  • When there are an even number of players (i.e., no BYE rounds), then the color balancing conditions ensure that every player has white game difference +1 or -1 after an odd number of rounds.

STEP 4

Perform pairing. The players are paired one by one in the pairing order as follows:

  • Pick the first unpaired player by the pairing order. Mark the player as paired. This player is called the first-of-pair.
  • Pick the highest-ranked unpaired player as the second-of-pair that maintains the following criteria:
    • The pairing condition is met (see STEP 3); and
    • The viability of the round pairing is maintained (see STEP 3)

Do this until every player has been paired. Add pairs in the encounter history for this round.

Notes:

  • The possible BYE player is not considered for pairing

STEP 5

Determine playing colors for each pair:

  • Single rounds. Determine which player of the pair has the greater white game difference (i.e., games played as white - games played as black). The player with the greater white game difference gets the black pieces. In case the difference equals, then the player with the higher score gets the black pieces. If both players have the same score, then the following formula is used:
    • First-of-pair receives the white pieces on rounds 2, 3, 6, 7, 10, 11, ... (first-of-pair has lower seed number)
    • Second-of-pair receives the white pieces on rounds 1, 4, 5, 8, 9, 12, ...
    • In other words, the following repeating pattern is used to determine the white-game advantage between the first and the second of pair per rounds: 2112 2112 2112...
    • The rationale for the 4-round pattern is that the white game difference is roughly even and uneven every second round. Thus, the pattern in flipped every second round with a total 4-round cycle.
  • Double rounds. The first-of-pair always plays with the black pieces on the first encounter, and with the white pieces on the second encounter

Notes:

  • Single rounds. For any pair (p1, p2):
    • If WGD(p1)=0 and WGD(p2)=0, then after the round: |WGD(p1)| + |WGD(p2)| = 2
    • In any other case, after the round: |WGD(p1)| + |WGD(p2)| <= 2
    • In other words, every player always has at most 2 more games with one color than with the other color.
    • Further, after an even number of games by player p, WGD(p) is even. Similarly, after an odd number of games, WGD(p) is odd. Thus, after an odd number of rounds without BYE: |WGD(p)|=1 for every player.
  • Double rounds. WGD(p)=0 for all players before and after the round.

Playing order within a round

  • Single rounds. Pairs are ordered by the pairing order of the first-of-pair (DESC). That is, the worst-performing pair plays first.
  • Double rounds. The single round schedule is executed twice. That is, the second encounter with reversed colors is after every pair has played once.

Python script for group seeding

#!/usr/bin/python3

import math

num_groups = 6

engines = [
    'Stockfish',
    'LCZero',
    'KomodoDragon',
    ...
]

num_engines = len(engines)
print("number of engines:", num_engines)
print("number of groups: ", num_groups)
print()

groups = { }

for a in range(0, num_groups):
    groups[a] = [ ]

# assign engines to groups
engine = 0
for group in range(0, num_groups):
    group_size = math.ceil((num_engines - engine) / (num_groups - group))
    for i in range(0, group_size):
        groups[group].append(engines[engine])
        engine = engine + 1

# create seeding order
rank = 0
seed = 1

while seed <= num_engines:
    for group in range(0, num_groups):
        print(f'# (' + chr(group + 65) + str(rank + 1) + ")  " + groups[group][rank])
        seed = seed + 1
        if seed > num_engines:
            break
    rank = rank + 1