董東風(fēng)

（湖南郵電職業(yè)技術(shù)學(xué)院，湖南長(zhǎng)沙410015）

瑞士賽制配對(duì)算法研究

董東風(fēng)

（湖南郵電職業(yè)技術(shù)學(xué)院，湖南長(zhǎng)沙410015）

瑞士賽制（包括配對(duì)規(guī)則）從最初開始發(fā)展至今在不斷完善。筆者在查詢文獻(xiàn)資料、總結(jié)多年實(shí)踐經(jīng)驗(yàn)的基礎(chǔ)上，對(duì)瑞士配對(duì)規(guī)則進(jìn)行了專門研究。研究結(jié)果表明，瑞士配對(duì)方法存在大量重復(fù)計(jì)算，計(jì)算不精確，影響了計(jì)算機(jī)配對(duì)效率；且手工難以完全按照瑞士規(guī)則中的移位和換位規(guī)則執(zhí)行配對(duì)操作。對(duì)此，筆者提出了新的“嵌套式循環(huán)輪次”配對(duì)方法，并給出了其配對(duì)輪次計(jì)算公式，這個(gè)公式可以達(dá)到精確計(jì)算目的，提高計(jì)算機(jī)的配對(duì)效率和智能化。由于配對(duì)輪次的生成方法遵循了循環(huán)賽“固定輪轉(zhuǎn)法”原理，使瑞士配對(duì)方法更容易理解，也方便手工操作記憶，同時(shí)，更能滿足瑞士規(guī)則中的浮動(dòng)規(guī)則要求?？梢哉f(shuō)，從配對(duì)的效率和可操作性上，新方法可以改進(jìn)傳統(tǒng)瑞士配對(duì)方法。

瑞士賽制；移位；換位；配對(duì)程序；配對(duì)輪次；配對(duì)質(zhì)量；固定輪轉(zhuǎn)法

瑞士賽制（包括配對(duì)規(guī)則）最早出現(xiàn)是在1895年的瑞士蘇黎世，從最初開始發(fā)展至今在不斷完善。瑞士賽制可以理解為一種不完全循環(huán)的循環(huán)賽制，所以也稱為積分循環(huán)賽制，或積分編排賽制（因?yàn)槊枯啽荣惗夹枰鋵?duì)編排）。瑞士賽制在棋類比賽中被廣泛運(yùn)用，在學(xué)校球類競(jìng)賽中也有所見，特別適合參賽人數(shù)（或球隊(duì)，下同）眾多的賽事。

在循環(huán)賽中，賽前就可以確定每輪的比賽對(duì)手，每個(gè)對(duì)手相互間都需要比賽，以此達(dá)到公平競(jìng)賽的目的；但是，由于對(duì)手的實(shí)力存在差異，而實(shí)力強(qiáng)者與實(shí)力弱者也需要比賽，這樣就給比賽帶來(lái)了消極因素；且賽程過(guò)長(zhǎng)，特別是在參賽人數(shù)眾多時(shí)不適合采用。

瑞士賽制可以彌補(bǔ)循環(huán)賽的上述缺點(diǎn)，不需要完全循環(huán)，只需要在一定的循環(huán)輪次后即可依據(jù)規(guī)定的排名程序進(jìn)行排名完成賽事。在瑞士賽制中，賽前不能確定每輪比賽的對(duì)手，而是要根據(jù)每輪比賽的結(jié)果來(lái)評(píng)估參賽者的實(shí)力（排名），然后，實(shí)力強(qiáng)的強(qiáng)對(duì)強(qiáng)、實(shí)力弱的弱對(duì)弱配對(duì)比賽，比賽雙方實(shí)力相當(dāng)，強(qiáng)弱者之間不需要比賽，因此，減少了比賽的消極因素；由于不需要每個(gè)對(duì)手相互間比賽，所以，比賽輪次少于循環(huán)賽，特別是在參賽人數(shù)眾多的情況下，將大大減少整個(gè)比賽賽程；瑞士賽制的公平性主要體現(xiàn)在配對(duì)上，由于每輪比賽都需要配對(duì)，所以，配對(duì)方法就顯得更加重要，好的配對(duì)方法主要體現(xiàn)在公平、效率、可操作三個(gè)方面。

