/* * Copyright (C) 1999  Rob Crittenden (rcrit@greyoak.com) * Copyright (C) 1999,2000  Ross Combs (rocombs@cs.nmsu.edu) * Copyright (C) 1999,2000  D.Moreaux (vapula@linuxbe.org) * * 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 <vapula@linuxbe.org>, 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 <vapula@linuxbe.org>, 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);