File indexing completed on 2022-09-20 13:02:50

0001 /***************************************************************************
0002  *   Copyright (C) 2005, 2008 by Albert Astals Cid <aacid@kde.org>         *
0003  *                                                                         *
0004  *   This program is free software; you can redistribute it and/or modify  *
0005  *   it under the terms of the GNU General Public License as published by  *
0006  *   the Free Software Foundation; either version 2 of the License, or     *
0007  *   (at your option) any later version.                                   *
0008  ***************************************************************************/
0009 
0010 // Using lots of code from
0011 
0012 /*
0013  * Gyatzee: Gnomified Yahtzee game.
0014  * (C) 1998 the Free Software Foundation
0015  *
0016  * File:   computer.c
0017  *
0018  * Author: Scott Heavner
0019  *
0020  *   Window manager independent yahtzee routines for computer opponents.
0021  *
0022  *   Variables are exported in yahtzee.h
0023  *
0024  *   This program is based on based on orest zborowski's curses based
0025  *   yahtze (c)1992.
0026  *
0027  *   This program is free software; you can redistribute it and/or modify
0028  *   it under the terms of the GNU General Public License as published by
0029  *   the Free Software Foundation; either version 2 of the License, or
0030  *   (at your option) any later version.
0031  *
0032  *   This program is distributed in the hope that it will be useful,
0033  *   but WITHOUT ANY WARRANTY; without even the implied warranty of
0034  *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
0035  *   GNU General Public License for more details.
0036  *
0037  *   You should have received a copy of the GNU General Public License
0038  *   along with this program; if not, write to the Free Software
0039  *   Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
0040  */
0041 
0042 #include "player.h"
0043 
0044 static const int NUM_UPPER = 6;
0045 static const int NUM_FIELDS = 13;
0046 static const int H_3 = 6;
0047 static const int H_4 = 7;
0048 static const int H_FH = 8;
0049 static const int H_SS = 9;
0050 static const int H_LS = 10;
0051 static const int H_YA = 11;
0052 static const int H_CH = 12;
0053 
0054 typedef struct {
0055   int val;
0056   int sel;
0057 } DiceInfo;
0058 
0059 DiceInfo DiceValues[5] = { {1,0}, {2,0}, {3,0}, {4,0}, {5,0} };
0060 
0061 void setComputerDiceValue(int dice, int value)
0062 {
0063     DiceValues[dice].val = value;
0064     DiceValues[dice].sel = false;
0065 }
0066 
0067 bool getComputerDiceSelected(int dice)
0068 {
0069     return DiceValues[dice].sel;
0070 }
0071 
0072 bool computerDiceSelected()
0073 {
0074     bool selected = false;
0075     int i = 0;
0076     while (!selected && i < 5)
0077     {
0078         selected = DiceValues[i].sel;
0079         i++;
0080     }
0081     return selected;
0082 }
0083 
0084 int numberOfRolls;
0085 
0086 /*
0087 **  questions are:
0088 **      0:  none
0089 **      1:  "what dice to roll again?"
0090 **      2:  "where do you want to put that?"
0091 */
0092 
0093 typedef struct
0094 {
0095     int value;
0096     char rerolls[5];
0097 } DiceRank;
0098 
0099 static DiceRank bc_table[NUM_FIELDS];
0100 
0101 static void MarkAllRerolls(DiceRank *t, int val)
0102 {
0103   int i;
0104   for (i=0; i<5; i++)
0105     t->rerolls[i] = val;
0106 }
0107 
0108 static inline void TagReroll(DiceRank *t, int i)
0109 {
0110   t->rerolls[i] = 1;
0111 }
0112 
0113 static inline void ClearReroll(DiceRank *t, int i)
0114 {
0115   t->rerolls[i] = 0;
0116 }
0117 
0118 static inline void ClearRerolls(DiceRank *t)
0119 {
0120   MarkAllRerolls(t,0);
0121 }
0122 
0123 static inline void TagRerolls(DiceRank *t)
0124 {
0125   MarkAllRerolls(t,1);
0126 }
0127 
0128 /*static inline int NeedsReroll(DiceRank *t)
0129 {
0130         int i, j=0;
0131         for (i=0; i<5; i++)
0132                 if (t->rerolls[i])
0133                         j++;
0134         return j;
0135 }*/
0136 
0137 int 
0138 add_dice(void)
0139 {
0140         int i;
0141         int val;
0142 
0143         val = 0;
0144 
0145         for (i = 0; i < 5; ++i)
0146                 val += DiceValues[i].val;
0147 
0148         return (val);
0149 }
0150 
0151 int 
0152 count(int val)
0153 {
0154         int i;
0155         int num;
0156 
0157         num = 0;
0158 
0159         for (i = 0; i < 5; ++i)
0160                 if (DiceValues[i].val == val)
0161                         ++num;
0162 
0163         return (num);
0164 }
0165 
0166 int 
0167 find_n_of_a_kind(int n, int but_not)
0168 {
0169         int i;
0170 
0171         for (i = 0; i < 5; ++i)
0172         {
0173                 if (DiceValues[i].val == but_not)
0174                         continue;
0175 
0176                 if (count(DiceValues[i].val) >= n)
0177                         return (DiceValues[i].val);
0178         }
0179 
0180         return (0);
0181 }
0182 
0183 int 
0184 find_straight(int run, int notstart, int notrun)
0185 {
0186         int i;
0187         int j;
0188 
0189         for (i = 1; i < 7; ++i)
0190         {
0191                 if (i >= notstart && i < notstart + notrun)
0192                         continue;
0193 
0194                 for (j = 0; j < run; ++j)
0195                         if (!count(i + j))
0196                                 break;
0197 
0198                 if (j == run)
0199                         return (i);
0200         }
0201 
0202         return (0);
0203 }
0204 
0205 /*static char *RerollString(DiceRank *t)
0206 {
0207         static char dice_string[11];
0208         int i;
0209 
0210         sprintf(dice_string,"          ");
0211 
0212         for (i=0; i<5; i++) {
0213                 if (t->rerolls[i])
0214                         dice_string[i*2] = '1'+i;
0215                 else
0216                         dice_string[i*2] = ' ';
0217         }
0218 
0219         return dice_string;
0220 }*/
0221 
0222 /*
0223 **  depending on the dice rolls, we fill in the choice table.  if
0224 **  for a particular choice the rolls are good, we put an appropriate
0225 **  value in the table.  we also give which die need to be rerolled.
0226 **
0227 **  basically, the value system is based off the highest score possible
0228 **  rolling the dice - all 6 (6 x 5 = 30).  so the best any of the upper
0229 **  ranks can get is 30.
0230 */
0231 
0232 static int throwaway[NUM_FIELDS] =
0233 {
0234     4,      /* 1 */
0235     3,      /* 2 */
0236     2,      /* 3 */
0237     2,      /* 4 */
0238     1,      /* 5 */
0239     1,      /* 6 */
0240     3,      /* 3 of a kind */
0241     5,      /* 4 of a kind */
0242     4,      /* Full House */
0243     3,      /* Small straight */
0244     5,      /* Large straight */
0245     4,      /* Yahtzee */
0246     0,      /* Chance */
0247 };
0248 
0249 static void
0250 BuildTable(const player &p, int NumberOfRolls)
0251 {
0252     int i;
0253     int j;
0254     int k;
0255     int d;
0256     int d2 = -1;
0257     int overflow;
0258 
0259     for (i = 0; i < NUM_FIELDS; ++i)
0260     {
0261         if (p.score(i) >= 0)
0262             bc_table[i].value = -99;
0263         else
0264             bc_table[i].value = throwaway[i];
0265 
0266         TagRerolls(&bc_table[i]);
0267     }
0268 
0269 /*
0270 **  HANDLING UPPER SLOTS
0271 */
0272 
0273 /*
0274 **  first, we calculate the overflow of the upper ranks. that is, we
0275 **  count all the points we have left over from our 3-of-all rule
0276 **  if we get 3 of all in the upper ranks, we get a bonus, so if
0277 **  we get 4 of something, that means a lower roll may be acceptable,
0278 **  as long as we remain in the running for a bonus.  overflow can
0279 **  be negative as well, in which case throwaway rolls are not
0280 **  encouraged, and a high roll will get a nice boost
0281 */
0282     overflow = 0;
0283 
0284     for (i = 0; i < NUM_UPPER; ++i)
0285     {
0286         if (p.score(i) >= 0)
0287             continue;
0288 
0289         overflow += (count(i+1) - 3) * (i+1);
0290     }
0291 
0292     for (i = 0; i < NUM_UPPER; ++i)
0293     {
0294         if (p.score(i) >= 0)
0295             continue;
0296 
0297         ClearRerolls(&bc_table[i]);
0298 
0299         for (d = 0; d < 5; ++d) {
0300                         if (DiceValues[d].val != i + 1)
0301                                 TagReroll(&bc_table[i],d);
0302         }
0303 
0304 /*
0305 **  ok. now we set a base value on the roll based on its count and
0306 **  how much it is worth to us.
0307 */
0308         bc_table[i].value = count(i+1) * 8;
0309 
0310 /*
0311 **  we have to play games with the bonus.
0312 **  if we already have a bonus, then all free slots are candidates for
0313 **      throwing away - we only do this when there are no more rolls
0314 **  if this would get us a bonus, we make it very attractive
0315 **
0316 **  if we get 3 of everything on the top, we get a bonus. so...
0317 **  if we have more than 3, we make the choice more attractive.
0318 **  if less than 3, we make it less attractive.
0319 **  if our overflow (any that are more than 3, summed up) covers up
0320 **      our lack (if we only have 2, and there were 4 6's), we
0321 **      do not penalize ourselves as much (since we're still in the
0322 **      running for a bonus)
0323 */
0324 
0325         if (p.upperTotal() >= 63)
0326         {
0327             if (NumberOfRolls > 2)
0328                 bc_table[i].value += 10;
0329         }
0330 
0331         else if (p.upperTotal() + count(i+1) * (i+1) >= 63)
0332         {
0333             bc_table[i].value += 35;
0334         }
0335 
0336         if (count(i+1) < 3)
0337         {
0338             if (overflow < (3 - count(i+1)) * (i+1))
0339                 bc_table[i].value -= (3 - count(i+1)) * 2;
0340         }
0341 
0342         else if (count(i+1) > 3)
0343         {
0344             bc_table[i].value += (count(i+1) - 3) * 2;
0345         }
0346     }
0347 
0348 /*
0349 **  HANDLING LOWER SLOTS
0350 */
0351 
0352 /*
0353 **  first, we look for potential.  these values will be larger than the
0354 **  single rolls but less than the made rolls (or those with higher value)
0355 **
0356 **  we also do such thinking only if we're not supposed to be looking just
0357 **  for the best combinations...
0358 */
0359     if (NumberOfRolls < 3)
0360     {
0361 /*
0362 **  searching for large straight... here we chicken out and only look at
0363 **  runs which might have possibilities
0364 */
0365         if (p.score(H_LS) < 0)
0366         {
0367             for (i = 4; i > 0; --i)
0368             {
0369                 d2 = find_straight(i, 0, 0 /* SDH 0 or 1? */);
0370 
0371                 if (d2 == 0)
0372                     continue;
0373 
0374                 bc_table[H_LS].value = (40 * i) / 5;
0375 
0376                 ClearRerolls(&bc_table[H_LS]);
0377 
0378                 for (d = 1; d < 7; ++d)
0379                 {
0380                     if (count(d) > 0)
0381                     {
0382                         if (d < d2 || d >= d2 + i)
0383                             k = count(d);
0384 
0385                         else
0386                             k = count(d) - 1;
0387 
0388                         if (k < 1)
0389                             continue;
0390 
0391                         for (j = 0; j < 5; ++j)
0392                         {
0393                             if (DiceValues[j].val!=d)
0394                                 continue;
0395 
0396                                                         TagReroll(&bc_table[H_LS],j);
0397 
0398                             if (!--k)
0399                                 break;
0400                         }
0401                     }
0402                 }
0403 
0404                 break;
0405             }
0406         }
0407 /*
0408 **  searching for small straight... here we chicken out and only look at
0409 **  runs which might have possibilities
0410 */
0411         if (p.score(H_SS) < 0)
0412         {
0413             for (i = 3; i > 0; --i)
0414             {
0415                 d2 = find_straight(i, 0, 0 /* SDH 0 or 1? */);
0416 
0417                 if (d2 == 0)
0418                     continue;
0419 
0420                 bc_table[H_SS].value = (30 * i) / 4;
0421 
0422                 ClearRerolls(&bc_table[H_SS]);
0423 
0424                 for (d = 1; d < 7; ++d)
0425                 {
0426                     if (count(d) > 0)
0427                     {
0428                         if (d < d2 || d >= d2 + i)
0429                             k = count(d);
0430 
0431                         else
0432                             k = count(d) - 1;
0433 
0434                         if (k < 1)
0435                             continue;
0436 
0437                         for (j = 0; j < 5; ++j)
0438                         {
0439                             if (DiceValues[j].val!=d)
0440                                 continue;
0441 
0442                                                         TagReroll(&bc_table[H_SS],j);
0443 
0444                             if (!--k)
0445                                 break;
0446                         }
0447                     }
0448                 }
0449 
0450                 break;
0451             }
0452         }
0453 /*
0454 **  searching for 3 of a kind
0455 */
0456         if (p.score(H_3) < 0)
0457         {
0458             for (i = 2; i > 0; --i)
0459             {
0460                 for (d = 6; d > 0; --d)
0461                 {
0462                     if (count(d) >= i)
0463                         break;
0464                 }
0465 
0466                 if (d == 0)
0467                     continue;
0468 
0469                 ClearRerolls(&bc_table[H_3]);
0470 
0471                 bc_table[H_3].value = (d * i);
0472 
0473                 for (j = 0; j < 5; ++j)
0474                     if (DiceValues[j].val != d) {
0475                                                 TagReroll(&bc_table[H_3],j);
0476                     }
0477 
0478                 break;
0479             }
0480         }
0481 /*
0482 **  searching for 4 of a kind
0483 */
0484         if (p.score(H_4) < 0)
0485         {
0486             for (i = 3; i > 0; --i)
0487             {
0488                 for (d = 6; d > 0; --d)
0489                 {
0490                     if (count(d) >= i)
0491                         break;
0492                 }
0493 
0494                 if (d == 0)
0495                     continue;
0496 
0497                 bc_table[H_4].value = (d * i);
0498 
0499                 ClearRerolls(&bc_table[H_4]);
0500 
0501                 for (j = 0; j < 5; ++j)
0502                     if (DiceValues[j].val != d) {
0503                                                 TagReroll(&bc_table[H_4],j);
0504                     }
0505 
0506                 break;
0507             }
0508         }
0509 
0510 /*
0511 **  searching for yahtzee... we can't set the potential value too high
0512 **  because if we fail, the value will be no better than 4 of a kind (or so)
0513 **  so, we make scoring the same as for 3-4 of a kind (this is 5 of a kind!)
0514 */
0515         if (p.score(H_YA) < 0)
0516         {
0517             for (i = 4; i > 0; --i)
0518             {
0519                 for (d = 6; d > 0; --d)
0520                 {
0521                     if (count(d) >= i)
0522                         break;
0523                 }
0524 
0525                 if (d == 0)
0526                     continue;
0527 
0528                 bc_table[H_YA].value = (d * i);
0529 
0530                 ClearRerolls(&bc_table[H_YA]);
0531 
0532                 for (j = 0; j < 5; ++j)
0533                     if (DiceValues[j].val != d)
0534                                                 TagReroll(&bc_table[H_YA],j);
0535 
0536                 break;
0537             }
0538         }
0539 
0540 /*
0541 **  searching for full house
0542 */
0543         if (p.score(H_FH) < 0)
0544         {
0545             for (i = 4; i > 0; --i)
0546             {
0547                 d = find_n_of_a_kind(i, 0);
0548 
0549                 if (d == 0)
0550                     continue;
0551 
0552                 for (j = i; j > 0; --j)
0553                 {
0554                     d2 = find_n_of_a_kind(j, d);
0555 
0556                     if (d2 > 0)
0557                         break;
0558                 }
0559 
0560                 if (j == 0)
0561                     continue;
0562 
0563                 ClearRerolls(&bc_table[H_FH]);
0564 
0565                 bc_table[H_FH].value = (i * 24 + j * 36) / 6;
0566 
0567                 for (i = 0; i < 5; ++i)
0568                 {
0569                     if (DiceValues[i].val != d &&
0570                       DiceValues[i].val != d2)
0571                                                 TagReroll(&bc_table[H_FH],i);
0572                 }
0573 
0574                 break;
0575             }
0576         }
0577     }
0578 
0579 /*
0580 **  now we look hard at what we got
0581 */
0582     if (p.score(H_SS) < 0 && find_straight(4, 0, 0))
0583     {
0584         d = find_straight(4, 0, 0);
0585 
0586         for (i = 0; i < 5; ++i)
0587             if (count(DiceValues[i].val) > 1 ||
0588                             DiceValues[i].val < d || DiceValues[i].val > d + 3) {
0589                                 TagReroll(&bc_table[H_SS],i);
0590                 break;
0591             }
0592 
0593         bc_table[H_SS].value = 30;
0594     }
0595 
0596     if (p.score(H_LS) < 0 && find_straight(5, 0, 0))
0597     {
0598         bc_table[H_LS].value = 40;
0599 
0600         ClearRerolls(&bc_table[H_LS]);
0601     }
0602 
0603     if (p.score(H_CH) < 0 && NumberOfRolls > 2)
0604     {
0605         bc_table[H_CH].value = add_dice();
0606 
0607         if (bc_table[H_CH].value < 20)
0608             bc_table[H_CH].value /= 2;
0609 
0610         ClearRerolls(&bc_table[H_CH]);
0611 
0612         for (i = 0; i < 5; ++i)
0613             if (DiceValues[i].val < 4)
0614                                 TagReroll(&bc_table[H_CH],i);
0615     }
0616 
0617     if (p.score(H_FH) < 0)
0618     {
0619         d = find_n_of_a_kind(3, 0);
0620 
0621         if (d != 0)
0622         {
0623             if (find_n_of_a_kind(2, d))
0624             {
0625                 bc_table[H_FH].value = 25;
0626 
0627                 ClearRerolls(&bc_table[H_FH]);
0628             }
0629         }
0630     }
0631 
0632     if (p.score(H_3) < 0)
0633     {
0634         d = find_n_of_a_kind(3, 0);
0635 
0636         if (d != 0)
0637         {
0638             bc_table[H_3].value = add_dice();
0639 
0640             ClearRerolls(&bc_table[H_3]);
0641 
0642             for (i = 0; i < 5; ++i)
0643                 if (d != DiceValues[i].val)
0644                                         TagReroll(&bc_table[H_3],i);
0645         }
0646     }
0647 
0648     if (p.score(H_4) < 0)
0649     {
0650         d = find_n_of_a_kind(4, 0);
0651 
0652         if (d != 0)
0653         {
0654 /*
0655 **  there will be a tie between 3 of a kind and 4 of a kind. we add 1
0656 **  to break the tie in favor of 4 of a kind
0657 */
0658             bc_table[H_4].value = add_dice() + 1;
0659             
0660             ClearRerolls(&bc_table[H_4]);
0661 
0662             for (i = 0; i < 5; ++i)
0663                 if (d != DiceValues[i].val)
0664                                         TagReroll(&bc_table[H_4],i);
0665         }
0666     }
0667 
0668     if (find_n_of_a_kind(5, 0))
0669     {
0670 
0671         if (p.score(H_YA) == 0)
0672             bc_table[H_YA].value = -99; /* scratch */
0673 
0674         else
0675             bc_table[H_YA].value = 150; /* so he will use it! */
0676         
0677     }
0678 }
0679 
0680 void
0681 ComputerRolling(const player &p, int NumberOfRolls)
0682 {
0683     int i;
0684     int best;
0685     int bestv;
0686 
0687     BuildTable(p, NumberOfRolls);
0688         
0689     best = 0;
0690         
0691     bestv = -99;
0692         
0693     for (i = NUM_FIELDS-1; i >= 0; --i)
0694         if (bc_table[i].value >= bestv) {
0695                         best = i;
0696                         
0697                         bestv = bc_table[i].value;
0698                 }
0699 
0700         for (i=0; i<5; ++i)
0701                 DiceValues[i].sel = bc_table[best].rerolls[i];
0702 }
0703 
0704 /*
0705 **  what we do here is generate a table of all the choices then choose
0706 **  the highest value one.  in case of a tie, we go for the lower choice
0707 **  cause higher choices tend to be easier to better
0708 */
0709 
0710 int ComputerScoring(const player &p)
0711 {
0712     int i;
0713     int best;
0714     int bestv;
0715 
0716     BuildTable(p, 2);
0717 
0718     best = 0;
0719 
0720     bestv = -99;
0721 
0722     for (i = NUM_FIELDS-1; i >= 0; --i) {
0723             if (bc_table[i].value > bestv)
0724             {
0725                 best = i;
0726 
0727                 bestv = bc_table[i].value;
0728             }
0729         }
0730 
0731     return best;
0732 }
0733