/[gnubg]/gnubg/mec.c
ViewVC logotype

Contents of /gnubg/mec.c

Parent Directory Parent Directory | Revision Log Revision Log


Revision 1.2 - (show annotations) (download)
Mon Apr 19 09:28:28 2004 UTC (20 years, 1 month ago) by Superfly_Jon
Branch: MAIN
CVS Tags: pre-rel-0-14-3
Changes since 1.1: +2 -2 lines
File MIME type: text/plain
Remove compiler warnings

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 }

savannah-hackers-public@gnu.org
ViewVC Help
Powered by ViewVC 1.1.26