1　瑞士賽制傳統(tǒng)配對(duì)方法

在棋類比賽中，瑞士賽制傳統(tǒng)配對(duì)方法都是依據(jù)世界國(guó)際象棋聯(lián)盟［1］官方承認(rèn)的瑞士規(guī)則［2］［3］中的配對(duì)規(guī)則，包括Dutch System［4］，Lim System，Dubov System，Burstein System［5］等。除第一輪比賽外，比賽對(duì)手的確定都需要根據(jù)前面比賽的結(jié)果。配對(duì)程序（Pairing Procedures）基本流程是：在每輪比賽前，把全部參賽者按相同積分（Scores）進(jìn)行分組，從最高積分組開始配對(duì)到最低積分組配對(duì)結(jié)束。如果一個(gè)參賽者在一個(gè)積分組內(nèi)不能被配對(duì)，將被下浮到下一個(gè)臨近積分組配對(duì)，由此存在兩種積分組：一種是同類積分組，該組參賽者的積分相同；另一種是不同類積分組，該組參賽者的積分存在不相同。

在一個(gè)積分組（Score brackets）內(nèi)配對(duì)，首先是按照規(guī)定的排序（Order）規(guī)則對(duì)該組參賽者進(jìn)行排序；然后，按序號(hào)分成兩個(gè)子組（Subgroups）S1和S2，S1包含序號(hào)1到N/2（取整），S2包含剩余序號(hào)N/2+ 1到N（N等于積分組人數(shù)），兩個(gè)子組配對(duì)，有N/2個(gè)配對(duì)，這被看成是一輪配對(duì)（或一組配對(duì)），通過(guò)S2移位（Transposition）規(guī)則，和S1與S2換位（Exchange）規(guī)則可以生成所有可能的配對(duì)輪次。

按照移位和換位規(guī)則，可以計(jì)算出一個(gè)積分組內(nèi)所有可能的配對(duì)輪次。以11人為例，S1（1，2，3，4，5），S2（6，7，8，9，10，11），首先是S2移位，有720組，即6個(gè)數(shù)的全排列；然后，S1與S2換位有455種可能的換位（30+150+200+75），即交換1個(gè)有30種可能；交換2個(gè)有150種可能；交換3個(gè)有200種可能（從6里面每次取出3個(gè)的組合數(shù)乘以從5里面每次取出3個(gè)的組合數(shù)）；交換4個(gè)有75種可能（從6里面每次取出4個(gè)的組合數(shù)乘以從5里面每次取出4個(gè)的組合數(shù)）。每次交換后又有S2移位。那么，全部可能的配對(duì)輪次就有327600輪次（455乘以720）［4］。

配對(duì)程序的目的，就是要從所有可能的配對(duì)輪次中找到能夠最好的滿足配對(duì)條件（Pairing Criteria）的一輪配對(duì)。滿足配對(duì)條件的好壞，可以用配對(duì)質(zhì)量（The quality of the pairings）［4］來(lái)衡量。如果一輪配對(duì)達(dá)不到配對(duì)質(zhì)量標(biāo)準(zhǔn)，這一輪配對(duì)就不能被采用。

配對(duì)質(zhì)量標(biāo)準(zhǔn)在配對(duì)前是可以知道的。已知一個(gè)積分組的人數(shù)，以及每個(gè)參賽者的浮動(dòng)史（不同積分配對(duì)，高分者記下浮，低分者記上?。灰演喛照卟辉佥喛眨┖皖伾罚ㄓ擅總€(gè)比賽輪次分配給參賽者的顏色構(gòu)成）；由顏色史又可以知道每個(gè)參賽者的優(yōu)先色（colour preferences）。那么，可以求得最優(yōu)配對(duì)標(biāo)準(zhǔn)（按優(yōu)先順序）：1）最大配對(duì)數(shù)，等于積分組人數(shù)除2（取整）；2）最小浮動(dòng)人數(shù)（例如，如果是同類積分組，偶數(shù)人數(shù)為0，奇數(shù)人數(shù)為1）；3）不能滿足優(yōu)先色的最小配對(duì)數(shù)，例如11人，優(yōu)先白色有3人，優(yōu)先黑色有8人，那么，只有3對(duì)配對(duì)能夠滿足，不能滿足優(yōu)先色的最小配對(duì)數(shù)為2；4）如果有下浮者，不能有一個(gè)下浮者違反浮動(dòng)規(guī)則；5）如果有上浮者，不能有一個(gè)上浮者違反浮動(dòng)規(guī)則［4］。

