Multiplayer Forums

package com.noblemaster.lib.data.score.control;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

import com.noblemaster.lib.base.type.list.DoubleList;
import com.noblemaster.lib.data.score.model.RankingList;
import com.noblemaster.lib.data.score.model.Rating;
import com.noblemaster.lib.data.score.model.RatingList;
import com.noblemaster.lib.role.user.model.Account;
import java.util.Random;
import static java.lang.Math.*;

/**
* Calculates rating updates. Formulas from "Kran-impire".
* Lambert`s W function code from wikipedia.org
*
* @author "Kran-impire" and Christoph Aschwanden
* @since May 18, 2010
* @access Public
*/
public final class RatingUtil {

    /** The initial rating. */
    public static final double INITIAL_RATING = 900;
    /** The initial volatility. */
    public static final double INITIAL_VOLATILITY = 500;
    /** The rating scale. */
    public static final double SCALE = 364;

    /**
     * The constructor is private to prevent instantiation.
     */
    private RatingUtil() {
        // not used
    }

    /**
     * Creates a new initialized rating.
     *
     * @param account  The account.
     * @return  The rating.
     */
    public static Rating create(Account account) {
        Rating rating = new Rating();
        rating.setAccount(account);
        rating.setRating(INITIAL_RATING);
        rating.setVolatility(INITIAL_VOLATILITY);
        rating.setCompetitions(0);
        return rating;
    }

    /**
     * Returns the reliability of a rating given the rating`s volatility.
     *
     * @param volatility  The volatility.
     * @return  The reliability of a rating of the given volatility.
     */
    private static double g(double volatility) {
        return 1 / sqrt(1 + 3 / (PI * PI) * (volatility * volatility) / (SCALE * SCALE));
    }

     /**
     * Returns the expected chance of one player defeating another.
     *
     * @param strength  The first player`s strength.
     * @param strengthOther  The other player`s strength.
     * @param volatility  The volatility.
     * @return  The expected score of first player if parameter volatility is
      * the volatility of the second player, or the expected win percentage,
      * if parameter volatility is the square root of the sum of the
      * squared volatilities of both players.
     */
    private static double e(double strength, double strengthOther, double volatility) {
        return 1 / (1 + exp((strengthOther - strength) * g(volatility) / SCALE));
    }

     /**
     * Converts a rating into strength.
     *
     * @param rating  The rating.
     * @return  The strength of the rating.
     */
    private static double convertRatingToStrength(double rating) {
        return Math.pow(9, rating / SCALE) * rating;
    }

     /**
     * Converts a strength into rating.
     *
     * @param strength  The strenght.
     * @return  The rating correspondent to the strength.
     */
    private static double convertStrengthToRating(double strength) {
        return ((SCALE / 2) / Math.log(3)) * lambertW(strength * Math.log(3) / (SCALE / 2), 1E-12, 100);
    }

     /**
     * Returns a estimative of the lambert`s W function.
     *
     * @param x lambert`s W function input.
     * @return  estimative of lambert`s W function output.
     */
    private static double estimateLambertW(double x) {
        if (x == 0) {
            return 0;
        }
        if (x == Math.E) {
            return 1;
        }
        if (x <= 500.0) {
            double lx1 = Math.log1p(x);
            return 0.665 * (1 + 0.0195 * lx1) * lx1 + 0.04;
        }
        double lnx = Math.log(x);
        return Math.log(x - 4.0) - (1.0 - 1.0 / lnx) * Math.log(lnx);
    }

     /**
     * Returns a the output of the lambert`s W function.
     *
     * @param x lambert`s W function input.
     * @return  the lambert`s W function output.
     */
    private static double lambertW(double x, double prec, int maxiters) {
        double w = x >= 0 ? estimateLambertW(x) : 0;
        for (int i = 0; i < maxiters; ++i) {
            double expW = Math.exp(w);
            double we = w * expW;
            double w1e = we + expW;
            if (prec > Math.abs((x - we) / w1e)) {
                return w;
            }
            w -= (we - x) / (w1e - (w + 2.0) * (we - x) / (2 * w + 2));
        }
        throw new RuntimeException(String.format("W doesn't converge fast enough for x = %f", x));
    }

