DEVTOME.COM HOSTING COSTS HAVE BEGUN TO EXCEED 115$ MONTHLY. THE ADMINISTRATION IS NO LONGER ABLE TO HANDLE THE COST WITHOUT ASSISTANCE DUE TO THE RISING COST. THIS HAS BEEN OCCURRING FOR ALMOST A YEAR, BUT WE HAVE BEEN HANDLING IT FROM OUR OWN POCKETS. HOWEVER, WITH LITERALLY NO DONATIONS FOR THE PAST 2+ YEARS IT HAS DEPLETED THE BUDGET IN SHORT ORDER WITH THE INCREASE IN ACTIVITY ON THE SITE IN THE PAST 6 MONTHS. OUR CPU USAGE HAS BECOME TOO HIGH TO REMAIN ON A REASONABLE COSTING PLAN THAT WE COULD MAINTAIN. IF YOU WOULD LIKE TO SUPPORT THE DEVTOME PROJECT AND KEEP THE SITE UP/ALIVE PLEASE DONATE (EVEN IF ITS A SATOSHI) TO OUR DEVCOIN 1M4PCuMXvpWX6LHPkBEf3LJ2z1boZv4EQa OR OUR BTC WALLET 16eqEcqfw4zHUh2znvMcmRzGVwCn7CJLxR TO ALLOW US TO AFFORD THE HOSTING.

THE DEVCOIN AND DEVTOME PROJECTS ARE BOTH VERY IMPORTANT TO THE COMMUNITY. PLEASE CONTRIBUTE TO ITS FURTHER SUCCESS FOR ANOTHER 5 OR MORE YEARS!

Odds of Winning a Knockout Tournament

In this article I am providing the C source code for a utility program I wrote many years ago (I think it would have been about 1992) to work out the odds of each competitor winning each round of a knockout tournament and thus eventually the whole tournament. The idea is to try and spot betting opportunities where you determine that a players true odds are better than the odds being offered by the bookmakers. It is also a way of determining how easy the players draw in the tournament could turn out to be.

I developed the program with snooker in mind, but the program can be used for any knockout tournament. It would work well for a tennis tournament for example.

The program operates based on rankings information for each player. In fact two sets of rankings can be provided (eg this years rankings and last years rankings). More weight is given to the recent ranking information (in fact twice as much weight is given to the recent rankings but this could be changed by a small tweak to the code). The lines of code in question are the following


      /* if last years results are available, treat this years as
           twice as significant */

       if (lastyear)
       {
           player[loop].ranking *= 2 ;
           player[loop].ranking += lastyear ;
       }

The value 2 is currently hardwired in the code, but it would be simple enough to provide it as an argument to the program (or you could just change to a value which matches your view of the relative importance of the two sets of rankings). So you could set to 1.5 for example to give last years rankings greater weight.

I should mention at this point that this program takes no account of past history between any two players. When you are watching the snooker on TV you will often be given information about how many times the two players have met previously, and how many times each has won. The program in its current form does not use information of this type, and operates solely on the ranking information.

Input File

The input to the program is a file which you need to construct containing the players taking part in the tournament specified in the order of the draw. The file may appear as follows for an imaginary snooker tournament at the point of the last 32

 
Mark Selby:79740:83640
Rory Mcleod:30900:32520
Ding Junhui:57900:59920
Judd Trump:76720:78200
Nigel Bond:30695:32825
Barry Howkins:58880:63085
Stuart Bingham:62940:61800
Shaun Murphy:68220:68600
Marco Fu:49790:57110
John Higgins:56355:64575
Mark Allen:62460:61220
Ricky Walden:59765:61710
Mark Davis:54280:56080
Jamie Cope:34145:37165
Robert Milkins:48580:57005
Joe Perry:44580:50300
Ali Carter:52895:54295
Graeme Dott:54900:55100
Neil Robertson:79460:90160
Mark Williams:53260:54520
Matthew Stevens:53660:58200
Michael Holt:43155:43425
Ryan Day:39575:42715
Mark King:41665:44325
Andrew Higginson:44055:45315
Marcus Campbell:42045:42025
Ronnie O'Sullivan:46360:45640
Peter Ebdon:40135:41270
Xiao Guodong:34185:37680
Tom Ford:43715:45235
Stephen Maguire:66940:66480
Dave Harold:29285:28835 