如果經(jīng)過(guò)所有可能的配對(duì)輪次還不能完成一個(gè)積分組配對(duì)，換句話說(shuō)，就是沒(méi)有一輪配對(duì)能夠滿足當(dāng)前配對(duì)質(zhì)量標(biāo)準(zhǔn)，就需要降低配對(duì)質(zhì)量標(biāo)準(zhǔn)：首先是不能滿足優(yōu)先色的最小配對(duì)數(shù)（遞增）；其次是最小浮動(dòng)人數(shù)（遞增）；第三是最大配對(duì)數(shù)（遞減）。每次降低配對(duì)質(zhì)量標(biāo)準(zhǔn)后再重復(fù)上述移位和換位配對(duì)。也就是說(shuō)，假如有x次降低配對(duì)質(zhì)量標(biāo)準(zhǔn)，那么，上述11人的例子全部可能的配對(duì)輪次就有x乘以327600輪配對(duì)（循環(huán)）。由此可以知道計(jì)算量相當(dāng)大。

2　瑞士賽制配對(duì)方法存在的問(wèn)題

按照移位和換位的順序，下浮者不是按配對(duì)輪次連續(xù)出現(xiàn)，參見表1（5人下浮者）［5］，在表1中，下浮者是在沒(méi)有充分配對(duì)的情況下被更換，例如3號(hào)下浮者分別出現(xiàn)在第1、4、12輪，而不是連續(xù)出現(xiàn)在第1、2、3輪，違背了下浮者充分配對(duì)規(guī)則。3號(hào)下浮者應(yīng)該是在所有可能的配對(duì)結(jié)束后才被更換。所以說(shuō)，移位和換位規(guī)則與浮動(dòng)規(guī)則存在自相矛盾。

表1　5人下浮者

由于移位和換位是排列組合計(jì)算，計(jì)算量相當(dāng)大，手工不可能完全按照移位和換位規(guī)則來(lái)進(jìn)行配對(duì)操作，且移位和換位的順序也很難讓人記住和理解。所以，移位和換位規(guī)則只能起到原則上指導(dǎo)手工操作的作用，可操作性差。所以，我們通?？吹降钠孱惛?jìng)賽規(guī)則中都只是對(duì)棋類瑞士賽的編排作原則性的說(shuō)明。移位和換位的順序不能決定配對(duì)質(zhì)量的優(yōu)劣。配對(duì)程序的目的，就是要在所有可能的配對(duì)輪次中，找到配對(duì)質(zhì)量盡可能最優(yōu)的一輪配對(duì)，而任何一輪配對(duì)都有可能。如果說(shuō)，移位和換位的順序是按配對(duì)質(zhì)量的優(yōu)劣來(lái)排序的，那么，這樣的順序才有實(shí)際意義。但實(shí)際是，移位和換位的順序只是決定了實(shí)力差的最小變動(dòng)到最大變動(dòng)，這種變動(dòng)并不能代表配對(duì)質(zhì)量的優(yōu)劣。假如可以對(duì)每輪配對(duì)都做配對(duì)質(zhì)量的優(yōu)劣統(tǒng)計(jì)，然后按配對(duì)質(zhì)量的優(yōu)劣排序輪次，那么，移位和換位的順序就會(huì)被完全打亂，而不起作用。按配對(duì)質(zhì)量排序輪次，就好比是運(yùn)動(dòng)會(huì)獎(jiǎng)牌排名，先比金牌數(shù)量，再比銀牌和銅牌數(shù)量。但我們需要的還不只是獎(jiǎng)牌排名，只是按獎(jiǎng)牌排名來(lái)確定當(dāng)前配對(duì)質(zhì)量標(biāo)準(zhǔn)，達(dá)不到標(biāo)準(zhǔn)，就逐步降低標(biāo)準(zhǔn)，最后“錄取”的一輪配對(duì)是按團(tuán)體總分來(lái)錄取。當(dāng)然，我們沒(méi)有必要去做獎(jiǎng)牌排名，這樣做計(jì)算量會(huì)更大，影響配對(duì)效率。實(shí)際情況是，在所有配對(duì)輪次中，循環(huán)查找滿足配對(duì)質(zhì)量標(biāo)準(zhǔn)的輪次，通常，在還沒(méi)有結(jié)束循環(huán)時(shí)，就找到了當(dāng)前條件下配對(duì)質(zhì)量最優(yōu)的一輪配對(duì)。所以說(shuō)，我們關(guān)心的只是所有可能的配對(duì)輪次，至于配對(duì)輪次的順序只是因?yàn)橛?jì)算的需要，方便操作和精確計(jì)算才是關(guān)鍵。

