1 |
/* |
2 |
* |
3 |
* mec - match equity calculator for backgammon. calculate equity table |
4 |
* given match length, gammon rate and winning probabilities. |
5 |
* |
6 |
* Copyright (C) 1996 Claes Thornberg (claest@it.kth.se) |
7 |
* |
8 |
* This program is free software; you can redistribute it and/or modify |
9 |
* it under the terms of the GNU General Public License as published by |
10 |
* the Free Software Foundation; either version 2 of the License, or |
11 |
* (at your option) any later version. |
12 |
* |
13 |
* This program is distributed in the hope that it will be useful, |
14 |
* but WITHOUT ANY WARRANTY; without even the implied warranty of |
15 |
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
16 |
* GNU General Public License for more details. |
17 |
* |
18 |
* You should have received a copy of the GNU General Public License |
19 |
* along with this program; if not, write to the Free Software |
20 |
* Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. |
21 |
* |
22 |
* Modified for usage with gnubg by Joern Thyssen <jth@gnubg.org>: |
23 |
* |
24 |
* (1) make external entry for usage in gnubg |
25 |
* (2) change "double" to "metentry", and typedef metentry to float |
26 |
* or double depending on MEC_STANDALONE |
27 |
* (3) Compile with MEC_STANDALONE to get Thornberg's original program, e.g., |
28 |
* |
29 |
* gcc -DMEC_STANDALONE mec.c -o mec |
30 |
* |
31 |
* $Id: mec.c,v 1.1 2004/04/16 20:06:28 thyssen Exp $ |
32 |
*/ |
33 |
|
34 |
#include <stdio.h> |
35 |
#include <stddef.h> |
36 |
#include <stdlib.h> |
37 |
|
38 |
#if !MEC_STANDALONE |
39 |
#include "mec.h" |
40 |
#endif |
41 |
|
42 |
struct dp |
43 |
{ |
44 |
double e; |
45 |
double w; |
46 |
}; |
47 |
|
48 |
typedef struct dp dp; |
49 |
|
50 |
void post_crawford (double, double, int, double **,double,double); |
51 |
|
52 |
void crawford (double, double, int, double **); |
53 |
|
54 |
void pre_crawford (double, double, int, double **); |
55 |
|
56 |
dp dpt (int, int, int, double, double, double **); |
57 |
|
58 |
/* |
59 |
Arguments are (in this order): |
60 |
match length |
61 |
gammon rate |
62 |
winning percentage (favorite) |
63 |
*/ |
64 |
|
65 |
#if MEC_STANDALONE |
66 |
|
67 |
int main (int argc, char **argv) |
68 |
{ |
69 |
/* match length */ |
70 |
|
71 |
int ml = argc > 1 ? atoi (argv[1]) : 9; |
72 |
|
73 |
/* gammon rate, i.e. how many of games won/lost will be gammons */ |
74 |
|
75 |
double gr = argc > 2 ? atof (argv[2]) : 0; |
76 |
|
77 |
/* Here one could argue for different approaches. Does the underdog |
78 |
in match (current score) have different gammon rate. Or does the |
79 |
underdog in match (equity at current score) have different gammon |
80 |
rate. This could be solved, but for now, we assume same rates. */ |
81 |
|
82 |
/* winning percentage for favorite in one game. NB: when one player |
83 |
is favorite, there is no symmetry in the equity table! I.e. |
84 |
E[i][1] = 1 - E[1][i] doesn't necessarily hold. This figure must |
85 |
be higher than or equal to .5, i.e. 50% */ |
86 |
|
87 |
double wpf = argc > 3 ? atof (argv[3]) : 0.5; |
88 |
|
89 |
/* Equity chart, E[p][o] = equity for p when p is p away, and o is o away. |
90 |
If there is a game favorite, i.e. wpf > 0.5, p above is considered |
91 |
to be the favorite in each game. For now we also assume no free drop |
92 |
vigourish. This will only affect the computation of post crawford |
93 |
equities, and is quite easy to correct. */ |
94 |
|
95 |
double **E = (double **) malloc ((ml + 1) * sizeof (double *)); |
96 |
|
97 |
double *ec = (double*) calloc ((ml + 1) * (ml + 1), sizeof (double)); |
98 |
|
99 |
{ |
100 |
int i; |
101 |
|
102 |
/* Initialize E to point to correct positions */ |
103 |
|
104 |
for (i = 0; i <= ml; i++) |
105 |
{ |
106 |
E[i] = & ec[i * (ml + 1)]; |
107 |
} |
108 |
|
109 |
/* Initialize E for 0-away scores */ |
110 |
|
111 |
for (i = 1; i <= ml; i++) |
112 |
{ |
113 |
E[0][i] = 1; |
114 |
E[i][0] = 0; |
115 |
} |
116 |
} |
117 |
|
118 |
/* Compute post crawford equities, given gammon rate, winning percentage |
119 |
for favorite (game), match length. Fill in the equity table. */ |
120 |
|
121 |
post_crawford (gr, wpf, ml, E, 0.0,0.0); |
122 |
|
123 |
{ |
124 |
int i; |
125 |
printf( "Post-crawford:\n" ); |
126 |
for ( i = 1; i < ml; ++i ) |
127 |
printf ("%6.3f", E[i][1]); |
128 |
printf( "\n" ); |
129 |
for ( i = 1; i < ml; ++i ) |
130 |
printf ("%6.3f", E[1][i]); |
131 |
printf( "\n" ); |
132 |
} |
133 |
|
134 |
|
135 |
/* Compute crawford equities, given gammon rate, winning percentage |
136 |
for favorite (game), match length, and post crawford equities. |
137 |
Fill in the table. */ |
138 |
|
139 |
crawford (gr, wpf, ml, E); |
140 |
|
141 |
/* Compute pre-crawford equities, given gammon rate, winning percentage |
142 |
for favorite (game), match length, and crawford equities. |
143 |
Fill in the table. */ |
144 |
|
145 |
pre_crawford (gr, wpf, ml, E); |
146 |
|
147 |
/* Print the equity table. Nothing fancy. */ |
148 |
|
149 |
{ |
150 |
int i, j; |
151 |
|
152 |
printf ("Gammon rate %5.4f\n" |
153 |
"Winning %% %5.4f\n\n", gr, wpf); |
154 |
|
155 |
|
156 |
printf ("%3s", ""); |
157 |
|
158 |
for (i = 1; i <= ml; i++) |
159 |
{ |
160 |
printf ("%6d", i); |
161 |
} |
162 |
|
163 |
printf ("\n"); |
164 |
|
165 |
for (i = 1; i <= ml; i++) |
166 |
{ |
167 |
printf ("%3d", i); |
168 |
for (j = 1; j <= ml; j++) |
169 |
printf ("%6.3f", E[i][j]); |
170 |
printf ("\n"); |
171 |
} |
172 |
} |
173 |
} |
174 |
|
175 |
#else /* MEC_STANDALONE */ |
176 |
|
177 |
extern void |
178 |
mec_pc( const float rGammonRate, |
179 |
const float rFreeDrop2Away, |
180 |
const float rFreeDrop4Away, |
181 |
const float rWinRate, |
182 |
float arMetPC[ MAXSCORE ] ) { |
183 |
|
184 |
int i; |
185 |
|
186 |
/* match length */ |
187 |
|
188 |
int ml = 64; |
189 |
|
190 |
/* gammon rate, i.e. how many of games won/lost will be gammons */ |
191 |
|
192 |
double gr = rGammonRate; |
193 |
|
194 |
/* Here one could argue for different approaches. Does the underdog |
195 |
in match (current score) have different gammon rate. Or does the |
196 |
underdog in match (equity at current score) have different gammon |
197 |
rate. This could be solved, but for now, we assume same rates. */ |
198 |
|
199 |
/* winning percentage for favorite in one game. NB: when one player |
200 |
is favorite, there is no symmetry in the equity table! I.e. |
201 |
E[i][1] = 1 - E[1][i] doesn't necessarily hold. This figure must |
202 |
be higher than or equal to .5, i.e. 50% */ |
203 |
|
204 |
double wpf = rWinRate; |
205 |
|
206 |
/* Equity chart, E[p][o] = equity for p when p is p away, and o is o away. |
207 |
If there is a game favorite, i.e. wpf > 0.5, p above is considered |
208 |
to be the favorite in each game. For now we also assume no free drop |
209 |
vigourish. This will only affect the computation of post crawford |
210 |
equities, and is quite easy to correct. */ |
211 |
|
212 |
double **E = (double **) malloc ((ml + 1) * sizeof (double *)); |
213 |
|
214 |
double *ec = (double*) calloc ((ml + 1) * (ml + 1), sizeof (double)); |
215 |
|
216 |
{ |
217 |
|
218 |
/* Initialize E to point to correct positions */ |
219 |
|
220 |
for (i = 0; i <= ml; i++) |
221 |
{ |
222 |
E[i] = & ec[i * (ml + 1)]; |
223 |
} |
224 |
|
225 |
/* Initialize E for 0-away scores */ |
226 |
|
227 |
for (i = 1; i <= ml; i++) |
228 |
{ |
229 |
E[0][i] = 1; |
230 |
E[i][0] = 0; |
231 |
} |
232 |
} |
233 |
|
234 |
/* Compute post crawford equities, given gammon rate, winning percentage |
235 |
for favorite (game), match length. Fill in the equity table. */ |
236 |
|
237 |
post_crawford (gr, wpf, ml, E,rFreeDrop2Away,rFreeDrop4Away); |
238 |
|
239 |
/* save post Crawford equities */ |
240 |
|
241 |
for ( i = 0; i < ml; ++i ) |
242 |
arMetPC[ i ] = E[ i + 1 ][ 1 ]; |
243 |
|
244 |
/* garbage collect */ |
245 |
|
246 |
free( ec ); |
247 |
|
248 |
} |
249 |
|
250 |
|
251 |
extern void |
252 |
mec( const float rGammonRate, |
253 |
const float rWinRate, |
254 |
/* const */ float aarMetPC[ 2 ][ MAXSCORE ], |
255 |
float aarMet[ MAXSCORE ][ MAXSCORE ] ) { |
256 |
|
257 |
int i, j; |
258 |
|
259 |
/* match length */ |
260 |
|
261 |
int ml = 64; |
262 |
|
263 |
/* gammon rate, i.e. how many of games won/lost will be gammons */ |
264 |
|
265 |
double gr = rGammonRate; |
266 |
|
267 |
/* Here one could argue for different approaches. Does the underdog |
268 |
in match (current score) have different gammon rate. Or does the |
269 |
underdog in match (equity at current score) have different gammon |
270 |
rate. This could be solved, but for now, we assume same rates. */ |
271 |
|
272 |
/* winning percentage for favorite in one game. NB: when one player |
273 |
is favorite, there is no symmetry in the equity table! I.e. |
274 |
E[i][1] = 1 - E[1][i] doesn't necessarily hold. This figure must |
275 |
be higher than or equal to .5, i.e. 50% */ |
276 |
|
277 |
double wpf = rWinRate; |
278 |
|
279 |
/* Equity chart, E[p][o] = equity for p when p is p away, and o is o away. |
280 |
If there is a game favorite, i.e. wpf > 0.5, p above is considered |
281 |
to be the favorite in each game. For now we also assume no free drop |
282 |
vigourish. This will only affect the computation of post crawford |
283 |
equities, and is quite easy to correct. */ |
284 |
|
285 |
double **E = (double **) malloc ((ml + 1) * sizeof (double *)); |
286 |
|
287 |
double *ec = (double*) calloc ((ml + 1) * (ml + 1), sizeof (double)); |
288 |
|
289 |
{ |
290 |
|
291 |
/* Initialize E to point to correct positions */ |
292 |
|
293 |
for (i = 0; i <= ml; i++) |
294 |
{ |
295 |
E[i] = & ec[i * (ml + 1)]; |
296 |
} |
297 |
|
298 |
/* Initialize E for 0-away scores */ |
299 |
|
300 |
for (i = 1; i <= ml; i++) |
301 |
{ |
302 |
E[0][i] = 1; |
303 |
E[i][0] = 0; |
304 |
} |
305 |
} |
306 |
|
307 |
/* Compute post crawford equities, given gammon rate, winning percentage |
308 |
for favorite (game), match length. Fill in the equity table. */ |
309 |
|
310 |
for ( i = 0; i < ml; ++i ) |
311 |
E[ i + 1 ][ 1 ] = aarMetPC[ 0 ][ i ]; |
312 |
|
313 |
for ( i = 0; i < ml; ++i ) |
314 |
E[ 1 ][ i + 1 ] = 1.0 - aarMetPC[ 1 ][ i ]; |
315 |
|
316 |
/* Compute crawford equities, given gammon rate, winning percentage |
317 |
for favorite (game), match length, and post crawford equities. |
318 |
Fill in the table. */ |
319 |
|
320 |
crawford (gr, wpf, ml, E); |
321 |
|
322 |
/* Compute pre-crawford equities, given gammon rate, winning percentage |
323 |
for favorite (game), match length, and crawford equities. |
324 |
Fill in the table. */ |
325 |
|
326 |
pre_crawford (gr, wpf, ml, E); |
327 |
|
328 |
/* save the match equiy table */ |
329 |
|
330 |
for ( i = 0; i < ml; ++i ) |
331 |
for ( j = 0; j < ml; ++j ) |
332 |
aarMet[ i ][ j ] = E[ i + 1 ][ j + 1 ]; |
333 |
|
334 |
/* garbage collect */ |
335 |
|
336 |
free( ec ); |
337 |
|
338 |
} |
339 |
|
340 |
#endif /* ! MEC_STANDALONE */ |
341 |
|
342 |
/* If last bit is zero, then x is even. */ |
343 |
#define even(x) (((x)&0x1)==0) |
344 |
|
345 |
/* sq returns x if x is greater than zero, else it returns zero. */ |
346 |
#define sq(x) ((x)>0?(x):0) |
347 |
|
348 |
void post_crawford (double gr, double wpf, int ml, double **E, |
349 |
double fd2, double fd4) |
350 |
{ |
351 |
int i; |
352 |
|
353 |
E[1][1] = wpf; |
354 |
|
355 |
for (i = 2; i <= ml; i++) |
356 |
{ |
357 |
if (even (i)) |
358 |
{ |
359 |
/* Free drop condition exists */ |
360 |
E[1][i] = E[1][i - 1]; |
361 |
E[i][1] = E[i - 1][1]; |
362 |
/* jth: add empirical values for free drop */ |
363 |
if ( i == 2 ) { |
364 |
/* 2-away */ |
365 |
E[1][i] += fd2; |
366 |
E[i][1] -= fd2; |
367 |
} |
368 |
else if ( i == 4 ) { |
369 |
/* 4-away */ |
370 |
E[1][i] += fd4; |
371 |
E[i][1] += fd4; |
372 |
} |
373 |
} |
374 |
else |
375 |
{ |
376 |
E[1][i] = /* Equity for favorite when 1-away, i-away */ |
377 |
E[0][i] * wpf /* Favorite wins */ |
378 |
+ E[1][sq (i - 2)] * (1 - wpf) * (1 - gr) /* Favorite loses single */ |
379 |
+ E[1][sq (i - 4)] * (1 - wpf) * gr; /* Favorite loses gammon */ |
380 |
|
381 |
E[i][1] = /* Equity for favorite when i-away, 1-away */ |
382 |
E[i][0] * (1 - wpf) /* Favorite loses */ |
383 |
+ E[sq (i - 2)][1] * wpf * (1 - gr) /* Favorite wins single */ |
384 |
+ E[sq (i - 4)][1] * wpf * gr; /* Favorite wins gammon */ |
385 |
} |
386 |
} |
387 |
} |
388 |
|
389 |
void crawford (double gr, double wpf, int ml, double **E) |
390 |
{ |
391 |
int i; |
392 |
|
393 |
/* Compute crawford equities. Do this backwards, since |
394 |
we overwrite post crawford equities with crawford equities. |
395 |
In this way we only overwrite equities no longer needed. */ |
396 |
|
397 |
for (i = ml; i >= 2; i--) |
398 |
{ |
399 |
E[1][i] = /* Equity for favorite when 1-away,i-away */ |
400 |
E[0][i] * wpf /* Favorite wins */ |
401 |
+ E[1][i - 1] * (1 - wpf) * (1 - gr) /* Favorite loses single */ |
402 |
+ E[1][i - 2] * (1 - wpf) * gr; /* Favorite loses gammon */ |
403 |
|
404 |
E[i][1] = /* Equity for favorite when i-away, 1-away */ |
405 |
E[i][0] * (1 - wpf) /* Favorite loses */ |
406 |
+ E[i - 1][1] * wpf * (1 - gr) /* Favorite wins single */ |
407 |
+ E[i - 2][1] * wpf * gr; /* Favorite wins gammon */ |
408 |
} |
409 |
} |
410 |
|
411 |
void pre_crawford (double gr, double wpf, int ml, double **E) |
412 |
{ |
413 |
int i, j; |
414 |
dp dpf, dpu; |
415 |
double eq; |
416 |
|
417 |
for (i = 2; i <= ml; i++) |
418 |
for (j = i; j <= ml; j++) |
419 |
{ |
420 |
dpf = dpt (i, j, 2, gr, wpf, E); |
421 |
dpu = dpt (j, i, 2, gr, 1 - wpf, E); |
422 |
|
423 |
dpu.e = 1 - dpu.e; |
424 |
dpu.w = 1 - dpu.w; |
425 |
|
426 |
eq = dpu.e |
427 |
+ (dpf.e - dpu.e) * (wpf - dpu.w) / (dpf.w - dpu.w); |
428 |
|
429 |
E[i][j] = eq; |
430 |
|
431 |
if (i != j) |
432 |
{ |
433 |
dpf = dpt (j, i, 2, gr, wpf, E); |
434 |
dpu = dpt (i, j, 2, gr, 1 - wpf, E); |
435 |
|
436 |
dpu.e = 1 - dpu.e; |
437 |
dpu.w = 1 - dpu.w; |
438 |
|
439 |
eq = dpu.e |
440 |
+ (dpf.e - dpu.e) * (wpf - dpu.w) / (dpf.w - dpu.w); |
441 |
|
442 |
E[j][i] = eq; |
443 |
} |
444 |
} |
445 |
} |
446 |
|
447 |
/* Compute point when p doubles o to c, assuming gammon rate gr, |
448 |
p wins wpp % of games, and equities E for favorite. At this |
449 |
point o does equally well passing the double as taking it. */ |
450 |
|
451 |
dp dpt (int p, int o, int c, double gr, double wpp, double **E) |
452 |
{ |
453 |
dp dpo, dpp; |
454 |
double e0, w0, edp, wdp; |
455 |
|
456 |
if (p <= c / 2) |
457 |
{ |
458 |
/* No reason for p to double o, since a single win |
459 |
is enough to win the match. */ |
460 |
|
461 |
dpp.e = 1; dpp.w = 1; |
462 |
return dpp; |
463 |
} |
464 |
|
465 |
/* p might double o to c since he needs more than a single |
466 |
game to win the match. */ |
467 |
|
468 |
/* Find out when o (re)doubles p to 2*c */ |
469 |
|
470 |
dpo = dpt (o, p, 2*c, gr, 1 - wpp, E); |
471 |
|
472 |
/* Find out equity for o if p does well and wins |
473 |
all games here (assuming no recube from o), i.e. |
474 |
o loses all games sitting on a c-cube. */ |
475 |
|
476 |
if (wpp > 0.5) |
477 |
{ |
478 |
/* o isn't game favorite, equity for o at o-away x-away is 1 - E[x][o]. */ |
479 |
|
480 |
e0 = (1 - E[sq (p - c)][o]) * (1 - gr) |
481 |
+ (1 - E[sq (p - 2 * c)][o]) * gr; |
482 |
} |
483 |
else |
484 |
{ |
485 |
/* o is game favorite, equity for o at o-away x-away is E[o][x]. */ |
486 |
|
487 |
e0 = E[o][sq (p - c)] * (1 - gr) |
488 |
+ E[o][sq (p - 2 * c)] * gr; |
489 |
} |
490 |
|
491 |
w0 = 0; |
492 |
|
493 |
/* Find out o:s equity if o passes the double to c, i.e. loses c / 2 points. */ |
494 |
|
495 |
if (wpp > 0.5) |
496 |
{ |
497 |
/* o isn't game favorite, equity for o at o-away x-away is 1 - E[x][o]. */ |
498 |
|
499 |
edp = 1 - E[sq (p - c / 2)][o]; |
500 |
} |
501 |
else |
502 |
{ |
503 |
/* o is game favorite, equity for o at o-away x-away is E[o][x]. */ |
504 |
|
505 |
edp = E[o][sq (p - c / 2)]; |
506 |
} |
507 |
|
508 |
/* Find the winning percentage, which on the line from |
509 |
(w0,e0) to (dpo.w,dpo.e) gives o an equity equal to O's |
510 |
equity passing the double to c (i.e. losing c / 2 pts) */ |
511 |
|
512 |
wdp = (edp - e0) * dpo.w / (dpo.e - e0); |
513 |
|
514 |
/* Now we know when p should double o, expressed as |
515 |
winning percentage and equity for o. Return this |
516 |
expressed in figures for p */ |
517 |
|
518 |
dpp.e = 1 - edp; dpp.w = 1 - wdp; |
519 |
return dpp; |
520 |
} |