So Mark Selby will be playing Rory McLeod in the first round, Ding Junhui will be playing Judd Trump, and so on. The first 16 names are the top half of the draw and the second 16 names are the bottom half of the draw. To the right of the players name is the most recent ranking information, and to the right of that older ranking information. Fields are separated by the : character. The third column (last years rankings) is optional.

Of course there is no requirement to slavishly follow the published ranking information when setting up this file. Ronnie o'Sullivan is the current world champion as I write this article, and has been world champion for the last 2 seasons, but his ranking does not reflect this as he plays in relatively few tournaments. I would therefore be tempted to increase his ranking figures. It has to be said that Ronnie is something of a special case. For most players you are likely to find that their ranking is a very good indicator of current form.

Running the program

When the program is run it works out all possible combinations of how the tournament might progress, along with the probability of each scenario. It adds up the probabilities for each possible scenario for each player, to come up with a figure which is the overall chance of the player winning at each round in the tournament

Given the input file I have used as an example above, running the program in the simplest way gives the following output. We are using “method” 1 here. I will explain what that means as we go along


% ./ko koFile 1
Mark Selby                    72.05     39.02   22.55   13.52   8.14
Rory Mcleod                   27.95     8.81    3.08    1.13    0.42
Ding Junhui                   43.14     20.88   10.41   5.41    2.84
Judd Trump                    56.86     31.28   17.71   10.41   6.15
Nigel Bond                    34.25     11.10   3.51    1.29    0.48
Barry Howkins                 65.75     31.51   14.73   7.76    4.12
Stuart Bingham                47.79     26.90   12.82   6.88    3.71
Shaun Murphy                  52.21     30.49   15.19   8.48    4.76
Marco Fu                      46.92     21.60   11.23   4.97    2.46
John Higgins                  53.08     26.07   14.35   6.79    3.57
Mark Allen                    50.67     26.68   15.01   7.28    3.91
Ricky Walden                  49.33     25.65   14.26   6.82    3.62
Mark Davis                    60.96     32.20   15.57   7.08    3.60
Jamie Cope                    39.04     16.31   6.12    2.14    0.85
Robert Milkins                52.50     27.65   12.92   5.67    2.79
Joe Perry                     47.50     23.84   10.54   4.37    2.04
Ali Carter                    49.26     21.35   11.47   6.09    2.84
Graeme Dott                   50.74     22.36   12.18   6.56    3.10
Neil Robertson                60.73     36.75   23.64   15.06   8.65
Mark Williams                 39.27     19.54   10.53   5.61    2.62
Matthew Stevens               56.06     31.96   14.90   8.04    3.81
Michael Holt                  43.94     22.40   9.12    4.37    1.81
Ryan Day                      48.84     22.00   8.63    4.01    1.60
Mark King                     51.16     23.64   9.53    4.53    1.86
Andrew Higginson              51.41     26.02   12.50   5.54    2.33
Marcus Campbell               48.59     23.91   11.16   4.79    1.95
Ronnie O'Sullivan             53.24     27.47   13.44   6.08    2.61
Peter Ebdon                   46.76     22.61   10.35   4.36    1.74
Xiao Guodong                  44.43     18.10   8.13    3.16    1.16
Tom Ford                      55.57     25.59   12.92   5.71    2.40
Stephen Maguire               69.63     43.51   26.37   14.32   7.46
Dave Harold                   30.37     12.80   5.14    1.77    0.57 

We can see that Mark Selby has a 72.05% chance of beating Rory Mcleod in the first round (correspondingly Rory Mcleod has a 27.95% chance of getting through the first round). Then, in the second, you see Mark Selby’s chance of getting through is 39.02%. This corresponds to his 72.05% chance of getting through the first round times his chance of beating either Ding Junhui (who he has a 43.14% chance of playing) or Judd Trump (who he has a 56.86 of playing). The program works out the overall chance of each player winning at each round based on the sum of the chances against each possible opponent.