對(duì)于同類積分組，移位和換位規(guī)則產(chǎn)生的循環(huán)算法存在大量重復(fù)計(jì)算。按照作者的研究，11人所有可能的配對(duì)輪次只有10395輪次（11×9×7×5×3× 1），后面將會(huì)描述計(jì)算公式。而按照移位和換位規(guī)則有327600輪次，相差了317205輪次。假如S1與S2每次換位后沒(méi)有S2的移位，那就只有1175輪次（720+455），但很顯然，這個(gè)輪次數(shù)不能滿足充分配對(duì)的規(guī)則要求。所以說(shuō)，移位和換位規(guī)則的循環(huán)算法存在大量重復(fù)計(jì)算（x乘以317205輪次），計(jì)算不精確，影響了配對(duì)效率。同時(shí)，這種循環(huán)是缺乏智能化的，也就是說(shuō)，每一次循環(huán)都需要計(jì)算。

其實(shí)，浮動(dòng)者的優(yōu)先順序更為重要，因?yàn)?，只要有一個(gè)浮動(dòng)者不符合浮動(dòng)規(guī)則，不管這一輪的配對(duì)質(zhì)量如何都不能被采用。因此，可以認(rèn)為，分成兩個(gè)子組的移位和換位配對(duì)沒(méi)有實(shí)際意義，反而增加了重復(fù)的配對(duì)輪次（循環(huán)次數(shù)），同時(shí)，也產(chǎn)生了與浮動(dòng)規(guī)則的矛盾。

對(duì)于不同類積分組，下浮者之間無(wú)需配對(duì)，因?yàn)?，下浮者正是由于在上一個(gè)積分組不能配對(duì)才被下浮的，所以，在不同類積分組，所有可能的配對(duì)將減去下浮者之間的配對(duì)。這時(shí)，由于規(guī)定S1包含所有下浮者，所以，分成兩個(gè)子組才有實(shí)際意義。也就是說(shuō)，只需要S2的移位，不需要S1與S2的換位。例外的情況是，當(dāng)最后一個(gè)積分組（可能是不同類積分組）不能完成配對(duì)時(shí)，將與上一個(gè)臨近積分組，合并成一個(gè)新的最后積分組（不同類積分組），這種情況下的不同類積分組，由于高分者之間存在可能配對(duì)的情況，所以，可以當(dāng)作同類積分組對(duì)待。

3　“嵌套式循環(huán)輪次”配對(duì)方法

已知循環(huán)賽奇數(shù)人數(shù)比賽輪次等于參賽人數(shù)，每?jī)奢喼g沒(méi)有重復(fù)配對(duì)。但是，在一個(gè)積分組內(nèi)的瑞士配對(duì)，每?jī)奢喼g允許重復(fù)，只要每?jī)奢喼g有一對(duì)配對(duì)不重復(fù)，就構(gòu)成一輪配對(duì)，因?yàn)?，我們只需要從所有可能的配?duì)輪次中找出一輪配對(duì)。依據(jù)循環(huán)賽配對(duì)輪次的生成原理，可以這樣來(lái)設(shè)計(jì)積分組配對(duì)輪次的生成：積分組人數(shù)N（奇數(shù)）是個(gè)大循環(huán)，大循環(huán)內(nèi)又包含次大循環(huán)，以此類推，直到包含最小循環(huán)，最多可嵌套（N+1）/2個(gè)循環(huán)。大循環(huán)每轉(zhuǎn)動(dòng)一輪，小循環(huán)需要轉(zhuǎn)動(dòng)多輪，每個(gè)循環(huán)都有自己的輪次。因此，依據(jù)概率的算法，全部可能的循環(huán)輪次就等于每個(gè)循環(huán)輪次的乘積。

