floodgateのマッチメイク改良案をシミュレートしてみました
http://www.sgtpepper.net/kaneko/diary/20120511.html の山下＠YSSさんのコメントの案です。
_ 山下＠YSS (2012-05-15 20:24)
floodgateの対戦の組み方ですが今の勝ち抜きトーナメント？形式はちょっと
対戦相手がかたよる傾向があると思います。YssL980X_1cだと
BlunderXX_4cとは1度も当たらずsakurapyon軍団ばかり、など。
負けたらいきなりpishogiまで落ちる、というのも結構きついです^^;
提案なのですが、ランダムに組み合わせを10個作って、個々のレーティングの差の合計が
最小の組み合わせを選ぶ、とかはどうでしょうか？
前回と同じ対戦は+400点とかで組みにくくして。
CGOSで使われれる？らしい方法の受け売りなのですが・・・
試しに、今日の21:05時点での2週間レーティングを元に、どういう組み合わせになるかやってみました。（vccさんとgps_さんは同じ名前で2プレイヤーありましたので、Rが低い方のプレイヤーのデータを削除しました。）
まずは、「ランダムに組み合わせを10個作る」方法。対局結果によるR変動は考慮せずに、全対局者が1000局指した場合の、対局ごとのRの差のヒストグラムと対局相手のカウントです。（画像クリックで原寸表示します。）
上のグラフは、横軸が対局ごとのレーティングの差、縦軸が対局回数です。下の方は、プレイヤーごとの対局回数で、例えば「tsutsukana_2630QM」の行の「3」の列は「tsutsukana_2630QM対gpsfish_4cの対局回数」になります。
それから、「ランダムに組み合わせを100個作る」場合もやってみました。グラフの見方は上と同じです。
ぱっと見では分かりづらいですが、R差の大きい対局数が減っています。組み合わせの個数が増えた為、R差の小さい対局が組まれやすくなっているものと思います。
今のマッチメイク方式だと、割と同じ相手との対局が多かったりしますので、山下さんの改良案は面白そうだと思います。floodgateの管理者の方も大変かとは思いますが、マッチメイクの改良をして貰えるならありがたいです。
それから、今回作った組み合わせのシミュレータですが、「続きを読む」の後にソースを置いておきますので興味のある方は触ってみて下さい。
使い方：下記のソースを「MatchmakeSimulator.java」という名前のファイルに貼り付けて、コマンドプロンプトなりシェルなりから「javac MatchmakeSimulator.java && java MatchmakeSimulator 1000 10」と実行すると結果がreport.csvに書き出されます。最初の「1000」がマッチメイク回数、次の「10」がランダムに作る対局の数です。
/** * MatchmakeSimulator.java * * 2012/08/15 森岡 祐一 */ import java.util.*; import java.io.*; /** * floodgateのマッチメイク改良案のエミュレートをするクラス。 * （http://www.sgtpepper.net/kaneko/diary/20120511.html のコメント欄参照。） */ public class MatchmakeSimulator { /** * プレイヤー（対局するエンジン）の情報を表すクラス。 */ private static class Player { /** * プレイヤー名。 */ public final String name; /** * レーティング。 */ public final int rating; /** * プレイヤー名とレーティングを指定してインスタンスを生成する。 */ public Player( final String name, final int rating ) { this.name = name; this.rating = rating; }// Player(...) public String toString() { return this.name; }// toString() public boolean equals( final Object obj ) { if( ! ( obj instanceof Player ) ) return false; return this.name.equals( ((Player)obj).name ); }// equalst(...) }// class Player /** * 対局の組み合わせを表すクラス。 */ private static class Game { /** * レーティングが上のプレイヤー。 */ public final Player player1; /** * レーティングが下のプレイヤー。 */ public final Player player2; public Game( final Player playerA, final Player playerB ) { if( playerA.rating < playerB.rating ) { this.player1 = playerB; this.player2 = playerA; } else { this.player1 = playerA; this.player2 = playerB; }// if(...) }// Game(...) public String toString() { return String.format( "Game[ %s vs %s ]", this.player1, this.player2 ); }// toString() public boolean equals( final Object obj ) { if( ! ( obj instanceof Game ) ) return false; final Game other = (Game)obj; return this.player1.equals( other.player1 ) && this.player2.equals( other.player2 ); }// equals(....) }// class Game /** * マッチメイクを行い、対局のリストを返す。 * 引数preGameListには直前のマッチメイク結果を渡す（初回のマッチメイク時はnullを渡す事）。 * * **** 引数playerListの要素数が偶数である事を前提に作ってあるので注意。 **** * **** 引数playerListに対して変更を行うので注意。 **** */ private static List<Game> matchmake( final List<Player> playerList, final List<Game> preGameList, final int CANDIDATE_COUNT ) { assert playerList.size() % 2 == 0 : playerList; // レーティング差の合計の最小値 int minRatingDiffSum = Integer.MAX_VALUE; // 返り値 List<Game> result = null; // マッチメイクの候補を一定個数生成する for( int i = 0; i < CANDIDATE_COUNT; i++ ) { // プレイヤーのリストをシャッフルする Collections.shuffle( playerList ); // リストの先頭から順に対局を組んでいく List<Game> resultCandidate = new ArrayList<Game>(); for( int j = 0; j < playerList.size(); j += 2 ) { resultCandidate.add( new Game( playerList.get( j ), playerList.get( j + 1 ) ) ); }// for(..j..) // レーティング差の合計を計算する int diffSum = 0; for( final Game game : resultCandidate ) { assert game.player2.rating <= game.player1.rating; diffSum += game.player1.rating - game.player2.rating; // 直前のマッチメイクで同じ対局があればR差に+400する if( preGameList != null && preGameList.contains( game ) ) diffSum += 400; }// for(..j..) // System.err.println( String.format( "resultCandidate==%s, diffSum==%d", resultCandidate, diffSum ) ); // レーティング差の合計が今までの値より小さかったら返り値の候補とする。 if( diffSum < minRatingDiffSum ) { result = resultCandidate; minRatingDiffSum = diffSum; }// if(...) }// for(..i..) return result; }// matchmake(...) public static void main( String[] args ) throws Exception { if( args.length < 2 ) { System.err.println( "＜希望するマッチメイク回数＞と＜1マッチメイクあたりの候補数＞をコマンドライン引数で指定して下さい。" ); System.exit( 0 ); }// if(...) // 対局回数 final int MAX_GAME = Integer.parseInt( args[ 0 ] ); // 候補数 final int CANDIDATE_COUNT = Integer.parseInt( args[ 1 ] ); // プレイヤーのリストを生成・初期化 // （2012/08/15 21:05時点でのプレイヤーとレーティング） List<Player> playerList = new ArrayList<Player>(); playerList.add( new Player( "vcc", 2863 ) ); playerList.add( new Player( "tsutsukana_2630QM", 2861 ) ); playerList.add( new Player( "i7-2600_8T_bona_Ver6.0", 2848 ) ); playerList.add( new Player( "gpsfish_4c", 2798 ) ); playerList.add( new Player( "ske48", 2781 ) ); playerList.add( new Player( "LePenseur", 2764 ) ); playerList.add( new Player( "bona_Sinobu", 2749 ) ); playerList.add( new Player( "Keep_firmness", 2747 ) ); playerList.add( new Player( "Gekisashi_X5590_1c", 2741 ) ); playerList.add( new Player( "ZERO", 2709 ) ); playerList.add( new Player( "Shueso_2c", 2695 ) ); playerList.add( new Player( "Revolver", 2613 ) ); playerList.add( new Player( "MK-shogi", 2577 ) ); playerList.add( new Player( "bona_1c", 2562 ) ); playerList.add( new Player( "BlunderXX_4c", 2550 ) ); playerList.add( new Player( "gps_l", 2470 ) ); playerList.add( new Player( "bona6.0_norm", 2404 ) ); playerList.add( new Player( "gps_", 2401 ) ); playerList.add( new Player( "Apery", 2214 ) ); playerList.add( new Player( "gps_normal", 2150 ) ); playerList.add( new Player( "vps_mc", 1708 ) ); playerList.add( new Player( "drdr_human", 1691 ) ); playerList.add( new Player( "HUI_shogi", 1680 ) ); playerList.add( new Player( "Caffic", 1565 ) ); playerList.add( new Player( "Gasyou_Atom-D510_1c2t", 1463 ) ); playerList.add( new Player( "gps500", 1444 ) ); playerList.add( new Player( "sakurapyon-2012-depth2.4", 1120 ) ); playerList.add( new Player( "sakurapyon-2012-depth2.2", 738 ) ); List<Game> preGameList = null; // ログ出力用ファイルをオープン final PrintWriter writer = new PrintWriter( new BufferedWriter( new FileWriter( "result.csv" ) ) ); // 対局回数カウント用の配列 final int[][] matchCounter = new int[ playerList.size() ][ playerList.size() ]; // コマンドライン引数で指定された回数だけマッチメイクする for( int i = 0; i < MAX_GAME; i++ ) { preGameList = matchmake( new ArrayList<Player>( playerList ), preGameList, CANDIDATE_COUNT ); System.err.println( String.format( "マッチメイク結果==%s", preGameList ) ); // ログファイルに対局のレーティング差を出力しつつ、 // 対局回数をカウントする for( final Game game : preGameList ) { final Player p1 = game.player1; final Player p2 = game.player2; writer.println( String.format( "%s, %d", game, p1.rating - p2.rating ) ); matchCounter[ playerList.indexOf( p1 ) ][ playerList.indexOf( p2 ) ]++; matchCounter[ playerList.indexOf( p2 ) ][ playerList.indexOf( p1 ) ]++; }// for(...) }// for(..i..) writer.println( "----------------------------------------------------------" ); // 各プレイヤーごとの対局数を出力 for( int i = 0; i < playerList.size(); i++ ) { writer.print( String.format( ",%d", i ) ); } writer.println(); for( int i = 0; i < playerList.size(); i++ ) { writer.print( String.format( "%s,", playerList.get( i ) ) ); for( int j = 0; j < playerList.size(); j++ ) { writer.print( String.format( "%d,", matchCounter[ i ][ j ] ) ); }// for(..j..) writer.println(); }// for(..i..) // ファイルクローズ writer.close(); }// main(...) }// MatchmakeSimulator // EOF