In the first round the opponent is known, in the second round the opponent may be one of 2 players, one of 4 players in the 3rd round, one of 8 players in the 4th round and one of 16 players in the final round. All the probabilities of every possible combination are added to give the overall chance at each round.

If the program is run with the following options (method 2 in the third argument) we get a slightly different result


% ./ko koFile 2
Mark Selby                    86.92     49.77   31.27   21.24   13.56
Rory Mcleod                   13.08     2.25    0.47    0.12    0.03
Ding Junhui                   36.53     14.60   6.88    3.63    1.77
Judd Trump                    63.47     33.37   20.21   13.30   8.21
Nigel Bond                    21.35     3.98    0.62    0.15    0.03
Barry Howkins                 78.65     35.99   14.27   7.72    3.88
Stuart Bingham                45.59     26.37   10.91   6.11    3.17
Shaun Murphy                  54.41     33.66   15.36   9.25    5.19
Marco Fu                      43.86     18.47   9.67    3.45    1.50
John Higgins                  56.14     27.07   15.80   6.53    3.22
Mark Allen                    51.33     28.29   17.17   7.50    3.87
Ricky Walden                  48.67     26.18   15.56   6.60    3.32
Mark Davis                    70.91     39.36   18.29   6.93    3.18
Jamie Cope                    29.09     9.86    2.60    0.53    0.14
Robert Milkins                55.00     29.12   12.59   4.40    1.88
Joe Perry                     45.00     21.66   8.32    2.55    0.97
Ali Carter                    48.52     17.11   9.64    4.97    2.00
Graeme Dott                   51.48     18.83   10.88   5.76    2.40
Neil Robertson                70.52     49.46   37.34   26.57   16.33
Mark Williams                 29.48     14.60   8.27    4.28    1.74
Matthew Stevens               61.94     39.47   16.16   8.58    3.59
Michael Holt                  38.06     19.76   5.98    2.49    0.77
Ryan Day                      47.68     18.89   5.25    2.04    0.58
Mark King                     52.32     21.88   6.48    2.65    0.80
Andrew Higginson              52.81     26.94   10.93   3.90    1.25
Marcus Campbell               47.19     22.74   8.66    2.88    0.86
Ronnie O'Sullivan             56.44     29.99   12.66   4.71    1.59
Peter Ebdon                   43.56     20.33   7.42    2.35    0.66
Xiao Guodong                  38.99     10.88   4.32    1.14    0.26
Tom Ford                      61.01     22.43   11.38   4.03    1.28
Stephen Maguire               84.01     61.22   42.93   23.32   11.91
Dave Harold                   15.99     5.47    1.69    0.34    0.06 

Method 1 and Method 2

The two examples given so far show the program calculations when each of two different “methods” is specified to be used. What we are doing here with the methods is changing the way we calculate the winning chances based on the rankings. You can see that with Method 2 Mark Selby is now far more likely to get through his first round match against Rory McLeod – he now has an 86.92% chance whereas he had only 72.05% chance with method 1. This is because we use the square of the ranking in the calculation in Method 2.

If Mark Selby has ranking A and Rory McLeod has ranking B, then with Method 1 the probability of winning is assessed as


Mark Selby chance = A / (A+ B)
Rory McLeod chance = B / (A + B)

With method 2 we change the calculation as follows


Mark Selby chance = A^2 / (A^2 + B^2)
Rory McLeod chance = B ^2 / (A^2 + B^2)

So to illustrate the effect, using small numbers for the ranking, if we say Mark Selby has a ranking of 10 and Rory McLeod a ranking of 7, then with Method 1 we get


Mark Selby chance = 10 / (10 + 7) = 58.82%
Rory McLeod chance = 7 / (10 + 7) = 41.18%

Using Method 2 we have


Mark Selby chance = (10 * 10) / ( (10 * 10) + (7 * 7)) = 100 / 149 = 67.11%
Rory McLeod chance = (7 * 7) / ( (10 * 10) + (7 * 7)) = 49 / 149 = 32.89%

