New tournament form
Posted: 19 Jun 2007, 23:10To segregate a large list of players with a limited number of matches, the Swiss system is developed. This was developed for Human tournaments, though, where you want all players to be playing simultaneously, while each player should play only one match at the time. Engine-engine tournaments on a single computer don't have to satisfy that boundary condition, as the computer can only handle one match at the time, and the players waiting for this match to finish don't get impatient. This makes other tournament forms possible.
The following idea occurred to me for such a system. Suppose you have an old ranking from a previous edition. Many of the engines on the list will have been improved, sometimes quite a lot. In addition there will be new engines, some of them strong.
The idea now is to make a section of consecutive engines on your list 'active'. In the active section, the engines play a round robin. After this finishes, you move the active region up one place, by leaving the player that finished lowest behind, and adding the lowest-ranked engine from the list above the active region (which has not played yet) to the active region. This engine than plays against all other engines in the active region, while the previous results between these engines against each other stay valid.
So if you just completed a 10-player RR, the lowest one goes out, and the added engine from above just has to play the 9 remaining opponents to complete a new 10-player RR moved one place upward. This way the active region 'bubbles' all the way to the top of the list.
Now the danger of this method, especially if you append all new engines at the bottom of the list before you start, is that the bubble collects all engines that are way too strong for their current environment. If there are more of those than the size of the active region, each new engine you add from above the bubble is immediately massacred by the engines in the bubble, and goes out on the next step. This then basically freezes the order of the engines in the list, except for those moving upward in the bubble, until the bubble arrives in a region where some of the engines in it belong. These will then start to drop out.
To prevent this, the size of the active region should dynamically adapt to the number of engines that need to be transported upward. But this could make the bubble unweildly large, if there are many. Each of the engines that are climbing plays each of the engines it passes on the list, and a new, strong engine started at the bottom this way plays very many, very uninteresting games.
To fix this, one could use the following modification: we put an upper limit to the size of the round-robins, (say 10), and a lower limit to the number of games an engine has to play before it can drop out (say 15). This way, if the engine added from above immediately ends last, it has only played 9 games, and cannot drop out yet. In that case, the engine added from above only plays the lowest-ranked 9 engines to complete a new 10-player RR, and the top engine gets 'parked' just above the active region. More engines can get parked, as long as the lowest engine does not have enough games to drop out.
Engines that are parked move up with the bubble for free, i.e. without playing any games. After all, they are supposed to be better than the best engines in the active region, as once they ended above some of them. At the moment an engine gets parked, it had played against all 9 engines that ended below it in the RR. At some point some of those engines start to drop out. As soon as so many engines have dropped out that there is an engine in the parking area that has played against fewer than (say) 5 engines in the active region, an engine that drops out from the latter is not replaced by an engine from the old ranking above the bubble, but by this engine from the parking area. (If there are more, then the one that was parked longest ago.)
Unparked engines, like added engines from the old ranking above the active region, play any engines in the active region they had not yet played, to complete the RR, and are further treated as though they had never been parked. I.e., they might get parked again if they finish a RR on top, or drop out if they finish last.
This way, a large group of strong engines can move all the way from the bottom (e.g. if new engines start there) up the ranking without all of them playing every engine they have to pass: the entire group of parked engines is pushed upward by the 5 that they proved to be superior to, without having to play themselves. They only have to start proving themselves again when these weaker engines meet their match in the ranking, and drop out of the bubble as a consequence.
So in summary:
1) Complete a round robin of 10 players at the bottom of the old list.
2) If the player finishing last has less than 15 matches, the engine finishing on top gets parked.
3) if the player finishing last has 15 games or more, it drops out
(i.e. it is added to the top of the new ranking)
4) A player that drops out or gets parked is replaced by the longest parked player that has played fewer than 5 of the players remaining in the RR.
5) If there is no such parked player, it is replaced by the lowest player of the old ranking that has not played yet.
6) The replacement plays the 9 remaining players of the RR to complete it (as the old results between those 9 stay valid).
7) Repeat steps 2-6.
8) If the old ranking is entirely consumed, drop-outs are replaced by the parked engine that has played the fewest opponents remaining in the RR, even if this is more than 5 (again, longest parked first in case of a tie).
9) If both the old ranking and the parking area are exhausted, the entire RR ranking is transferred to the top of the new ranking. I.e., the player on top of the last RR is the new champion.
The following idea occurred to me for such a system. Suppose you have an old ranking from a previous edition. Many of the engines on the list will have been improved, sometimes quite a lot. In addition there will be new engines, some of them strong.
The idea now is to make a section of consecutive engines on your list 'active'. In the active section, the engines play a round robin. After this finishes, you move the active region up one place, by leaving the player that finished lowest behind, and adding the lowest-ranked engine from the list above the active region (which has not played yet) to the active region. This engine than plays against all other engines in the active region, while the previous results between these engines against each other stay valid.
So if you just completed a 10-player RR, the lowest one goes out, and the added engine from above just has to play the 9 remaining opponents to complete a new 10-player RR moved one place upward. This way the active region 'bubbles' all the way to the top of the list.
Now the danger of this method, especially if you append all new engines at the bottom of the list before you start, is that the bubble collects all engines that are way too strong for their current environment. If there are more of those than the size of the active region, each new engine you add from above the bubble is immediately massacred by the engines in the bubble, and goes out on the next step. This then basically freezes the order of the engines in the list, except for those moving upward in the bubble, until the bubble arrives in a region where some of the engines in it belong. These will then start to drop out.
To prevent this, the size of the active region should dynamically adapt to the number of engines that need to be transported upward. But this could make the bubble unweildly large, if there are many. Each of the engines that are climbing plays each of the engines it passes on the list, and a new, strong engine started at the bottom this way plays very many, very uninteresting games.
To fix this, one could use the following modification: we put an upper limit to the size of the round-robins, (say 10), and a lower limit to the number of games an engine has to play before it can drop out (say 15). This way, if the engine added from above immediately ends last, it has only played 9 games, and cannot drop out yet. In that case, the engine added from above only plays the lowest-ranked 9 engines to complete a new 10-player RR, and the top engine gets 'parked' just above the active region. More engines can get parked, as long as the lowest engine does not have enough games to drop out.
Engines that are parked move up with the bubble for free, i.e. without playing any games. After all, they are supposed to be better than the best engines in the active region, as once they ended above some of them. At the moment an engine gets parked, it had played against all 9 engines that ended below it in the RR. At some point some of those engines start to drop out. As soon as so many engines have dropped out that there is an engine in the parking area that has played against fewer than (say) 5 engines in the active region, an engine that drops out from the latter is not replaced by an engine from the old ranking above the bubble, but by this engine from the parking area. (If there are more, then the one that was parked longest ago.)
Unparked engines, like added engines from the old ranking above the active region, play any engines in the active region they had not yet played, to complete the RR, and are further treated as though they had never been parked. I.e., they might get parked again if they finish a RR on top, or drop out if they finish last.
This way, a large group of strong engines can move all the way from the bottom (e.g. if new engines start there) up the ranking without all of them playing every engine they have to pass: the entire group of parked engines is pushed upward by the 5 that they proved to be superior to, without having to play themselves. They only have to start proving themselves again when these weaker engines meet their match in the ranking, and drop out of the bubble as a consequence.
So in summary:
1) Complete a round robin of 10 players at the bottom of the old list.
2) If the player finishing last has less than 15 matches, the engine finishing on top gets parked.
3) if the player finishing last has 15 games or more, it drops out
(i.e. it is added to the top of the new ranking)
4) A player that drops out or gets parked is replaced by the longest parked player that has played fewer than 5 of the players remaining in the RR.
5) If there is no such parked player, it is replaced by the lowest player of the old ranking that has not played yet.
6) The replacement plays the 9 remaining players of the RR to complete it (as the old results between those 9 stay valid).
7) Repeat steps 2-6.
8) If the old ranking is entirely consumed, drop-outs are replaced by the parked engine that has played the fewest opponents remaining in the RR, even if this is more than 5 (again, longest parked first in case of a tie).
9) If both the old ranking and the parking area are exhausted, the entire RR ranking is transferred to the top of the new ranking. I.e., the player on top of the last RR is the new champion.