例如，表2是積分組人數(shù)為5（6）人時(shí)的所有可能的配對(duì)輪次表，是依據(jù)循環(huán)賽固定輪轉(zhuǎn)法原理（即固定一個(gè)位置，其余位置每輪轉(zhuǎn)動(dòng)一個(gè)位置）生成的，其中，大循環(huán)：0、1、2、3、4、5，按U形排列，固定0號(hào)，其余號(hào)每輪逆時(shí)針輪轉(zhuǎn)一個(gè)位置，生成5個(gè)大循環(huán)；子循環(huán)：剩余號(hào)，按序號(hào)從小到大排序，U形排列，固定最大號(hào)，其余號(hào)每輪順時(shí)針輪轉(zhuǎn)一個(gè)位置，在大循環(huán)下生成3個(gè)子循環(huán)。

表2　5（6）人所有可能的配對(duì)輪次表

從表2中可以看到，5（6）人循環(huán)是5輪，其中每一輪都包含了3（4）人循環(huán)；3（4）人循環(huán)是3輪，其中每一輪又都包含了1（2）人循環(huán)；1（2）人循環(huán)只有一輪。因此，全部可能的循環(huán)輪次是5×3×1=15輪；另外，還可以看到下浮者是在充分配對(duì)后才按順序被更換（5-4-3-2-1）。

在一個(gè)積分組內(nèi)的人數(shù)（N）為奇數(shù)時(shí)的配對(duì)輪次與偶數(shù)時(shí)的配對(duì)輪次是相等的，只是奇數(shù)時(shí)每輪中的配對(duì)（場(chǎng)次）少一對(duì)，有一人不能配對(duì)，對(duì)手為0號(hào)。所以，我們只需要推出奇數(shù)人數(shù)配對(duì)輪次計(jì)算公式。如果人數(shù)為偶數(shù)，只需要將每輪中的0號(hào)改為最大號(hào)。

有奇數(shù)數(shù)列1，3，5，…，2k-1。其中k=1，2，3，…，（N+1）/2。

當(dāng)k=1時(shí)，N=1，有（2×1-1）=1輪。

當(dāng)k=2時(shí)，N=3，有（2×1-1）（2×2-1）=3輪。

當(dāng)k=3時(shí)，N=5，有（2×1-1）（2×2-1）（2× 3-1）=15輪。

以此類推。

當(dāng)k=（N+1）/2時(shí)，N=2k-1，有（2×1-1）（2×2-1）（2×3-1）…（2k-1）輪。其中，k表示最多嵌套的循環(huán)數(shù)；N表示積分組內(nèi)人數(shù)（奇數(shù)）。例如：11人：（2×1-1）（2×2-1）（2×3-1）（2×4-1）（2×5-1）（2×6-1）=10395輪。

上述配對(duì)算法，一是實(shí)現(xiàn)了配對(duì)輪次的精確計(jì)算，減少了不必要的循環(huán)次數(shù)，可提高配對(duì)效率；二是大循環(huán)有一對(duì)不能配對(duì)時(shí)，其下的子循環(huán)（小循環(huán)）都可以跳過(guò)，更進(jìn)一步減少了循環(huán)次數(shù)，這正是這種嵌套式循環(huán)設(shè)計(jì)的智能化優(yōu)點(diǎn)；三是配對(duì)輪次的生成，由于遵循了循環(huán)賽固定輪轉(zhuǎn)法原理，所以，更容易使人理解，也方便手工操作記憶，但是，手工操作量的減少對(duì)于完全改善手工操作還是有限，畢竟計(jì)算量還是很大，這也正是這種賽制不宜手工編排的原因；四是配對(duì)輪次按下?。ㄝ喛眨┱邇?yōu)先順序生成，下浮者是在充分配對(duì)后才按順序被更換，更符合瑞士規(guī)則中的浮動(dòng)規(guī)則精神。但上述配對(duì)算法只適用于同類積分組或被當(dāng)作同類積分組。