The 2 methods are encapsulated in the function “probability” which you will see in the full source code (last function at the end of the code) which is at the end of this article.


   if (method == 1)
   {
       prob = (double) player[p1].ranking / ((double) player[p1].ranking + (double) player[p2].ranking) ;
   }
   else if (method == 2)
   {
       double p1sq, p2sq ;
       p1sq = (double) player[p1].ranking ;
       p1sq = p1sq * p1sq ;
       p2sq = (double) player[p2].ranking ;
       p2sq = p2sq * p2sq ;
       prob = p1sq / (p1sq + p2sq) ;
   } 

You may very well want to develop your own “method” for assessing likelihood of 1 player beating another based on their ranking. If you want to do so, it can be easily slotted into the probability function. You may also want to develop different methods for use with different sports. You may consider the rankings to be a stronger indication of what is likely to happen in snooker than in tennis for example.

HTML output

At this point I would also like to mention there is an html output option from the program. If the program is run as


./ko –html koFile 2 

Then HTML output is produced. This could be useful if you are integrating the program into a web page. The following screenshot shows the output in this case

kohtml.jpg

Players that have lost

As the tournament progresses the results of various matches will be decided. The losing players now have a 0% chance of winning the tournament (obviously). This information can be fed into the tool simply by changing the first name to “Lost” – note this is case sensitive (“lost” would not work). The tool will adjust the other players chances accordingly, giving the player that has already lost no chance whatsoever.

Please note that it is NOT necessary to wait for a whole round to be completed for this to be done. Any results can be plugged in at any time and the tool rerun. Let’s see what happens if the first match played is the Ding Junhui vs Judd Trump match and Ding Junhui wins. I am going to use Method 1 for this example

The input file is changed as follows


Mark Selby:79740:83640
Rory Mcleod:30900:32520
Ding Junhui:57900:59920
Lost Trump:76720:78200
Nigel Bond:30695:32825
Barry Hawkins:58880:63085
Stuart Bingham:62940:61800
Shaun Murphy:68220:68600
Marco Fu:49790:57110
John Higgins:56355:64575
Mark Allen:62460:61220
Ricky Walden:59765:61710
Mark Davis:54280:56080
Jamie Cope:34145:37165
Robert Milkins:48580:57005
Joe Perry:44580:50300
Ali Carter:52895:54295
Graeme Dott:54900:55100
Neil Robertson:79460:90160
Mark Williams:53260:54520
Matthew Stevens:53660:58200
Michael Holt:43155:43425
Ryan Day:39575:42715
Mark King:41665:44325
Andrew Higginson:44055:45315
Marcus Campbell:42045:42025
Ronnie O'Sullivan:46360:45640
Peter Ebdon:40135:41270
Xiao Guodong:34185:37680
Tom Ford:43715:45235
Stephen Maguire:66940:66480
Dave Harold:29285:28835 

The results now look like this


% ./ko koFile 1
Mark Selby                    72.05     41.82   24.17   14.49   8.73
Rory Mcleod                   27.95     9.76    3.41    1.26    0.47
Ding Junhui                   100.00    48.42   24.13   12.55   6.57
Lost Trump                    0.00      0.00    0.00    0.00    0.00
Nigel Bond                    34.25     11.10   3.71    1.37    0.51
Barry Hawkins                 65.75     31.51   15.38   8.11    4.30
Stuart Bingham                47.79     26.90   13.38   7.17    3.87
Shaun Murphy                  52.21     30.49   15.82   8.83    4.96
Marco Fu                      46.92     21.60   11.23   5.10    2.53
John Higgins                  53.08     26.07   14.35   6.95    3.65
Mark Allen                    50.67     26.68   15.01   7.45    4.01
Ricky Walden                  49.33     25.65   14.26   6.98    3.71
Mark Davis                    60.96     32.20   15.57   7.25    3.68
Jamie Cope                    39.04     16.31   6.12    2.20    0.88
Robert Milkins                52.50     27.65   12.92   5.81    2.86
Joe Perry                     47.50     23.84   10.54   4.49    2.10
Ali Carter                    49.26     21.35   11.47   6.09    2.88
Graeme Dott                   50.74     22.36   12.18   6.56    3.14
Neil Robertson                60.73     36.75   23.64   15.06   8.75
Mark Williams                 39.27     19.54   10.53   5.61    2.66
Matthew Stevens               56.06     31.96   14.90   8.04    3.86
Michael Holt                  43.94     22.40   9.12    4.37    1.84
Ryan Day                      48.84     22.00   8.63    4.01    1.63
Mark King                     51.16     23.64   9.53    4.53    1.89
Andrew Higginson              51.41     26.02   12.50   5.54    2.37
Marcus Campbell               48.59     23.91   11.16   4.79    1.98
Ronnie O'Sullivan             53.24     27.47   13.44   6.08    2.65
Peter Ebdon                   46.76     22.61   10.35   4.36    1.76
Xiao Guodong                  44.43     18.10   8.13    3.16    1.18
Tom Ford                      55.57     25.59   12.92   5.71    2.43
Stephen Maguire               69.63     43.51   26.37   14.32   7.56
Dave Harold                   30.37     12.80   5.14    1.77    0.58

