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 }