Skip to content

Дневник программиста: система Эло

03/08/2009

О формате «дневник программиста» я узнал на StackOverflow. Там рекомендовали ведение такого дневника как один из способов профессионального роста. Мне этот способ показался интересным, и вот первая запись🙂 Пока блог, думаю, будет вестись здесь, а если наберётся хотя бы три записи — я найду для него отдельное место.

Долго ли, коротко ли — захотелось мне сделать реализацию системы Эло. Начальной идеей было сделать централизованный рейтинг игроков Warhammer 40K. Как оказалось впоследствии, Эло для этого не очень подходит.

Но — всё по порядку.

Система Эло в принципе не очень сложна. Определённая разница в очках означает определённый шанс победы над противником (в оригинальной работе Эло 200 очков разницы соответствуют шансу выигрыша 75%). Вначале система считает ожидаемый рейтинг игроков, затем сравнивает его с реальными результатами турнира. Если игрок выступил лучше ожидаемых очков, это означает что его рейтинг ниже его реальной силы, и он должен быть увеличен. В качестве стартового рейтинга для новичков можно выбирать в принципе любое значение — обычно используется 1600 или 1200.

Первый вариант был довольно прост и неправилен🙂

<style>
    div.perfrating {
        padding: 10px;
        background-color: #DDD;
        border: 1px solid #444;
    }
</style>
<?php
    define('NUM_TOURNAMENTS', 40);
    define('NUM_PLAYERS', 40);

    function random_pairing($pairs) {
        $out = array();

        // Fail if number of items is odd
        $first = array();
        $second = array();

        for($i = 0; $i < $pairs * 2; $i++){

            $nums&#91;&#93; = $i;

        }

        shuffle($nums);

        $first = array_slice($nums, 0, $pairs);
        $second = array_slice($nums, $pairs, $pairs);

        shuffle($second);

        return array_combine($first, $second);
    }


    $players = array();

    for($i=0;$i<=NUM_PLAYERS;$i++){
        $players&#91;$i&#93; = rand(2200,2220); // Beginners rating in Elo system
    }


    for($tour=0;$tour<=NUM_TOURNAMENTS;$tour++){

        echo '<h3>Tournament '. $tour . '</h3>';
        // Choose 20 participants at random
        $mob = array_keys($players);
        shuffle($mob);
        $participants = array_combine(range(0,19), array_slice($mob, 0, 20));

        ksort($participants);
        // Decide the pairing
        $pairs = random_pairing(10);

        $subtour = 0;

        // new log every tournament
        $tour_log = array();
        foreach ($pairs as $player1 => $player2) {

            // Fetch ratings
            $rating1 = $players[$participants[$player1]];
            $rating2 = $players[$participants[$player2]];

            // Throw a dice here
            $points = rand(1, $rating1 + $rating2);
            if ($points <= $rating1) {
                // player 1 won
                $winner = $participants&#91;$player1&#93;;
                $loser  = $participants&#91;$player2&#93;;
            } else {
                $winner = $participants&#91;$player2&#93;;
                $loser  = $participants&#91;$player1&#93;;
            }

            // Add log record
            $tourlog&#91;&#93; = array(
                'player1' => $participants[$player1],
                'player2' => $participants[$player2],
                'winner'  => $winner,
                'loser'  => $loser
            );

            echo '<em>(' . $subtour . ')</em> ' . $participants[$player1] . '[' . $players[$participants[$player1]] . '] vs ' . $participants[$player2] . '[' . $players[$participants[$player2]] . '], winner is <b>' . $winner . '</b><br/>';
            $subtour++;
        }

        // Performance Rating is a hypothetical rating that would result from the games
        // of a single event only. Some chess organizations use the "algorithm of 400"
        // to calculate performance rating. According to this algorithm, performance rating
        // for an event is calculated by taking (1) the rating of each player beaten and
        // adding 400, (2) the rating of each player lost to and subtracting 400, (3)
        // the rating of each player drawn, and (4) summing these figures and dividing by
        // the number of games played.

        $perfRating = array();

        echo '<span>Tour #' . $tour . ' games are ended, tourlog has ' . count($tourlog) .' records</span>';
        echo '<div class="perfrating">';
        foreach($participants as $participant) {
            $rating = 0;
            $games_played = 0;
            // Process tour logs
            foreach($tourlog as $tour_record) {

                if ($participant == $tour_record['winner']) {
                    $rating = $players[$tour_record['loser']] + 400;
                    $games_played++;
                } elseif($participant == $tour_record['loser']) {
                    $rating = $players[$tour_record['winner']] - 400;
                    $games_played++;
                }

            }

            // Calculate performance ratings:

            if ($games_played > 0) {
                $perfRating[$participant] = $rating / $games_played;
                echo 'PerformanceRating of player ' . $participant . ' on event #'. $tour .' is ' . $perfRating[$participant] . '<br/>';
            }

        }
        echo '</div>';

    }