    /**
     * Returns the win probability of two ratings.
     *
     * @param rating  The rating to return the win probability compared to the other rating.
     * @param other  The other rating.
     * @return  The win probability for rating.
     */
    public static double getWinProbability(Rating rating, Rating other) {
        double rv = rating.getVolatility();
        double ov = other.getVolatility();
        double rs = convertRatingToStrength(rating.getRating()) * exp(rv/SCALE);
        double os = convertRatingToStrength(other.getRating()) * exp(ov/SCALE);
        return e(log(rs / sqrt(INITIAL_RATING))/Math.log(9) * SCALE,
                log(os / sqrt(INITIAL_RATING))/Math.log(9) * SCALE,
                sqrt(rv * rv + ov * ov));
    }

    /**
     * Returns the win probability compared to everybody.
     *
     * @param rating  The rating to return the win probability compared to the other ratings.
     * @param others  The other ratings.
     * @return  The win probability for rating.
     */
    public static double getWinProbability(Rating rating, RatingList others) {
        double st = 0;
        for (Rating x : others) {
            st += getWinProbability(x, rating) / (1-getWinProbability(x, rating));
        }
        return 1 / st;
    }

    /**
     * Returns the expected rank.
     *
     * @param rating  The rating to return the expected rank compared to the other ratings.
     * @param others  The other ratings.
     * @return  The expected rank for rating.
     */
    public static double getExpectedRank(Rating rating, RatingList others) {
        double expectedRankSum = 0;
        int size = others.size();
        for (int i = 0; i < size; i++) {
            double rs,os;
            rs = convertRatingToStrength(rating.getRating())
                * exp(rating.getVolatility()/SCALE);
            os = convertRatingToStrength(others.get(i).getRating())
                * exp(others.get(i).getVolatility()/SCALE);
            double rr = log(rs)/log(9)*SCALE;
            double or = log(os)/log(9)*SCALE;
            expectedRankSum += e(or, rr, others.get(i).getVolatility());
        }
        return expectedRankSum + 0.5;
    }

    /**
     * Returns the new ratings given the inputed rankings. Please note that the inputs do not need to match.
     * Ratings are instantiated automatically if missing.
     *
     * @param rankings  The rankings.
     * @param ratings  The old ratings to calculated the new ratings off.
     * @return  The new ratings.
     */
    public static RatingList getNewRatings(RankingList rankings, RatingList ratings) {
        int size = rankings.size();

        // place into sortable array
        List<Object[]> ranks = new ArrayList<Object[]>();
        for (int i = 0; i < size; i++) {
            Object[] ranking = new Object[2];
            ranking[0] = new Long(rankings.get(i).getRank());
            Account account = rankings.get(i).getAccount();
            Rating rating = null;
            for (int k = 0; k < ratings.size(); k++) {
                if (account.equals(ratings.get(k).getAccount())) {
                    rating = ratings.get(k);
                }
            }
            if (rating == null) {
                rating = create(account);
            }
            ranking[1] = rating;
            ranks.add(ranking);
        }

        // sort rankings
        Collections.sort(ranks, new Comparator() {

            public int compare(Object object0, Object object1) {
                long rank0 = ((Long) ((Object[]) object0)[0]).longValue();
                long rank1 = ((Long) ((Object[]) object1)[0]).longValue();
                return (rank0 < rank1 ? -1 : (rank0 == rank1 ? 0 : 1));
            }
        });

        // prepare the ranks
        DoubleList newRanks = new DoubleList();
        for (int i = 0; i < size; i++) {
            long rank = ((Long) ((Object[]) ranks.get(i))[0]).longValue();
            long numRanks = 0;
            double rankSum = 0;
            for (int k = 0; k < size; k++) {
                if (((Long) ((Object[]) ranks.get(k))[0]).longValue() == rank) {
                    numRanks++;
                    rankSum += k + 1;
                }
            }
            newRanks.add(new Double(rankSum / numRanks));
        }

        // prepare the ratings
        RatingList newRatings = new RatingList();
        for (int i = 0; i < size; i++) {
            newRatings.add((Rating) ((Object[]) ranks.get(i))[1]);
        }

        // and calculate new ratings
        return getNewRatings(newRanks, newRatings);
    }

    /**
     * Returns the new rating for an inputed rating based on other ratings.
     *
     * @param rating  The rating to return the new rating for.
     * @param actualRank  The actual rank. Rank is the actual rank of the player in the
     *     competition based on score (1 for first place, numPlayers forlast). If the
     *     player tied with another player, the rank is the average of the positions
     *     covered by the tied players.
     * @param others  The other ratings.
     * @return  The new rating.
     */
    private static Rating getNewRating(Rating rating, double actualRank, RatingList others) {
        Rating newRating = new Rating();
        newRating.setId(rating.getId());
        newRating.setAccount(rating.getAccount());

        // increase competitions
        newRating.setCompetitions(rating.getCompetitions() + 1);

        // calculate rating and volatility
        double n = others.size() - 1; // number of opponents
        double a = 0;
        double b = 0;
        double rs = convertRatingToStrength(rating.getRating())
                * exp(rating.getVolatility()/SCALE);
        for (Rating x : others) {
            double xs = convertRatingToStrength(x.getRating())
                    * exp(x.getVolatility()/SCALE);
            double e = e(log(rs)/log(9),
                    log(xs)/log(9), x.getVolatility());

            a += g(x.getVolatility()) * g(x.getVolatility()) * e * (1 - e);
            b += g(x.getVolatility());
        }
        a -= g(rating.getVolatility()) * g(rating.getVolatility()) / 4;
        b -= g(rating.getVolatility());
        double expected = getExpectedRank(rating, others);

        double d2;
        if(a==0){
            d2 = Double.POSITIVE_INFINITY;
        }
        else{
            d2 = 1/(a / (SCALE * SCALE));
        }
        double k;
        if (b == 0) {
            k = 0;
        } else {
            k = pow(1 + 1 / b, b) - 1;
            k /= n;
        }

        double f;
        if (b == 0) {
            f = 0;
        } else {
            double btt, wrs;
            btt = actualRank - 1;
            wrs = others.size() - actualRank;
            f = 2 - pow(2,-btt) - pow(2,-wrs);
            f /= n;
        }

        double rd2 = rating.getVolatility() * rating.getVolatility();
        double c = 1/((1/rd2 + 1/d2)*SCALE);
        double v = sqrt(1 / (1 / pow(rating.getVolatility(),2) + f / d2));
        v = sqrt(v*v + 0 * f);
        rs /= exp(v/SCALE);

        // sets the new volatility
        newRating.setVolatility(v);
        double update = (k * (expected - actualRank) * b * c + rating.getVolatility() - v)/SCALE;

        // sets the new rating
        newRating.setRating(convertStrengthToRating(rs*exp(update)));

        // and return the new rating
        return newRating;
    }

    /**
     * Returns the new ratings for the inputted data.
     *
     * @param actualRanks  The actual ranks. Rank is the actual rank of the player in the
     *              competition based on score (1 for first place, NumPlayers forlast). If the
     *              player tied with another player, the rank is the average of the positions
     *              covered by the tied players.
     * @param ratings  The ratings which match the inputed ranks.
     * @return  The new ratings in the same order as the inputed ratings.
     */
    private static RatingList getNewRatings(DoubleList actualRanks, RatingList ratings) {
        RatingList newRatings = new RatingList();
        for (int i = 0; i < actualRanks.size(); i++) {
            double actualRank = actualRanks.get(i).doubleValue();
            Rating rating = ratings.get(i);
            Rating newRating = getNewRating(rating, actualRank, ratings);
            newRatings.add(newRating);
        }
        return newRatings;
    }
}

    public static void main(String... args) {
        System.out.println("Kran Rating System");
        System.out.println("Starting test...");
        System.out.println("400,000 Players and 10,000,000 Games");
        System.out.println("5 Players per game");
        System.out.println("Initial Rating: 900");
        System.out.println("Initial Volatility: 500");
        System.out.println("Each Player`s True Strength will be drawn according to the gaussian \"bell\" curve");
        System.out.println("Setting up players...");
        RatingList playerList = new RatingList();
        Random generator = new Random();
        int playerNumber = 400000;
        int gameNumber = 10000000;
        double[] trueStrengthList = new double[playerNumber];
        for(int a = 0 ; a < playerNumber ; a++){
            Rating x = new Rating();
            x.setRating(900);
            x.setVolatility(500);
            double xStrength = generator.nextGaussian();
            trueStrengthList[a] = xStrength;
            playerList.add(x);
        }
        System.out.println("Simulating games...");
        for(int a = 0 ; a < gameNumber ; a++){
            if(a%1000 == 0){
                System.out.println(100*a/(double)gameNumber);
            }
            RatingList gamePlayers = new RatingList();
            ArrayList<Integer> intList = new ArrayList<Integer>();
            double[] gamePlayersStrength = new double[playerNumber];
            for(int b = 0 ; b < 5 ; b++){
                int i = generator.nextInt(playerNumber);
                while(intList.contains(i)){
                    i = generator.nextInt(playerNumber);
                }
                gamePlayers.add(playerList.get(i));
                gamePlayersStrength[b] = trueStrengthList[i];
                intList.add(i);
            }
            double[] performed = new double[5];
            for(int b = 0 ; b < 5 ; b++){
                double doubleRandom = generator.nextDouble();
                double logRandom = -log(1/doubleRandom-1)/log(3)/sqrt(2);
                double perfx = pow(9,gamePlayersStrength[b]) * pow(9, logRandom);
                performed[b] = perfx;
            }
            int[] order = new int[5];
            order[0] = 0;
            order[1] = 1;
            order[2] = 2;
            order[3] = 3;
            order[4] = 4;
            for(int b = 0 ; b < 5 ; b++){
                for(int c = 0 ; c < 4 ; c++){
                    double perfx = performed[c];
                    double perfy = performed[c+1];
                    if(perfy > perfx){
                        int dir = order[c];
                        order[c] = order[c+1];
                        order[c+1] = dir;
                        performed[c] = perfy;
                        performed[c+1] = perfx;
                    }
                }
            }
            double ranksArray[] = new double[5];
            ranksArray[order[0]]=1.0;
            ranksArray[order[1]]=2.0;
            ranksArray[order[2]]=3.0;
            ranksArray[order[3]]=4.0;
            ranksArray[order[4]]=5.0;
            DoubleList ranks = new DoubleList();
            for(double x : ranksArray){
                ranks.add(x);
            }
            RatingList newRatings = getNewRatings(ranks, gamePlayers);
            for(int b = 0 ; b < 5 ; b++){
                gamePlayers.get(b).setRating(newRatings.get(b).getRating());
                gamePlayers.get(b).setVolatility(newRatings.get(b).getVolatility());
            }
        }
        double high, low;
        high = 0;
        low = 3000;
        for(Rating x : playerList){
            double r = x.getRating();
            if(r > high){
                high = r;
            }
            if(r < low){
                low = r;
            }
        }
        System.out.println("Highest rating: " + high);
        System.out.println("Lowest rating: " + low);
        int level0,level1,level2,level3,level4,level5,level6;
        level0 = 0;
        level1 = 0;
        level2 = 0;
        level3 = 0;
        level4 = 0;
        level5 = 0;
        level6 = 0;
        for(Rating x : playerList){
            double r = x.getRating();
            if(r < 800.0){
                level0++;
            }
            else if(r < 1100.0){
                level1++;
            }
            else if(r < 1400.0){
                level2++;
            }
            else if(r < 1700.0){
                level3++;
            }
            else if(r < 2100.0){
                level4++;
            }
            else if(r < 2500.0){
                level5++;
            }
            else{
                level6++;
            }
        }
        System.out.println("Rating Distribution:");
        System.out.println("Level0 (0-800) = " + level0);
        System.out.println("Level1 (800-1100) = " + level1);
        System.out.println("Level2 (1100-1400) = " + level2);
        System.out.println("Level3 (1400-1700) = " + level3);
        System.out.println("Level4 (1700-2100) = " + level4);
        System.out.println("Level5 (2100-2500) = " + level5);
        System.out.println("Level6 (2500+) = " + level6);
        System.out.println("Finished");
    }

Kran Rating System 1.0
Starting test...
400,000 Players and 10,000,000 Games
5 Players games
Initial Rating: 900
Initial Volatility: 500
Each Player`s True Strength will be drawn according to the gaussian "bell" curve
Setting up players...
Simulating games...
Highest rating: 2581.7428137574093
Lowest rating: 165.62245468241463
Rating Distribution:
Level0 (0-800) = 36730
Level1 (800-1100) = 95178
Level2 (1100-1400) = 133732
Level3 (1400-1700) = 93228
Level4 (1700-2100) = 37686
Level5 (2100-2500) = 3430
Level6 (2500+) = 16
Finished
CONSTRUÍDO COM SUCESSO (tempo total: 159 minutos 29 segundos)