對(duì)于不同類積分組，由于S1包含所有下浮者，且下浮者之間無(wú)需配對(duì)，所以，只需要S2的移位，無(wú)需S1與S2換位。也就是說(shuō)，所有可能的配對(duì)輪次等于S2的全排列。因此，瑞士賽制傳統(tǒng)配對(duì)方法在這種情況下才是精確計(jì)算。

4　結(jié)束語(yǔ)

筆者在查詢文獻(xiàn)資料、總結(jié)多年實(shí)踐經(jīng)驗(yàn)的基礎(chǔ)上，對(duì)瑞士配對(duì)規(guī)則進(jìn)行了專門研究。研究結(jié)果表明，瑞士配對(duì)方法存在大量重復(fù)計(jì)算，計(jì)算不精確，影響了計(jì)算機(jī)配對(duì)效率；且手工難以完全按照瑞士規(guī)則中的移位和換位規(guī)則執(zhí)行配對(duì)操作。對(duì)此，作者提出了新的“嵌套式循環(huán)輪次”配對(duì)方法，并給出了其配對(duì)輪次計(jì)算公式，這個(gè)公式可以達(dá)到精確計(jì)算目的，提高計(jì)算機(jī)的配對(duì)效率和智能化。由于配對(duì)輪次的生成方法遵循了循環(huán)賽“固定輪轉(zhuǎn)法”原理，使瑞士配對(duì)方法更容易理解，也方便手工操作記憶，同時(shí)，更能滿足瑞士規(guī)則中的浮動(dòng)規(guī)則要求?？梢哉f(shuō)，從配對(duì)的效率和可操作性上，新方法可以改進(jìn)傳統(tǒng)瑞士配對(duì)方法。

［1］World Chess Federation［EB/OL］.http：//www.fide.com/.

［2］徐家亮.國(guó)際象棋競(jìng)賽裁判手冊(cè)［M］.北京：人民體育出版社，2007.90-115.

［3］FIDE Swiss Rules［EB/OL］.http：//www.fide.com/component/ handbook/？id=18&view=category.

［4］Dutch System［EB/OL］.http：//www.fide.com/component/ handbook/？id=167&view=article.

［5］Burstein System［EB/OL］.http：//www.fide.com/fide/handbook. html？id=85&view=article.

［6］張潔.學(xué)校球類與瑞士賽制相關(guān)研究［J］.長(zhǎng)沙通信職業(yè)技術(shù)學(xué)院學(xué)報(bào)，2013（2）.

［7］陳堅(jiān)，等.球類競(jìng)賽的排名式積分編排方法研究［J］.湖北財(cái)經(jīng)高等?？茖W(xué)校學(xué)報(bào)，2009（4）.

［8］徐善瑤.在積分編排制比賽中定位編排法［J］.棋海新友，1993（1）.

［9］Heinz Herzog.Swiss-Manager［CP/OL］.http：//swissmanager.at.

［10］Swiss Perfect［CP/OL］.http：//www.SwissPerfect.com.

Research on pairing algorithm of Swiss System

DONG Dong-feng
（Hunan Post and Telecommunication College，Changsha，Hunan，China 410015）

Swiss System（including pairing rules）has been in continuous improvement from the beginning.Based on literature summary query and years of experience，the author specializes in the Swiss pairing rules.The research results show that the Swiss pairing method has a large number of repeated calculations and imprecise computation which affects the computer pairing efficiency and it is difficult to complete the pairing operation manually according to the transposition and exchange rules in Swiss rules.So，the author proposes a new“nested loop round”pairing method and the formula for calculating the pairing rounds is given.The formula can achieve the accurate calculation and improve the pairing efficiency and intelligent of the computer.The method for generating pairing rounds follows the round robin"fixed rotation"principle，so the Swiss pairing method is easier to understand，and also convenient for manual operation.At the same time，it can meet the requirements of the floating rules in the Swiss rules.It can be said that from the pairing efficiency and maneuverability，the new method can improve the traditional Swiss pairing method.

Swiss System；transposition；exchange；pairing procedures；pairing rounds；quality of the pairings；fixed rotation

10.3969/j.issn.2095-7661.2015.01.020】

G808.24

A

2095-7661（2015）01-0077-04

2014-12-17

董東風(fēng)（1958-），男，湖南長(zhǎng)沙人，湖南郵電職業(yè)技術(shù)學(xué)院教授，研究方向：體育競(jìng)賽編排。