?>

Это первая из зарегистрированных в Snipplr версий — более ранние не сохранились. Все формулы взяты со страницы Elo rating system в английской Википедии.

Функция random_pairing — моя давняя наработка (Snipplr подсказывает что январская). Получает количество пар участников, возвращает пары в виде массива array('игрокX' => 'игрокY', 'игрокA' => 'игрокB').

Сам рейтинг Эло казался мне достаточно сложным на тот момент, и я решил для начала реализовать Performance rating. Это рейтинг выступления игроков на одном отдельно взятом event`е — обычно турнире. Считается он довольно просто, по так называемой «схеме 400»: берётся рейтинг каждого побеждённого оппонента и к нему прибавляется 400; рейтинг каждого оппонента которому игрок проиграл, и отнимается 400; и рейтинг каждого оппонента с которым сыграли вничью без изменений. Потом получившаяся сумма делится на количество сыгранных раундов.

Простой пример: Алиса играет на турнире три партии. Её рейтинг перед турниром — 1310. Она выигрывает у Боба, чей рейтинг равен 1360 (неплохая победа), прогрывает Кэрол, чей рейтинг 1321, и сводит вничью игру с Дейвом (рейтинг 1350).

Performance Rating у Алисы равен:

((1360 + 400) + (1321 — 400) + 1350) / 3 ~= 1343.6

Всемирная шахматная ассоциация ФИДЕ вычисляет performance rating немного по другому, но нас сейчас это волновать не должно.

Этот рейтинг сам по себе не особо много значит, он нужен исключительно для сравнения с другими игроками в том же турнире и с выступлениями того же игрока в предыдущих эвентах. Например, новичок, победивший двух серьёзных противников и выбывший из турнира вполне может иметь больший Performance Rating чем признаный чемпион, одной рукой сделавший всех противников и выигравший турнир.

На следующий день я переработал большую часть этого кода — вынес некоторые магические переменные в константы, вынес проведение тура и отдельной игры в отдельные функции play_tier и play_game, выделил расчёт performance rating’а в отдельную функцию. В общем, сделал небольшой рефакторинг по Макконнеллу🙂 Читать код стало действительно удобнее:

<style>
    div.perfrating {
        padding: 10px;
        background-color: #DDD;
        border: 1px solid #444;
    }

    span.rating_change {
        display: block;
        padding: 5px;
        background-color: light-blue;
        border: 1px solid blue;
    }
</style>
<?php
    define('NUM_TOURNAMENTS', 1);
    define('NUM_PLAYERS', 70);
    define('NUM_PARTICIPANTS', 32);
    define('K_KOEFF', 32);

    // We need even number of participants to do pairing
    assert('NUM_PARTICIPANTS % 2 == 0');

    function random_pairing($pairs) {
        $out = array();

        // Fail if number of items is odd
        $first = array();
        $second = array();

        for($i = 0; $i < $pairs * 2; $i++){

            $nums&#91;&#93; = $i;

        }

        shuffle($nums);

        $first = array_slice($nums, 0, $pairs);
        $second = array_slice($nums, $pairs, $pairs);

        shuffle($second);

        return array_combine($first, $second);
    }

    function play_game($player1, $player2, &$participants2) {
        global $players;

        // Fetch ratings
        $rating1 = $players&#91;$player1&#93;;
        $rating2 = $players&#91;$player2&#93;;

        // Throw a dice here
        $points = rand(1, $rating1 + $rating2);
        if ($points <= $rating1) {
            // player 1 won
            $winner = $player1;
            $loser  = $player2;
        } else {
            $winner = $player2;
            $loser  = $player1;
        }

        $participants2&#91;&#93; = $winner;

        echo '<em>(' . $subtour . ')</em> ' . $player1 . '[' . $players[$player1] . '] vs ' . $player2 . '[' . $players[$player2] . '], winner is <b>' . $winner . '</b><br/>';

        // Add log record
        $log_record = array(
            'player1' => $player1,
            'player2' => $player2,
            'winner'  => $winner,
            'loser'  => $loser
        );

        return $log_record;

    }

    function play_tier($participants, &$tourlog) {
        global $players;
        ksort($participants);
        // Decide the pairing
        $pairs = random_pairing(count($participants) / 2);

        $subtour = 0;

        // Second round
        $participants2 = array();
        foreach ($pairs as $player1 => $player2) {

            $tourlog[] = play_game($participants[$player1], $participants[$player2], $participants2);

            $subtour++;
        }

        return $participants2;
    }

    function display_performance_rating($tourlog, $participants) {
        global $players;
        // Performance Rating is a hypothetical rating that would result from the games
        // of a single event only. Some chess organizations use the "algorithm of 400"
        // to calculate performance rating. According to this algorithm, performance rating
        // for an event is calculated by taking (1) the rating of each player beaten and
        // adding 400, (2) the rating of each player lost to and subtracting 400, (3)
        // the rating of each player drawn, and (4) summing these figures and dividing by
        // the number of games played.
        echo '<div class="perfrating">';
        foreach($participants as $participant) {
            $Prating = 0;
            $games_played = 0;
            // Process tour logs
            foreach($tourlog as $tour_record) {

                if ($participant == $tour_record['winner']) {
                    $Prating += $players[$tour_record['loser']] + 400;
                    $games_played++;
                } elseif($participant == $tour_record['loser']) {
                    $Prating += $players[$tour_record['winner']] - 400;
                    $games_played++;
                }

            }

            // Calculate performance ratings:

            if ($games_played > 0) {
                $perfRating[$participant] = round($Prating / $games_played);
                // echo 'PerformanceRating of player ' . $participant . ' on event #'. $tour .' is ' . IntVal($perfRating[$participant]) . '<br/>';
            }

            arsort($perfRating);


        }

        foreach ($perfRating as $player => $p_rating) {
            echo ' PerformanceRating of player ' . $player . ' on event is ' . $p_rating . '<br/>';
        }

        echo '</div>';

    }

    function process_ratings($tourlog) {
        global $players;

        // Expected scores
        $exp = array();
        // Actual scores
        $s = array();
        // Games played
        $games_count = array();

        foreach($tourlog as $tour_record) {

            // Expected scores
            $exp[$tour_record['player1']] += 1 / (1 + pow(10, (($players[$tour_record['player2']] - $players[$tour_record['player1']])/400)));
            // echo 'Expected rating for player '  . $tour_record['player1'] . ' = ' . $exp1 . '<br/>';
            $exp[$tour_record['player2']] += 1 / (1 + pow(10, (($players[$tour_record['player1']] - $players[$tour_record['player2']])/400)));
            // echo 'Expected rating for player '  . $tour_record['player2'] . ' = ' . $exp2 . '<br/>';

            $games_count[$tour_record['player1']]++;
            $games_count[$tour_record['player2']]++;

            if ($tour_record['winner'] == $tour_record['player1']) {
                $s[$tour_record['player1']] += 1;
                $s[$tour_record['player2']] -= 1;
            } else {
                $s[$tour_record['player2']] += 1;
                $s[$tour_record['player1']] = 1;
            }

        }

        // Do calculations only for those in the current log
        $participants = array_keys($games_count);
        foreach($participants as $player) {
            $newrating = round($players[$player] + K_KOEFF * ($s[$player] - $exp[$player]));
            echo '<div>Player ' . $player . ' have expected score ' . $exp[$player] . ' and actual ' . $s[$player] .  '</div>';
            if ($players[$player] != $newrating) {
                echo '<span class="rating_change">Player ' . $player . ' has rating change from <em class="rating">' . $players[$tour_record['player1']] . '</em> to <em class="rating">' . $newrating . '</em></span>';
            }

        }

    }

    //                              BEGIN

    global $players;
    $players = array();

    for($i = 0; $i <= NUM_PLAYERS; $i++){
        $players&#91;$i&#93; = rand(2200, 2220); // Beginners rating in Elo system
    }

    for($tour = 0; $tour <= NUM_TOURNAMENTS; $tour++){

        echo '<h3>Tournament '. $tour . '</h3>';
        // Choose 20 participants at random
        if (count($players) > NUM_PARTICIPANTS) {
            $mob = array_keys($players);
            shuffle($mob);
            $participants = array_combine(range(0,NUM_PARTICIPANTS - 1), array_slice($mob, 0, NUM_PARTICIPANTS));
        } elseif (count($players) == NUM_PARTICIPANTS) {
            $participants =array_combine(range(0,NUM_PARTICIPANTS - 1), array_keys($players));
        } else {
            echo 'Too few players'.
            exit;
        }

        // new log every tournament
        $tourlog = array();

        echo '<h4>Tier 0</h4>';
        $participants1 = play_tier($participants, $tourlog);

        // TIER 1
        echo '<h4>Tier 1</h4>';
        $participants2 = play_tier($participants1, $tourlog);

        // TIER 2

        echo '<h4>Tier 2</h4>';
        $participants3 = play_tier($participants2, $tourlog);

        // TIER 3

        echo '<h4>Tier 3</h4>';
        $participants4 = play_tier($participants3, $tourlog);

        // FINALS

        echo '<h4>Finals</h4>';
        $winner = play_tier($participants4, $tourlog);


        echo '<span>Tour #' . $tour . ' games are ended, tourlog has ' . count($tourlog) .' records</span>';

        // RATINGS CALCULATION
        display_performance_rating($tourlog, $participants);

        process_ratings($tourlog);
    }
?>

Вынесение тура в отдельную функцию упростило проведение турниров на выбывание. Швейцарскую систему я не вводил — как я уже писал, прицел был на Warhammer 40K, а там такой формат турнира — редкость. Впрочем, система Эло показала себя неплохо даже в этом случае (изначально я не был уверен на этот счёт).

Также теперь для игрока высчитывался новый рейтинг (но пока не присваивался — это был просто тест).

Выставив тысячу турниров по 32 участника (большой тест), я запустил скрипт. Расчёт занял меньше минуты. После расчёта я понял что что-то пошло не так — большинство игроков (точнее, все кроме одного) ушли в глубокие минуса. При 100 турнирах этот эффект не был так выражен.

Изучение кода и статьи в Википедии (а также на нескольких других ресурсах) показало что я невнимательно прочитал статью — победителю в системе Эло начислялся 1 балл, проигравшему не начислялось ничего. У меня же проигравший получал -1 балл.

Кстати, чтобы до этого дойти пришлось создать базу данных, сложить туда все полученные игроками за 1000 турниров баллы и вычислить сумму. Нашёлся дефицит примерно в ~12000 баллов.

            if ($tour_record['winner'] == $tour_record['player1']) {
                $s[$tour_record['player1']] += 1;
                $s[$tour_record['player2']] -= 1;
            } else {
                $s[$tour_record['player2']] += 1;
                $s[$tour_record['player1']] = 1;
            }

Вот часть кода, ответственная за начисление баллов. Сейчас, кстати, можно видеть ещё один баг, который от меня ускользнул до написания статьи — в последней строке я использовал

$s[$tour_record['player1']] = 1;

вместо

$s[$tour_record['player1']] -= 1;

Неудивительно, что результаты оказались такими плачевными.

В этом же варианте я узнал ещё об одном своём проколе: я считал что выражение 10^3 возводит 10 в третью степень, но оказалось что в PHP это — бинарная функция XOR. Чтобы это понять, потребовался отдельный вопрос на StackOverflow🙂

Следующий вариант был уже последним:

<style>
    div.perfrating {
        padding: 10px;
        background-color: #DDD;
        border: 1px solid #444;
    }

    span.rating_change {
        display: block;
        padding: 5px;
        background-color: light-blue;
        border: 1px solid blue;
    }
</style>
<?php
    set_time_limit(120);

    define('NUM_TOURNAMENTS', 1000);
    define('NUM_PLAYERS', 64);
    define('NUM_PARTICIPANTS', 32);
    define('K_KOEFF', 16);
    define('START_RATING', 1600);

    // We need even number of participants to do pairing
    assert('NUM_PARTICIPANTS % 2 == 0');

    class player {
        public $strength;
        public $rating;
        public $games;

        /**
        * Constructor
        *
        * @param int $rating Start rating

        * @return player
        */
        public function player($rating) {
            $this->rating = $rating;
            $this->strength = rand(0, 100);
        }

        /**
        * Calculate K-factor for player
        *
        * @return int K-factor
        */
        public function get_k_factor() {

            $factor = 25;

            if ($this->games > 30) {
                $factor = 22;
            }

            if ($this->rating > 1700) {
                $factor = 20;
            }

            if ($this->rating > 1900) {
                $factor = 15;
            }

            if ($this->rating > 2100) {
                $factor = 10;
            }

            return $factor;
        }
    }
    function connect() {
        $host="localhost";
        $login="root";
        $pass="";
        $dname="elo";
        mysql_connect($host,$login,$pass) or die("Problem with Database Connection");
        mysql_select_db("$dname");

        // Create the table in case someone wants to check the script
        mysql_query(
            "CREATE TABLE IF NOT EXISTS `deltas` (
                `value` decimal(11,4) NOT NULL
            ) ENGINE=MyISAM DEFAULT CHARSET=utf8;"
        );
    }

    function random_pairing($pairs) {
        $out = array();

        // Fail if number of items is odd
        $first = array();
        $second = array();

        for($i = 0; $i < $pairs * 2; $i++){

            $nums&#91;&#93; = $i;

        }

        shuffle($nums);

        $first = array_slice($nums, 0, $pairs);
        $second = array_slice($nums, $pairs, $pairs);

        shuffle($second);

        return array_combine($first, $second);
    }

    function play_game($player1, $player2, &$participants2) {
        global $players;

        // Fetch ratings
        $str1 = $players&#91;$player1&#93;->strength;
        $str2 = $players[$player2]->strength;

        // Throw a dice here
        // $points = rand(1, $rating1 + $rating2);
        if ($str2 <= $str1) {
            // player 1 won
            $winner = $player1;
            $loser  = $player2;
        } else {
            $winner = $player2;
            $loser  = $player1;
        }

        $participants2&#91;&#93; = $winner;

        echo '' . $player1 . '&#91;' . $players&#91;$player1&#93;->rating . '] vs ' . $player2 . '[' . $players[$player2]->rating . '], winner is <b>' . $winner . '</b><br/>';

        $status = 'normal';
        // 5% of games end in draw.
        // User that go in next tier determined by VP
        if (rand(0,100) <= 5) {
            $status = 'draw';
        }

        // Add log record
        $log_record = array(
            'player1' => $player1,
            'player2' => $player2,
            'winner'  => $winner,
            'loser'  => $loser,
            'status' => $status
        );

        return $log_record;

    }

    function play_tier($participants, &$tourlog) {
        global $players;
        ksort($participants);
        // Decide the pairing
        $pairs = random_pairing(count($participants) / 2);

        $subtour = 0;

        // Second round
        $participants2 = array();
        foreach ($pairs as $player1 => $player2) {

            $tourlog[] = play_game($participants[$player1], $participants[$player2], $participants2);

            $subtour++;
        }

        return $participants2;
    }

    /**
    * Performance Rating is a hypothetical rating that would result from the games
    * of a single event only. Some chess organizations use the "algorithm of 400"
    * to calculate performance rating. According to this algorithm, performance rating
    * for an event is calculated by taking (1) the rating of each player beaten and
    * adding 400, (2) the rating of each player lost to and subtracting 400, (3)
    * the rating of each player drawn, and (4) summing these figures and dividing by
    * the number of games played.
    *
    * @param mixed $tourlog
    * @param mixed $participants
    */
    function display_performance_rating($tourlog, $participants) {
        global $players;
        //
        echo '<div class="perfrating">';
        foreach ($participants as $participant) {
            $Prating = 0;
            $games_played = 0;
            // Process tour logs
            foreach($tourlog as $tour_record) {

                if ($tour_record['status'] == 'draw' && ($participant == $tour_record['player1'] || $participant == $tour_record['player2']) ) {
                    if ($participant == $tour_record['player1']) {
                        $Prating += $players[$tour_record['player2']]->rating;
                    } else {
                        $Prating += $players[$tour_record['player1']]->rating;
                    }
                } elseif ($participant == $tour_record['winner']) {
                    $Prating += $players[$tour_record['loser']]->rating + 400;
                    $games_played++;
                } elseif($participant == $tour_record['loser']) {
                    $Prating += $players[$tour_record['winner']]->rating - 400;
                    $games_played++;
                }

            }

            // Calculate performance ratings:

            if ($games_played > 0) {
                $perfRating[$participant] = round($Prating / $games_played);
                // echo 'PerformanceRating of player ' . $participant . ' on event #'. $tour .' is ' . IntVal($perfRating[$participant]) . '<br/>';
            }

            arsort($perfRating);


        }

        foreach ($perfRating as $player => $p_rating) {
            echo ' PerformanceRating of player ' . $player . ' on event is ' . $p_rating . '<br/>';
        }

        echo '</div>';

    }

    function process_ratings($tourlog) {
        global $players;

        // Expected scores
        $exp = array();
        // Actual scores
        $s = array();
        // Games played
        $games_count = array();

        foreach ($tourlog as $tour_record) {

            // Expected scores
            $exp[$tour_record['player1']] += 1 / (1 + pow(10, (($players[$tour_record['player2']]->rating - $players[$tour_record['player1']]->rating)/400)));
            $exp[$tour_record['player2']] += 1 / (1 + pow(10, (($players[$tour_record['player1']]->rating - $players[$tour_record['player2']]->rating)/400)));

            $games_count[$tour_record['player1']]++;
            $games_count[$tour_record['player2']]++;

            if ($tour_record['status'] == 'draw') {
                $s[$tour_record['player1']] += 0.5;
                $s[$tour_record['player2']] += 0.5;
            } elseif ($tour_record['winner'] == $tour_record['player1']) {
                $s[$tour_record['player1']] += 1;
                // $s[$tour_record['player2']] -= 1;
            } else {
                $s[$tour_record['player2']] += 1;
                // $s[$tour_record['player1']] = 1;
            }

        }

        // Do calculations only for those in the current log
        $participants = array_keys($games_count);
        foreach ($participants as $player) {
            $newrating = round($players[$player]->rating + $players[$player]->get_k_factor() * ($s[$player] - $exp[$player]));
            echo '<div>Player ' . $player . ' have expected score ' . $exp[$player] . ' and actual ' . $s[$player] .  '</div>';
            if ($players[$player]->rating != $newrating) {
                echo '<span class="rating_change">Player ' . $player . ' has rating change from <em class="rating">' . $players[$player]->rating . '</em> to <em class="rating">' . $newrating . '</em> (delta is ' . ($s[$player] - $exp[$player]) .' and k-factor is ' . $players[$player]->get_k_factor() . ')</span>';
                mysql_query(
                    "INSERT INTO  `elo`.`deltas` (
                        `value`
                    )
                    VALUES (
                        '" . ($s[$player] - $exp[$player]). "'
                    );"
                );

                // New rating
                $players[$player]->rating = $newrating;
                $players[$player]->games += $games_count[$player];
            }

        }

    }

    //                              BEGIN

    global $players;
    $players = array();

    //                              MYSQL
    connect();
    ob_start();

    for ($i = 0; $i <= NUM_PLAYERS; $i++){
        $players&#91;$i&#93; = new player(START_RATING); // Beginners rating
    }

    for ($tour = 1; $tour <= NUM_TOURNAMENTS; $tour++){

        echo '<h3>Tournament '. $tour . '</h3>';
        // Choose 20 participants at random
        if (count($players) > NUM_PARTICIPANTS) {
            $mob = array_keys($players);
            shuffle($mob);
            $participants = array_combine(range(0,NUM_PARTICIPANTS - 1), array_slice($mob, 0, NUM_PARTICIPANTS));
        } elseif (count($players) == NUM_PARTICIPANTS) {
            $participants = array_combine(range(0,NUM_PARTICIPANTS - 1), array_keys($players));
        } else {
            echo 'Too few players'.
            exit;
        }

        // new log every tournament
        $tourlog = array();

        echo '<h4>Tier 0</h4>';
        $participants1 = play_tier($participants, $tourlog);

        // TIER 1
        echo '<h4>Tier 1</h4>';
        $participants2 = play_tier($participants1, $tourlog);

        // TIER 2

        echo '<h4>Tier 2</h4>';
        $participants3 = play_tier($participants2, $tourlog);

        // TIER 3

        echo '<h4>Tier 3</h4>';
        $participants4 = play_tier($participants3, $tourlog);

        // FINALS

        echo '<h4>Finals</h4>';
        $winner = play_tier($participants4, $tourlog);


        echo '<span>Tour #' . $tour . ' games are ended, tourlog has ' . count($tourlog) .' records</span>';

        // RATINGS CALCULATION
        display_performance_rating($tourlog, $participants);

        process_ratings($tourlog);
    }

    // arsort($players;

    echo '<table>';
    echo '<tr><th>Player</th><th>Rating</th><th>Strength</th></tr>';
    foreach ($players as $playerid => $player) {
        echo '<tr><td>' . $playerid . '</td><td>' . $player->rating . '</td><td>' . $player->strength . '</td></tr>';
    }
    echo '</table>';
    ob_end_flush();
?>

Здесь добавлен set_time_limit — время расчёта превысило минуту. Кроме того, я исправил ошибку в вычислениях рейтинга, и изменил способ игры. Раньше победитель определялся бросанием случайной точки в пул из рейтингов игроков. То есть, рейтинги складывались и выбиралось случайное число от 0 до суммы рейтингов. Если число было меньше рейтинга первого игрока, выигрывал он, иначе выигрывал второй игрок.

$points = rand(1, $rating1 + $rating2);
if ($points <= $rating1) { // player 1 won $winner = $player1; $loser = $player2; } else { $winner = $player2; $loser = $player1; } [/sourcecode] Теперь же у каждого игрока есть показатель "реальной силы". Игрок с большей реальной силой всегда побеждал игрока с меньшей (потом это сыграло со мной злую шутку - я объясню почему). Кроме того, добавлена 5% вероятность того что игроки сыграют вничью. Вряд ли это точно соответствует ситуации в Warhammer, это было сделано скорее из интереса. Итак, я запустил симуляцию и увидел довольно неплохой результат - рейтинги игроков довольно точно соответствовали их "реальной силе". Наибольший разброс был среди самых слабых игроков - полагаю, это потому что они рано выбывали на турнирах и у системы было недостаточно данных чтобы сравнить их друг с другом. В реальном мире это решается делением игроков на ступени - например, в лиге для новичков имеют право играть люди с рейтингом ниже 1300. Игроки, чей рейтинг выше, сражаются в своих турнирах и не мешают новичкам. Но был и ещё один интересный результат. Рейтинг игрока с максимальной силой рос непропорционально быстро. Особенно это было заметно когда ничьи ещё не были введены. Через пару дней я всё таки понял в чём дело. Так как этот игрок постоянно выигрывал (не считая 5% ничьих), для системы его реальная сила фактически была бесконечной. На самом деле, если вместо 100 поставить игроку 100 000 - ничего не изменится. В реальной жизни, естественно, у игрока с "реальной силой" 100 есть неплохой шанс проиграть игроку с "силой" 90. О "реальной силе" в приложении к жизни я тут говорю довольно условно, кстати. На игру в реальности влияют множество факторов - моральное и физическое состояние игроков, условия проведения игры, в случае с Warhammer - это ещё и удача. В реальности рейтинг "самого сильного" будет ограничиваться как раз случайными (или закономерными) проигрышами - в системе Эло выигрыш у оппонента ниже рангом не особо прибавляет рейтинга, а проигрыш игроку ниже в рейтинге отнимает немаленькое число очков. Кстати, в первой версии системы была ещё одна небольшая ошибка - рост рейтинга приводил к росту шанса на победу. Полагаю, при достаточно большом числе итераций эта положительная обратная связь привела бы к росту самого сильного игрока, хоть и не такому быстрому - 200 очков рейтинга не сильно повышают реальный шанс выигрыша (при бросании точки), тогда как в оригинальной системе Эло разница в 200 очков означает что игрок с большим рейтингом имеет 75% шанс на победу (как уже упоминалось). В конце концов, когда имплементация была закончена и тесты пройдены, оказалось что система Эло не слишком подходит для ранжирования игроков Warhammer. Во первых, она не поддерживает количественный результат игры (хотя для го такая система вроде бы была разработана). То есть, выигрыш с разницей 100 VP и выигрыш с разницей в 400 VP принесут одинаковое количество очков рейтинга. Но, что ещё хуже, система Эло не приспособлена для командных игр. В шахматах не бывает (насколько я знаю) турниров 2 на 2 или свалок по 8 игроков в стиле "каждый сам за себя" и "2 команды по 4", тогда как в Warhammer 40K это довольно обычный формат для турниров и Мегабитв. В общем, от использования Эло пришлось отказаться. Следующей системой, привлёкшей моё внимание, оказался Microsoft TrueSkill — но это уже совсем другая тема🙂

Добавить комментарий

Заполните поля или щелкните по значку, чтобы оставить свой комментарий:

Логотип WordPress.com

Для комментария используется ваша учётная запись WordPress.com. Выход / Изменить )

Фотография Twitter

Для комментария используется ваша учётная запись Twitter. Выход / Изменить )

Фотография Facebook

Для комментария используется ваша учётная запись Facebook. Выход / Изменить )

Google+ photo

Для комментария используется ваша учётная запись Google+. Выход / Изменить )

Connecting to %s

%d такие блоггеры, как: