ladder_calc.c

打魔兽战网的都知道他是什么

/*
 * Copyright (C) 1999  Rob Crittenden ([e-mail])
 * Copyright (C) 1999,2000  Ross Combs ([e-mail])
 * Copyright (C) 1999,2000  D.Moreaux ([e-mail])
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version 2
 * of the License, or (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
 */
#include "common/setup_before.h"
#include <math.h>
#ifdef HAVE_STRING_H
# include <string.h>
#else
# ifdef HAVE_STRINGS_H
#  include <strings.h>
# endif
#endif
#include "account.h"
#include "account_wrap.h"
#include "common/eventlog.h"
#include "game.h"
#include "common/tag.h"
#include "ladder.h"
#include "ladder_calc.h"
#include "common/xalloc.h"
#include "common/setup_after.h"


static double probability(unsigned int a, unsigned int b) ;
static int coefficient(t_account * account, t_clienttag clienttag, t_ladder_id id);

static double two_player(unsigned int *rating);

static double three_player(unsigned int *rating);

static double four_player(unsigned int *rating);

static double five_player(unsigned int *rating);
static double five_f1(int a, int b, int c, int d, int e) ;
static double five_f2(int a, int b, int c) ;

static double six_player(unsigned int *rating);
static double six_f1(int a, int b, int c, int d, int e, int f) ;
static double six_f2(int a, int b, int c, int d, int e, int f) ;
static double six_f3(int a, int b, int c, int d) ;

static double seven_player(unsigned int *rating);
static double seven_f1(int a, int b, int c, int d, int e, int f, int g) ;
static double seven_f2(int a, int b, int c, int d, int e, int f, int g) ;

static double eight_player(unsigned int *rating);
static double eight_f1(int a, int b, int c, int d, int e, int f, int g) ;
static double eight_f2(int a, int b, int c, int d, int e, int f, int g) ;
static double eight_f3(int a, int b, int c, int d, int e) ;

/*
 * Compute probability of winning using the Elo system
 *
 * The formula is:
 *
 *  D = rating(player a) - rating(player b)
 *
 *                    1
 *  Pwin(D) = ------------------
 *                   -(D / 400)
 *             1 + 10
 */
static double probability(unsigned int a, unsigned int b)
{
    double i, j;
    
    i = (((double)a) - ((double)b)) / 400.0;
    
    j = pow(10.0,-i);
    
    return (1.0 / (1.0+j));
}


/*
 *  This is the coefficient k which is meant to enhance the
 *  effect of the Elo system where more experienced players
 *  will gain fewer points when playing against newbies, and
 *  newbies will gain massive points if they win against an
 *  experienced player. It also helps stabilize a player's
 *  rating after they have played 30 games or so.
 *
 *  K=50 for new players
 *  K=30 for players who have played 30 or more ladder games
 *  K=20 for players who have attained a rating of 2400 or higher
 */
static int coefficient(t_account * account, t_clienttag clienttag, t_ladder_id id)
{
    int const total_ladder_games=account_get_ladder_wins(account,clienttag,id) +
				 account_get_ladder_losses(account,clienttag,id) +
				 account_get_ladder_disconnects(account,clienttag,id);
    
    if (total_ladder_games < 30)
	return 50;
    
    if (account_get_ladder_rating(account,clienttag,id) < 2400)
	return 30;
    
    return 20;
}


/*
 * The Elo system only handles 2 players, these functions extend
 * the calculation to different numbers of players as if they were
 * in a tournament. It turns out the math for this is really ugly,
 * so we have hardcoded the equations for every number of players.
 */
static double two_player(unsigned int *rating)
{
    unsigned int a,b;
    double       ab;
    
    a = rating[0];
    b = rating[1];
    
    ab = probability(a,b);
    
    return ab;
}

static double three_player(unsigned int *rating)
{
    unsigned int a,b,c;
    double       ab,ac,bc,cb;
    
    a = rating[0];
    b = rating[1];
    c = rating[2];
    
    ab = probability(a,b);
    ac = probability(a,c);
    bc = probability(b,c);
    cb = 1.0 - bc;

    return (2*(ab*ac)+(bc*ab)+(cb*ac))/3;
}

static double four_player(unsigned int *rating)
{
    unsigned int a,b,c,d;
    double       ab,ac,ad,bc,bd,cb,cd,db,dc;
    
    a = rating[0];
    b = rating[1];
    c = rating[2];
    d = rating[3];

    
    ab = probability(a,b);
    ac = probability(a,c);
    ad = probability(a,d);
    bc = probability(b,c);
    bd = probability(b,d);
    cd = probability(c,d);
    cb = 1.0 - bc;
    db = 1.0 - bd;
    dc = 1.0 - cd;
    
    return (ab*ac*(cd+bd)+ac*ad*(db+cb)+ab*ad*(dc+bc))/3;
}


/* [Denis MOREAUX <[e-mail]>, 10 Apr 2000]
 *
 *     C D E          A D E   The winner may be in the
 * A B  C E       B C  A E    2 players or the 3 players
 *  A    C         B    A     group. In either case, a
 *    A              A        second player must be choosen
 *                            to be either the one playing
 * against A in the 2-players subtree or being the winner
 * of the 2-player subtree if A is in the 3-players subtree.
 */

static double five_player(unsigned int *rating)
{
    unsigned int a,b,c,d,e;
    
    a = rating[0];
    b = rating[1];
    c = rating[2];
    d = rating[3];
    e = rating[4];
    
    return (five_f1(a,b,c,d,e)+five_f1(a,c,d,e,b)+
            five_f1(a,d,e,b,c)+five_f1(a,e,b,c,d))/30;
}

/* [Denis MOREAUX <[e-mail]>, 10 Apr 2000
 *
 * Two cases to treat : AB-CDE and BC-ADE.
 * in both cases, A win against B.
 * In the first case, A win over the winner of a 3-players game
 * (3 possible winners).
 * In the second case, B win over one of the three other and A is in
 * the 3-players game.
 */

static double five_f1(int a, int b, int c, int d, int e)
{
    double ab,ac,ad,ae,bc,bd,be;

    ab = probability(a,b);
    ac = probability(a,c);
    ad = probability(a,d);
    ae = probability(a,e);
    bc = probability(b,c);
    bd = probability(b,d);
    be = probability(b,e);

    return ab*(ac*five_f2(c,d,e)+ad*five_f2(d,e,c)+ae*five_f2(e,c,d)+
               bc*five_f2(a,d,e)+bd*five_f2(a,c,e)+be*five_f2(a,c,d));
}

static double five_f2(int a, int b, int c)
{
    double       ab,ac,bc,cb;

    ab = probability(a,b);
    ac = probability(a,c);
    bc = probability(b,c);
    cb = 1.0 - bc;

    return (2*(ab*ac)+bc*ab+cb*ac);
}


static double six_player(unsigned int *rating)
{
    unsigned int a,b,c,d,e,f;
    
    a = rating[0];
    b = rating[1];
    c = rating[2];
    d = rating[3];
    e = rating[4];
    f = rating[5];

/* A B C D
 *  A   C    E F
 *    A       E
 *        A
 */

    return (six_f1(a,b,c,d,e,f)+  /* A is in group of 4 */
            six_f1(a,b,c,e,d,f)+
            six_f1(a,b,e,d,c,f)+
            six_f1(a,e,c,d,b,f)+
            six_f1(a,b,c,f,d,e)+
            six_f1(a,b,f,d,c,e)+
            six_f1(a,f,c,d,b,e)+
            six_f1(a,e,f,b,c,d)+
            six_f1(a,e,f,c,b,d)+
            six_f1(a,e,f,d,b,c)+
            six_f2(a,b,c,d,e,f)+   /* A is in group of 2 */
            six_f2(a,c,b,d,e,f)+
            six_f2(a,d,b,c,e,f)+
            six_f2(a,e,b,c,d,f)+
            six_f2(a,f,b,c,d,e))/45;
}


/* ABCD = group of 4, EF = group of 2, A must win */
/* D.Moreaux, 10 Apr 2000: changed double to int for the parameters */

static double six_f1(int a, int b, int c, int d, int e, int f)
{
    double ab,ac,ad,bc,bd,cb,cd,db,dc,ef,fe,ae,af;
    
    ab = probability(a,b);
    ac = probability(a,c);
    ad = probability(a,d);
    ae = probability(a,e);
    af = probability(a,f);
    bc = probability(b,c);
    bd = probability(b,d);
    cd = probability(c,d);
    ef = probability(e,f);
    cb = 1.0 - bc;
    db = 1.0 - bd;
    dc = 1.0 - cd;
    fe = 1.0 - ef;
    return (ab*ac*(cd+bd)+ac*ad*(db+cb)+ab*ad*(dc+bc))*(ef*ae+fe*af);
}


/* AB is group of 2, CDEF is group of 4, A must win */

static double six_f2(int a, int b, int c, int d, int e, int f)
{
    double ab,ac,ad,ae,af;
    
    ab = probability(a,b);
    ac = probability(a,c);
    ad = probability(a,d);
    ae = probability(a,e);
    af = probability(a,f);
    
    return (six_f3(c,d,e,f)*ab*ac+
            six_f3(d,c,e,f)*ab*ad+
            six_f3(e,c,d,f)*ab*ae+
            six_f3(f,c,d,e)*ab*af);