Obviously Ding has done himself a favour by winning the first round, and his overall chances of winning have now gone up to 6.57% (from 2.84% previously). But also notice that Mark Selby has benefitted. This is because the player he could have most expected to meet in the 2cd round (Judd Trump) is no longer in the tournament. MarkSelby now has a 41.82% chance of getting through the 2cd round (up from 39.02%) and an 8.73% chance (up from 8.14%) overall.

Also note that this first round match in the top half of the draw can have no effect in the bottom half of the draw until the final. If you look for example at the odds of Stephen Maguire winning you will see that his odds at each round of the tournament are unchanged until the final where they have gone up from 7.46% to 7.56%. This reflects the fact that a player with a good ranking has gone out of the tournament from the top half of the draw. The magnitude of the effect is small at only 0.1% (given our calculation method - method 1). This is part of the point of the program - to quantify the effect results have on the odds of another player in a different part of the draw winning. You can imagine the TV commentary - “Stephen Maguire must be feeling good about the fact that Judd Trump has been knocked out in the first round, it gives him a great chance in the tournament.” But our job with this tool is to work out exactly how much of a better chance he has actually been handed, and in this case, based on our assumptions, his increased chance is not really significant.

Complete Program

The complete program is shown below. Please note that to satisfy the formatting requirements of the wiki I have had to use &lt; in place of < and &gt; instead of > in various places. If you edit the page to take a copy of the code you will need to do a global replace to revert this in the resulting source code.


#include <stdio.h>
#include <strings.h>
#include <math.h>

#define         TOP   1
#define         LEFT  2
#define         RIGHT 3

typedef struct
{
   int     ranking ;
   char    name[200] ;
   double  prob_level[10] ;
} Player ;

typedef struct Node
{
   struct Node             *left ;
   struct Node             *right ;
   int                      player ;
} NODE ;

NODE   *node[8][128] ;
int     left[128] ;
int     right[128] ;
int     nlefts, nrights ;
Player  player[256] ;

int     method = 1 ;
double  total = 0.0 ;
char    result[256] = "" ;
char    buffer[256] = "" ;

