File indexing completed on 2024-06-09 04:03:36

0001 /*
0002  * Copyright (C) 2006-2009 Stephan Kulow <coolo@kde.org>
0003  *
0004  * This program is free software; you can redistribute it and/or
0005  * modify it under the terms of the GNU General Public License as
0006  * published by the Free Software Foundation; either version 2 of
0007  * the License, or (at your option) any later version.
0008  *
0009  * This program is distributed in the hope that it will be useful,
0010  * but WITHOUT ANY WARRANTY; without even the implied warranty of
0011  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
0012  * GNU General Public License for more details.
0013  *
0014  * You should have received a copy of the GNU General Public License
0015  * along with this program.  If not, see <http://www.gnu.org/licenses/>.
0016  */
0017 
0018 #include "gypsysolver.h"
0019 
0020 // own
0021 #include "../gypsy.h"
0022 #include "../kpat_debug.h"
0023 /// Std
0024 #include <cassert>
0025 
0026 #define PRINT 0
0027 
0028 #define suitable(a, b) (COLOR(a) != COLOR(b))
0029 
0030 /* These two routines make and unmake moves. */
0031 
0032 void GypsySolver::make_move(MOVE *m)
0033 {
0034 #if PRINT
0035     // qCDebug(KPAT_LOG) << "\n\nmake_move\n";
0036     if (m->totype == O_Type)
0037         fprintf(stderr, "move %d from %d out (at %d) Prio: %d\n\n", m->card_index, m->from, m->turn_index, m->pri);
0038     else
0039         fprintf(stderr, "move %d from %d to %d (%d) Prio: %d\n\n", m->card_index, m->from, m->to, m->turn_index, m->pri);
0040     print_layout();
0041 #else
0042     // print_layout();
0043 #endif
0044 
0045     int from, to;
0046     // card_t card = NONE;
0047 
0048     from = m->from;
0049     to = m->to;
0050 
0051     if (m->from == deck) {
0052         for (int i = 0; i < 8; ++i) {
0053             card_t card = *Wp[from];
0054             card = (SUIT(card) << 4) + RANK(card);
0055             ++Wp[i];
0056             *Wp[i] = card;
0057             --Wp[from];
0058             Wlen[i]++;
0059             hashpile(i);
0060             Wlen[from]--;
0061         }
0062         hashpile(from);
0063 #if PRINT
0064         print_layout();
0065 #endif
0066         return;
0067     }
0068 
0069     card_t card = NONE;
0070     for (int l = m->card_index; l >= 0; --l) {
0071         card = W[from][Wlen[from] - l - 1];
0072         Wp[from]--;
0073         if (m->totype != O_Type) {
0074             Wp[to]++;
0075             *Wp[to] = card;
0076             Wlen[to]++;
0077         }
0078     }
0079     Wlen[from] -= m->card_index + 1;
0080 
0081     if (m->turn_index == 0) {
0082         if (DOWN(card))
0083             card = (SUIT(card) << 4) + RANK(card);
0084         else
0085             card += (1 << 7);
0086         W[to][Wlen[to] - m->card_index - 1] = card;
0087     } else if (m->turn_index != -1) {
0088         card_t card2 = *Wp[from];
0089         if (DOWN(card2))
0090             card2 = (SUIT(card2) << 4) + RANK(card2);
0091         *Wp[from] = card2;
0092     }
0093 
0094     hashpile(from);
0095     /* Add to pile. */
0096 
0097     if (m->totype == O_Type) {
0098         if (Wlen[to])
0099             *Wp[to] = card;
0100         else {
0101             Wp[to]++;
0102             Wlen[to]++;
0103             *Wp[to] = card;
0104         }
0105         Q_ASSERT(m->card_index == 0);
0106     }
0107     hashpile(to);
0108 
0109 #if PRINT
0110     print_layout();
0111 #endif
0112 }
0113 
0114 void GypsySolver::undo_move(MOVE *m)
0115 {
0116 #if PRINT
0117     // qCDebug(KPAT_LOG) << "\n\nundo_move\n";
0118     if (m->totype == O_Type)
0119         fprintf(stderr, "move %d from %d out (at %d)\n\n", m->card_index, m->from, m->turn_index);
0120     else
0121         fprintf(stderr, "move %d from %d to %d (%d)\n\n", m->card_index, m->from, m->to, m->turn_index);
0122     print_layout();
0123 
0124 #endif
0125     int from, to;
0126     // card_t card;
0127 
0128     from = m->from;
0129     to = m->to;
0130 
0131     if (m->from == deck) {
0132         for (int i = 7; i >= 0; --i) {
0133             card_t card = *Wp[i];
0134             Q_ASSERT(!DOWN(card));
0135             card = (SUIT(card) << 4) + RANK(card) + (1 << 7);
0136             ++Wp[from];
0137             --Wp[i];
0138             *Wp[from] = card;
0139             Wlen[from]++;
0140             Wlen[i]--;
0141             hashpile(i);
0142         }
0143         hashpile(from);
0144 #if PRINT
0145         print_layout();
0146 #endif
0147         return;
0148     }
0149 
0150     /* Add to 'from' pile. */
0151     if (m->turn_index > 0) {
0152         card_t card2 = *Wp[from];
0153         if (!DOWN(card2))
0154             card2 = (SUIT(card2) << 4) + RANK(card2) + (1 << 7);
0155         *Wp[from] = card2;
0156     }
0157 
0158     card_t card = NONE;
0159 
0160     if (m->totype == O_Type) {
0161         card = *Wp[to];
0162         if (RANK(card) == PS_ACE) {
0163             Wlen[to] = 0;
0164         } else {
0165             *Wp[to] = card - 1; // SUIT( card ) << 4 + RANK( card ) - 1;
0166         }
0167         Wp[from]++;
0168         *Wp[from] = card;
0169         Wlen[from]++;
0170         hashpile(to);
0171     } else {
0172         for (int l = m->card_index; l >= 0; --l) {
0173             card = W[to][Wlen[to] - l - 1];
0174             Wp[from]++;
0175             *Wp[from] = card;
0176             Wlen[from]++;
0177             Wp[to]--;
0178         }
0179         Wlen[to] -= m->card_index + 1;
0180         hashpile(to);
0181     }
0182 
0183     if (m->turn_index == 0) {
0184         card_t card = *Wp[from];
0185         if (DOWN(card))
0186             card = (SUIT(card) << 4) + RANK(card);
0187         else
0188             card += (1 << 7);
0189         *Wp[from] = card;
0190     }
0191 
0192     hashpile(from);
0193 
0194 #if PRINT
0195     print_layout();
0196 #endif
0197 }
0198 
0199 /* Automove logic.  Gypsy games must avoid certain types of automoves. */
0200 
0201 int GypsySolver::good_automove(int o, int r)
0202 {
0203     int i;
0204 
0205     if (r <= 2) {
0206         return true;
0207     }
0208 
0209     /* Check the Out piles of opposite color. */
0210     int red_piles[] = {0, 1, 4, 5};
0211     int black_piles[] = {2, 3, 6, 7};
0212 
0213     for (i = 0; i < 4; ++i) {
0214         int pile = 0;
0215         if (COLOR(o) == PS_BLACK)
0216             pile = red_piles[i] + outs;
0217         else
0218             pile = black_piles[i] + outs;
0219         if (!Wlen[pile] || RANK(*Wp[pile]) < r - 1) {
0220             /* Not all the N-1's of opposite color are out
0221                yet.  We can still make an automove if either
0222                both N-2's are out or the other same color N-3
0223                is out (Raymond's rule).  Note the re-use of
0224                the loop variable i.  We return here and never
0225                make it back to the outer loop. */
0226 
0227             for (i = 0; i < 4; ++i) {
0228                 if (COLOR(o) == PS_BLACK)
0229                     pile = red_piles[i] + outs;
0230                 else
0231                     pile = black_piles[i] + outs;
0232                 if (!Wlen[pile] || RANK(*Wp[pile]) < r - 2)
0233                     return false;
0234             }
0235 
0236             for (i = 0; i < 4; ++i) {
0237                 if (COLOR(o) == PS_BLACK)
0238                     pile = black_piles[i] + outs;
0239                 else
0240                     pile = red_piles[i] + outs;
0241                 if (!Wlen[pile] || RANK(*Wp[pile]) < r - 3)
0242                     return false;
0243             }
0244 
0245             return true;
0246         }
0247     }
0248 
0249     return true;
0250 }
0251 
0252 /* Get the possible moves from a position, and store them in Possible[]. */
0253 
0254 int GypsySolver::get_possible_moves(int *a, int *numout)
0255 {
0256     MOVE *mp;
0257 
0258     /* Check for moves from W to O. */
0259 
0260     int n = 0;
0261     mp = Possible;
0262     for (int w = 0; w < 8; ++w) {
0263         if (Wlen[w] > 0) {
0264             card_t card = *Wp[w];
0265             int o = SUIT(card);
0266             for (int off = 0; off < 2; ++off) {
0267                 bool empty = !Wlen[o * 2 + off + outs];
0268                 if ((empty && (RANK(card) == PS_ACE)) || (!empty && (RANK(card) == RANK(*Wp[outs + o * 2 + off]) + 1))) {
0269                     mp->card_index = 0;
0270                     mp->from = w;
0271                     mp->to = outs + o * 2 + off;
0272                     mp->totype = O_Type;
0273                     mp->pri = params[4];
0274                     mp->turn_index = -1;
0275                     if (Wlen[w] > 1 && DOWN(W[w][Wlen[w] - 2]))
0276                         mp->turn_index = 1;
0277                     n++;
0278                     mp++;
0279 
0280                     /* If it's an automove, just do it. */
0281 
0282                     if (params[4] == 127 || good_automove(o, RANK(card))) {
0283                         *a = true;
0284                         mp[-1].pri = 127;
0285                         if (n != 1)
0286                             Possible[0] = mp[-1];
0287                         return 1;
0288                     }
0289                 }
0290             }
0291         }
0292     }
0293 
0294     /* No more automoves, but remember if there were any moves out. */
0295 
0296     *a = false;
0297     *numout = n;
0298 
0299     for (int i = 0; i < 8; ++i) {
0300         int len = Wlen[i];
0301         for (int l = 0; l < len; ++l) {
0302             card_t card = W[i][Wlen[i] - 1 - l];
0303             if (DOWN(card))
0304                 break;
0305 
0306             if (l > 0) {
0307                 card_t card_on_top = W[i][Wlen[i] - l];
0308                 if (RANK(card) != RANK(card_on_top) + 1)
0309                     break;
0310                 if (!suitable(card, card_on_top))
0311                     break;
0312             }
0313 
0314             bool wasempty = false;
0315             for (int j = 0; j < 8; ++j) {
0316                 if (i == j)
0317                     continue;
0318 
0319                 bool allowed = false;
0320 
0321                 if (Wlen[j] > 0 && suitable(card, *Wp[j]) && RANK(card) == RANK(*Wp[j]) - 1) {
0322                     allowed = true;
0323                 }
0324                 if (Wlen[j] == 0 && !wasempty) {
0325                     if (l != Wlen[i] - 1) {
0326                         allowed = true;
0327                         wasempty = true;
0328                     }
0329                 }
0330 
0331                 if (!allowed)
0332                     continue;
0333 
0334                 mp->card_index = l;
0335                 mp->from = i;
0336                 mp->to = j;
0337                 mp->totype = W_Type;
0338                 mp->turn_index = -1;
0339                 mp->pri = params[3];
0340                 if (Wlen[i] >= 2 + l) {
0341                     assert(Wlen[i] - 2 - l >= 0);
0342                     card_t card2 = W[i][Wlen[i] - 2 - l];
0343                     if (DOWN(card2)) {
0344                         mp->turn_index = 1;
0345                         mp->pri = params[2];
0346                     }
0347                     if (Wlen[i] >= l + 2 && RANK(card) == RANK(card2) - 1 && COLOR(card) != COLOR(card2) && !DOWN(card2)) {
0348                         int o = SUIT(card2);
0349                         for (int off = 0; off < 2; ++off) {
0350                             bool empty = !Wlen[o * 2 + off + outs];
0351                             if ((empty && (RANK(card2) == PS_ACE)) || (!empty && (RANK(card2) == RANK(*Wp[outs + o * 2 + off]) + 1))) {
0352                                 o = -1;
0353                                 break;
0354                             }
0355                         }
0356                         if (o > -1)
0357                             mp->pri = -117;
0358                         else
0359                             mp->pri = (int)qMin(qreal(127.), params[1] + qreal(l) * params[5] / 10);
0360                     }
0361                 }
0362 
0363                 n++;
0364                 mp++;
0365                 // leave one for redeal
0366                 if (n >= MAXMOVES - 2)
0367                     goto redeal;
0368             }
0369         }
0370     }
0371 
0372 redeal:
0373     if (Wlen[deck]) {
0374         /* check for redeal */
0375         mp->card_index = 0;
0376         mp->from = deck;
0377         mp->to = 0; // unused
0378         mp->totype = W_Type;
0379         mp->pri = params[0];
0380         mp->turn_index = -1;
0381         n++;
0382         mp++;
0383     }
0384 
0385     assert(n < MAXMOVES);
0386     return n;
0387 }
0388 
0389 bool GypsySolver::isWon()
0390 {
0391     // maybe won?
0392     for (int o = 0; o < 8; ++o) {
0393         if ((Wlen[outs + o] == 0) || (RANK(*Wp[outs + o]) != PS_KING))
0394             return false;
0395     }
0396 
0397     return true;
0398 }
0399 
0400 int GypsySolver::getOuts()
0401 {
0402     int k = 0;
0403     for (int o = 0; o < 8; ++o)
0404         if (Wlen[outs + o])
0405             k += RANK(*Wp[outs + o]);
0406 
0407     return k;
0408 }
0409 
0410 GypsySolver::GypsySolver(const Gypsy *dealer)
0411     : Solver()
0412 {
0413     deal = dealer;
0414 
0415     char buffer[10];
0416     params[0] = 3;
0417     params[1] = 3;
0418     params[2] = 44;
0419     params[3] = 19;
0420     params[4] = 5;
0421     params[5] = 10;
0422     for (int i = 1; i <= 6; ++i) {
0423         sprintf(buffer, "DECK%d", i);
0424         const QByteArray env = qgetenv(buffer);
0425         if (!env.isEmpty())
0426             params[i - 1] = env.toInt();
0427     }
0428 }
0429 
0430 void GypsySolver::translate_layout()
0431 {
0432     /* Read the workspace. */
0433     for (int w = 0; w < 8; ++w) {
0434         int i = translate_pile(deal->store[w], W[w], 52);
0435         Wp[w] = &W[w][i - 1];
0436         Wlen[w] = i;
0437     }
0438 
0439     deck = 8;
0440     int i = translate_pile(deal->talon, W[deck], 80);
0441     Wp[deck] = &W[deck][i - 1];
0442     Wlen[deck] = i;
0443 
0444     outs = 9;
0445 
0446     /* Output piles, if any. */
0447     for (int i = 0; i < 8; ++i) {
0448         Wlen[outs + i] = 0;
0449         Wp[outs + i] = &W[outs + i][-1];
0450     }
0451 
0452     for (int i = 0; i < 8; ++i) {
0453         KCard *c = deal->target[i]->topCard();
0454         if (c) {
0455             int suit = translateSuit(c->suit()) >> 4;
0456             int target = outs + suit * 2;
0457             if (Wlen[target])
0458                 target++;
0459             Wp[target]++;
0460             Wlen[target]++;
0461             *Wp[target] = (suit << 4) + c->rank();
0462         }
0463     }
0464 }
0465 
0466 void GypsySolver::print_layout()
0467 {
0468     int i, w, o;
0469 
0470     fprintf(stderr, "print-layout-begin\n");
0471     for (w = 0; w < 8; ++w) {
0472         fprintf(stderr, "Play%d: ", w);
0473         for (i = 0; i < Wlen[w]; ++i) {
0474             printcard(W[w][i], stderr);
0475         }
0476         fputc('\n', stderr);
0477     }
0478     fprintf(stderr, "Off: ");
0479     for (o = 0; o < 8; ++o) {
0480         if (Wlen[outs + o])
0481             printcard(*Wp[outs + o], stderr);
0482     }
0483     fprintf(stderr, "\nDeck: ");
0484     for (i = 0; i < Wlen[deck]; ++i)
0485         printcard(W[deck][i], stderr);
0486 
0487     fprintf(stderr, "\nprint-layout-end\n");
0488     return;
0489 }
0490 
0491 MoveHint GypsySolver::translateMove(const MOVE &m)
0492 {
0493     // print_layout();
0494     if (m.from == deck)
0495         return MoveHint();
0496 
0497     PatPile *frompile = deal->store[m.from];
0498     KCard *card = frompile->at(frompile->count() - m.card_index - 1);
0499 
0500     if (m.totype == O_Type) {
0501         PatPile *target = nullptr;
0502         PatPile *empty = nullptr;
0503         for (int i = 0; i < 8; ++i) {
0504             KCard *c = deal->target[i]->topCard();
0505             if (c) {
0506                 if (c->suit() == card->suit() && c->rank() == card->rank() - 1) {
0507                     target = deal->target[i];
0508                     break;
0509                 }
0510             } else if (!empty)
0511                 empty = deal->target[i];
0512         }
0513         if (!target)
0514             target = empty;
0515         return MoveHint(card, target, m.pri);
0516     }
0517 
0518     return MoveHint(card, deal->store[m.to], m.pri);
0519 }