main(argc, argv)
int     argc ;
char    **argv ;
{
       FILE   *stream = NULL;
       int     rd = 0 , loop = 0 , loop2 = 0;
       int     no_of_players = 0;
       int     level = 0 ;
       char    pr[30] = "";
       char   *ptr = NULL;
       int     lval=0;
       int     html=0;
       int     lastyear=0 ;

       /* open the file containing the draw */

       if (argc < 2 || argc > 4)
       {
           printf ("Usage: ko < filename >\n");
           printf ("or:    ko < filename > \n");
           printf ("or:    ko -html < filename >\n");
           printf ("or:    ko -html < filename > \n");
           exit (0) ;
       }

       if (!strcmp (argv[1], "-html"))
       {
           html = 1 ;
           stream = fopen (argv[2], "r") ;
           if (argc == 4)
               method = atoi (argv[3]) ;
       }
       else
       {
           if (argc == 3)
               method = atoi (argv[2]) ;
           stream = fopen (argv[1], "r") ;
       }


       /* read in the data from this file */

       loop=0;

       while (fgets (buffer, 256, stream))
       {
           char *rest = NULL ;

           ptr = (char *) strtok_r (buffer, ":", &rest) ;
           sprintf (player[loop].name, "%-30s", ptr) ;
           ptr = (char *) strtok_r (NULL, ":", &rest) ;
           player[loop].ranking = atoi (ptr) ;
           ptr = (char *) strtok_r (NULL, ":", &rest) ;
           lastyear = atoi (ptr) ;

           /* if last years results are available, treat this years as
              twice as significant */

           if (lastyear)
           {
               player[loop].ranking *= 2 ;
               player[loop].ranking += lastyear ;
           }
           loop++ ;
       }

       /* set up some info */

       no_of_players = loop;

       for (level=1, lval=no_of_players ;;level++)
       {
           lval = lval / 2 ;
           if (lval <= 1)
               break ;
       }

       /* ok, fairly obviously everyone has a 1.0 chance of getting
          to this bottom level */

       for (loop = 0; loop < no_of_players; loop++)
       {
            player[loop].prob_level[level] = 1.0 ;
       }

       /* create the tree */

       create_tree(level) ;

       /* calculate the probabilties */

       for (loop = level-1; loop >=  0; loop--)
       {
            calculate_probs (loop) ;
       }

       /* print out the results */

       if (html)
       {
           printf ("<center> <TABLE COLS=%d\n border = 3>", level + 2) ;
           printf ("<TR> <TD> <center> Player <center> </TD> <TD> <center> Ranking </center> </TD> \n") ;
           for (loop2 = level-1; loop2 >= 0; loop2--)
           {
               if (loop2 > 2)
                   printf ("<TD> <center> Round %d</center></TD>\n", level - loop2) ;
               else if (loop2 == 2)
                   printf ("<TD> <center>Quarter Final</center></TD>\n") ;
               else if (loop2 == 1)
                   printf ("<TD> <center>Semi Final</center></TD>\n") ;
               else if (loop2 == 0)
                   printf ("<TD><center>Final</center></TD>\n") ;
               }
               printf ("</TR>\n") ;
               for (loop = 0;loop < no_of_players; loop++)
               {
                   printf("<TR><TD><center>%s</center></TD><TD><center>%d</center></TD>\n", 
                               player[loop].name, player[loop].ranking) ;
                   for (loop2 = level-1; loop2 >= 0; loop2--)
                   {
                       double odds ;
                       odds = player[loop].prob_level[loop2] * 100.0 ;
                       printf ("<TD> <center>%2.2f</center></TD>\n", odds) ;
                   }
                   printf ("</TR>\n") ;
               }
               printf ("</TABLE>\n") ;
       }
       else
       {
               for (loop = 0; loop < no_of_players; loop++)
               {
                       sprintf (result, "%s", player[loop].name) ;

                       for (loop2 = level-1; loop2 >= 0; loop2--)
                       {
                               sprintf (pr, "%2.2f\t", player[loop].prob_level[loop2] * 100.0) ;
                               strcat (result, pr) ;
                       }

                       total += player[loop].prob_level[0] ;
                       strcat (result, "\n") ;
                       printf (result) ;
               }
       }

       /* close the input stream */

       fclose (stream) ;
}

create_tree(levels)
int levels ;
{
       int loop, loop2, i ;
       int     no_of_nodes ;

       /* create the binary tree which represents the draw */

       for (loop = levels; loop >= 0; loop--)
       {
           for (i = 0, no_of_nodes = 1; i < levels; i++)
           {
               no_of_nodes = no_of_nodes * 2 ;
           }

           /* no_of_nodes = (int) pow (2.0, (double) loop) ; */

           for (loop2 = 0; loop2 < no_of_nodes; loop2++)
           {
               node[loop][loop2] = (NODE *) malloc (sizeof(NODE)) ;

               if (loop == levels)
               {
                   node[loop][loop2]->left = NULL ;
                   node[loop][loop2]->right = NULL ;
                   node[loop][loop2]->player = loop2 ;
               }
               else
               {
                   node[loop][loop2]->left = node[loop+1][loop2*2] ;
                   node[loop][loop2]->right = node[loop+1][loop2*2 + 1] ;
                   node[loop][loop2]->player = -1 ;
               }
           }
       }
}

walk_tree(node, branch)
NODE *node ;
int  branch ;
{
       int nbranch ;

       /* collect the left and right children of a node in arrays */

       if (node->left)
       {
               nbranch = (branch == TOP) ? LEFT : branch ;

               if (node->left->player != -1)
               {
                       if (nbranch == RIGHT)
                               right[nrights++] = node->left->player ;
                       else
                               left[nlefts++] = node->left->player ;
               }

               walk_tree(node->left, nbranch) ;
       }

       if (node->right)
       {
               nbranch = (branch == TOP) ? RIGHT : branch ;

               if (node->right->player != -1)
               {
                       if (nbranch == RIGHT)
                               right[nrights++] = node->right->player ;
                       else
                               left[nlefts++] = node->right->player ;
               }

               walk_tree(node->right, nbranch) ;
       }
}

calculate_probs(level)
int level ;
{
       int             no_of_nodes ;
       int             loop, loop1, loop2, i ;
       double  prob, oprob ;
       double  probability() ;

       for (i = 0, no_of_nodes = 1;i < level; i++)
       {
               no_of_nodes = no_of_nodes * 2 ;
       }

       /* no_of_nodes = (int) pow (2.0, (double)level) ; */

       for (loop = 0; loop < no_of_nodes;loop++)
       {
               nlefts = nrights = 0 ;
               walk_tree (node[level][loop], TOP) ;

               /* for each on the left - probability of winning all
                  possibilities on the right */

               for (loop1 = 0; loop1 < nlefts; loop1++)
               {
                       oprob = 0.0 ;
                       for (loop2 = 0;loop2 < nrights; loop2++)
                       {
                               prob = probability (left[loop1], right[loop2]) ;
                               oprob += player[left[loop1]].prob_level[level+1]
                                      * player[right[loop2]].prob_level[level+1] * prob ;
                       }

                       if ((oprob == 0.0) && (prob != 0.0))
                               oprob = player[left[loop1]].prob_level[level+1] ;

                       player[left[loop1]].prob_level[level] = oprob ;
               }

               /* for each on the right - probability of winning all
                  possibilities on the left */

               for (loop1 = 0;loop1 < nrights; loop1++)
               {
                       oprob = 0.0 ;
                       for (loop2 = 0;loop2 < nlefts; loop2++)
                       {
                               prob = probability (right[loop1], left[loop2]) ;
                               oprob += player[right[loop1]].prob_level[level+1]
                                      * player[left[loop2]].prob_level[level+1] * prob ;
                       }

                       if ((oprob == 0.0) && (prob != 0.0))
                               oprob = player[right[loop1]].prob_level[level+1] ;

                       player[right[loop1]].prob_level[level] = oprob ;
               }
       }
}

double probability(p1, p2)
int p1, p2 ;
{
       /* probability that p1 beats p2 */

       double  prob ;
       int     denom ;

       if (strstr (player[p1].name, "Lost"))
           return (0.0) ;

       if (strstr (player[p2].name, "Lost"))
           return (1.0) ;

       denom = player[p1].ranking + player[p2].ranking ;
       if (denom == 0)
           return (1.0) ;

       if (method == 1)
       {
           prob = (double) player[p1].ranking 
                    / ((double) player[p1].ranking + (double) player[p2].ranking) ;
       }
       else if (method == 2)
       {
           double p1sq, p2sq ;
           p1sq = (double) player[p1].ranking ;
           p1sq = p1sq * p1sq ;
           p2sq = (double) player[p2].ranking ;
           p2sq = p2sq * p2sq ;
           prob = p1sq / (p1sq + p2sq) ;
       }
       return (prob) ;
} 


Computers | Open Source | Gambling


QR Code
QR Code odds_of_winning_a_knockout_tournament (generated for current page)
 

Advertise with Anonymous Ads