1 /*
2 * Copyright (C) 2006-2009 Stephan Kulow <coolo@kde.org>
3 *
4 * This program is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU General Public License as
6 * published by the Free Software Foundation; either version 2 of
7 * the License, or (at your option) any later version.
8 *
9 * This program is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
13 *
14 * You should have received a copy of the GNU General Public License
15 * along with this program. If not, see <http://www.gnu.org/licenses/>.
16 */
17
18 #include "fortyeightsolver.h"
19
20 // own
21 #include "../fortyeight.h"
22 #include "../kpat_debug.h"
23
24 namespace {
25 constexpr auto NUM_PILE = 8;
26 constexpr auto NUM_DECK = 9;
27 }
28
29 #define PRINT 0
30
31 class FortyeightSolverState {
32 public:
33 bool empty[8];
34 bool linedup[8];
35 int highestbreak[8];
36 int firstempty;
37 int freestores;
38 int fromscore[8];
39 };
40
checkState(FortyeightSolverState & d)41 void FortyeightSolver::checkState(FortyeightSolverState &d)
42 {
43 d.firstempty = -1;
44 d.freestores = 0;
45
46 for ( int w = 0; w < 8; w++ )
47 {
48 d.empty[w] = (Wlen[w] == 0);
49 d.linedup[w] = true;
50 if ( !Wlen[w] )
51 {
52 d.freestores++;
53 if (d.firstempty < 0) d.firstempty = w;
54 }
55 d.highestbreak[w] = 0;
56 for (int i = 1; i < Wlen[w]; i++)
57 {
58 card_t card1 = W[w][Wlen[w]-i-1];
59 card_t card2 = W[w][Wlen[w]-i];
60 if ( SUIT( card1 ) != SUIT( card2 ) ||
61 RANK( card1 ) != RANK( card2 ) + 1 )
62 {
63 d.highestbreak[w] = i - 1;
64 d.linedup[w] = false;
65 break;
66 }
67 }
68 d.fromscore[w] = 0;
69 for (int i = d.highestbreak[w] + 1; i < Wlen[w]; i++)
70 {
71 card_t card = W[w][Wlen[w]-i-1];
72 if ( RANK(card) < 5 || RANK(card) == PS_ACE) {
73 d.fromscore[w] += (13 - RANK(card)) * 20;
74 }
75 }
76 if (Wlen[w])
77 d.fromscore[w] /= Wlen[w];
78 }
79 }
80
make_move(MOVE * m)81 void FortyeightSolver::make_move(MOVE *m)
82 {
83 #if PRINT
84 if ( m->totype == O_Type )
85 fprintf( stderr, "\nmake move %d from %d to %d out (at %d)\n\n", m->card_index, m->from, m->to, m->turn_index );
86 else
87 fprintf( stderr, "\nmake move %d from %d to %d (%d)\n\n", m->card_index, m->from, m->to, m->turn_index );
88 print_layout();
89 #endif
90
91 int from = m->from;
92 int to = m->to;
93
94 // move to pile
95 if ( from == NUM_DECK && to == NUM_PILE )
96 {
97 card_t card = *Wp[NUM_DECK];
98 Wp[NUM_DECK]--;
99 Wlen[NUM_DECK]--;
100 card = ( SUIT( card ) << 4 ) + RANK( card );
101 Wp[NUM_PILE]++;
102 *Wp[NUM_PILE] = card;
103 Wlen[NUM_PILE]++;
104 hashpile( NUM_DECK );
105 hashpile( NUM_PILE );
106 #if PRINT
107 print_layout();
108 #endif
109 return;
110 }
111
112 // move to deck
113 if ( from == NUM_PILE && to == NUM_DECK )
114 {
115 while ( Wlen[NUM_PILE] > 1 )
116 {
117 Wlen[NUM_DECK]++;
118 Wp[NUM_DECK]++;
119 card_t card = *Wp[NUM_PILE] + ( 1 << 7 );
120 *Wp[NUM_DECK] = card;
121 Wlen[NUM_PILE]--;
122 Wp[NUM_PILE]--;
123 }
124 hashpile( NUM_DECK );
125 hashpile( NUM_PILE );
126 lastdeal = true;
127 #if PRINT
128 print_layout();
129 #endif
130 return;
131 }
132
133 for ( int i = m->card_index + 1; i > 0; --i )
134 {
135 card_t card = W[from][Wlen[from]-i];
136 Wp[from]--;
137
138 if ( m->totype == O_Type )
139 {
140 O[to]++;
141 }
142 else
143 {
144 Wp[to]++;
145 *Wp[to] = card;
146 Wlen[to]++;
147 }
148 }
149 Wlen[from] -= m->card_index+1;
150
151 hashpile(from);
152 if ( m->totype != O_Type )
153 hashpile(to);
154 #if PRINT
155 print_layout();
156 #endif
157 }
158
undo_move(MOVE * m)159 void FortyeightSolver::undo_move(MOVE *m)
160 {
161 #if PRINT
162 if ( m->totype == O_Type )
163 fprintf( stderr, "\nundo move %d from %d to %d out (at %d)\n\n", m->card_index, m->from, m->to, m->turn_index );
164 else
165 fprintf( stderr, "\nundo move %d from %d to %d (%d)\n\n", m->card_index, m->from, m->to, m->turn_index );
166 print_layout();
167 #endif
168
169 int from = m->from;
170 int to = m->to;
171
172 // move to pile
173 if ( from == NUM_DECK && to == NUM_PILE )
174 {
175 card_t card = *Wp[NUM_PILE];
176 Wp[NUM_PILE]--;
177 Wlen[NUM_PILE]--;
178 card = ( SUIT( card ) << 4 ) + RANK( card ) + ( 1 << 7 );
179 Wp[NUM_DECK]++;
180 *Wp[NUM_DECK] = card;
181 Wlen[NUM_DECK]++;
182 hashpile( NUM_DECK );
183 hashpile( NUM_PILE );
184 #if PRINT
185 print_layout();
186 #endif
187 return;
188 }
189
190 // move to deck
191 if ( from == NUM_PILE && to == NUM_DECK )
192 {
193 while ( Wlen[NUM_DECK] )
194 {
195 Wlen[NUM_PILE]++;
196 Wp[NUM_PILE]++;
197 *Wp[NUM_PILE] = ( SUIT( *Wp[NUM_DECK] ) << 4 ) + RANK( *Wp[NUM_DECK] );
198 Wlen[NUM_DECK]--;
199 Wp[NUM_DECK]--;
200 }
201 hashpile( NUM_DECK );
202 hashpile( NUM_PILE );
203 lastdeal = false;
204 #if PRINT
205 print_layout();
206 #endif
207 return;
208 }
209
210 for ( int i = m->card_index + 1; i > 0; --i )
211 {
212
213 card_t card;
214 if ( m->totype != O_Type )
215 {
216 card = W[to][Wlen[to]-i];
217 Wp[to]--;
218 }
219 else
220 {
221 card = Osuit[to] + O[to];
222 O[to]--;
223 }
224
225 Wp[from]++;
226 *Wp[from] = card;
227 Wlen[from]++;
228 }
229
230 hashpile(from);
231 if ( m->totype != O_Type ) {
232 Wlen[to] -= m->card_index+1;
233 hashpile(to);
234 }
235 #if PRINT
236 print_layout();
237 #endif
238 }
239
checkMoveOut(int from,MOVE * mp,int * dropped)240 bool FortyeightSolver::checkMoveOut( int from, MOVE *mp, int *dropped)
241 {
242 if ( !Wlen[from] )
243 return false;
244
245 card_t card = *Wp[from];
246 int suit = SUIT( card );
247
248 int target = suit * 2;
249
250 // aces need to fit on empty
251 if ( RANK(card) == PS_ACE )
252 {
253 if (O[target++] != NONE)
254 target--;
255 else if ( O[target] != NONE)
256 return false;
257 }
258 else
259 {
260 if ( RANK(card) == O[target++] + 1 )
261 target--;
262 else if ( RANK(card) != O[target] + 1 )
263 return false;
264 }
265
266 dropped[target]++;
267 mp->card_index = 0;
268 mp->from = from;
269 mp->to = target;
270 mp->totype = O_Type;
271 mp->pri = 127;
272 mp->turn_index = -1;
273 return true;
274
275 }
276
277 /* Get the possible moves from a position, and store them in Possible[]. */
checkMove(int from,int to,MOVE * mp)278 bool FortyeightSolver::checkMove( int from, int to, MOVE *mp )
279 {
280 if ( !Wlen[from] )
281 return false;
282
283 card_t card = *Wp[from];
284 Q_ASSERT( to < 8 );
285
286 if ( Wlen[to] )
287 {
288 card_t top = *Wp[to];
289 if ( SUIT( top ) != SUIT( card ) ||
290 RANK( top ) != RANK( card ) + 1 )
291 return false;
292 }
293
294 mp->card_index = 0;
295 mp->from = from;
296 mp->to = to;
297 mp->totype = W_Type;
298 mp->pri = 70;
299 mp->turn_index = -1;
300 return true;
301 }
302
get_possible_moves(int * a,int * numout)303 int FortyeightSolver::get_possible_moves(int *a, int *numout)
304 {
305 int n = 0;
306 MOVE *mp = Possible;
307
308 *a = false;
309
310 FortyeightSolverState d;
311 checkState(d);
312
313 //print_layout();
314 // if a specific target got two possible drops, we don't make it auto drop
315 int dropped[8] = { 0, 0, 0, 0, 0, 0, 0, 0};
316
317 // off
318 for ( int w = 0; w < 8; w++ )
319 {
320 if ( checkMoveOut( w, mp, dropped ) )
321 {
322 n++;
323 mp++;
324 break;
325 }
326 }
327 if ( checkMoveOut( NUM_PILE, mp, dropped ) )
328 {
329 n++;
330 mp++;
331 }
332
333 for ( int i = 0; i < 8; i++ )
334 {
335 if ( dropped[i] > 1 )
336 {
337 for ( int j = 0; j < n; j++ )
338 if ( Possible[j].to == i )
339 Possible[j].pri = qBound( 121, 110 + Wlen[Possible[j].from], 126 );
340 }
341 if ( dropped[i] == 1 )
342 {
343 // good automove
344 if (n != 1)
345 {
346 for ( int j = 0; j < n; j++ )
347 {
348 if ( Possible[j].to == i )
349 {
350 Possible[0] = Possible[j];
351 Possible[0].pri = 127;
352 break;
353 }
354 }
355 }
356 *a = true;
357 *numout = 1;
358 return 1;
359 }
360 }
361
362 //fprintf(stderr, "\n");
363 *numout = n;
364
365 for (int w = 0; w < 8; w++)
366 {
367 for ( int j = 0; j < 8; j++ )
368 {
369 if ( j == w )
370 continue;
371 if ( checkMove( w, j, mp ) )
372 {
373 if ( !Wlen[j] )
374 {
375 if (d.linedup[w])
376 continue; // ignore it
377
378 if ( j != d.firstempty ) // one is enough
379 continue;
380 if ( d.highestbreak[w] >= 1)
381 continue;
382 mp->pri = qMin( 115, 11 + d.fromscore[w]);
383 } else {
384 if (d.linedup[w] && Wlen[w] > 1)
385 continue;
386 if (d.linedup[j] && Wlen[j] > 1)
387 mp->pri = 110 + Wlen[j];
388 else {
389 if (d.fromscore[w] < d.fromscore[j])
390 mp->pri = 2;
391 else
392 mp->pri = qMin(115, 20 + d.highestbreak[w] + RANK(*Wp[w]) + d.fromscore[w]);
393 }
394 }
395
396 n++;
397 mp++;
398 }
399 }
400 if ( checkMove( NUM_PILE, w, mp ) && (!d.empty[w] || w == d.firstempty))
401 {
402 if (d.empty[w])
403 mp->pri = 15;
404 else {
405 if (d.linedup[w])
406 mp->pri = 100;
407 else
408 mp->pri = qMax(50 - d.fromscore[w], 0);
409 }
410 n++;
411 mp++;
412 }
413 if ( Wlen[w] > 1 && d.freestores )
414 {
415 // Column w has two or more cards and there is at least one empty
416 // column, so we can try for multi-card moves from w to other cols.
417 // This is valid only if ALL the cards to move are of the same
418 // suit and in ascending sequence, starting with the top two cards.
419 const card_t nextw = W[w][Wlen[w]-2]; // Next card after top.
420 const bool possMultiMove = ( SUIT( nextw ) == SUIT( *Wp[w] ) ) &&
421 ( ( RANK( nextw ) - RANK( *Wp[w] ) ) == 1 );
422 if ( possMultiMove )
423 {
424 //print_layout();
425
426 for ( int to = 0; to < 8; to++ )
427 {
428 if ( to == w )
429 continue;
430 if ( Wlen[to] && SUIT( *Wp[to] ) != SUIT( *Wp[w] ) )
431 continue;
432 if ( d.empty[to] && to != d.firstempty )
433 continue;
434 int moves = 1 << d.freestores;
435 if ( !Wlen[to] )
436 moves = 1 << ( d.freestores - 1 );
437
438 if ( moves >= Wlen[w] )
439 moves = Wlen[w];
440
441 bool switched = false;
442 for ( int i = 2; i < moves; ++i )
443 {
444 /* printcard( W[w][Wlen[w]-i-1], stderr );
445 printcard( *Wp[w], stderr );
446 fprintf( stderr, " switch? %d\n", i ); */
447 if ( SUIT( W[w][Wlen[w]-i-1] ) != SUIT( *Wp[w] ) ||
448 RANK ( W[w][Wlen[w]-i-1] ) != RANK ( W[w][Wlen[w]-i] ) + 1)
449 {
450 switched = true;
451 moves = i;
452 break;
453 }
454 }
455 if ( !Wlen[to] )
456 {
457 if ( moves < 2 || moves == Wlen[w] || !switched)
458 continue;
459 //print_layout();
460 mp->card_index = moves-1;
461 mp->from = w;
462 mp->to = to;
463 mp->totype = W_Type;
464 mp->pri = 60;
465 mp->turn_index = -1;
466 n++;
467 mp++;
468 continue;
469 }
470 if (d.linedup[w] && moves < Wlen[w])
471 continue;
472 card_t top = *Wp[to];
473 for ( int i = 2; i <= moves && i <= Wlen[w]; i++ )
474 {
475 card_t cur = W[w][Wlen[w]-i];
476 /* printcard( top, stderr );
477 printcard( cur, stderr );
478 fprintf( stderr, " %d\n", i ); */
479 Q_ASSERT( SUIT( top ) == SUIT( cur ) );
480 if ( RANK( top ) == RANK( cur ) + 1 )
481 {
482 mp->card_index = i-1;
483 mp->from = w;
484 mp->to = to;
485 mp->totype = W_Type;
486 mp->pri = 80;
487 mp->turn_index = -1;
488 n++;
489 mp++;
490 }
491 }
492 }
493 }
494 }
495 }
496 /* check for deck->pile */
497 if ( Wlen[NUM_DECK] ) {
498 mp->card_index = 1;
499 mp->from = NUM_DECK;
500 mp->to = NUM_PILE;
501 mp->totype = W_Type;
502 mp->pri = 19;
503 mp->turn_index = 0;
504 n++;
505 mp++;
506 } else if ( !lastdeal )
507 {
508 mp->card_index = 1;
509 mp->from = NUM_PILE;
510 mp->to = NUM_DECK;
511 mp->totype = W_Type;
512 mp->pri = 19;
513 mp->turn_index = 0;
514 n++;
515 mp++;
516 }
517
518 return n;
519 }
520
unpack_cluster(unsigned int k)521 void FortyeightSolver::unpack_cluster( unsigned int k )
522 {
523 O[0] = k & 0xF;
524 k >>= 4;
525 O[1] = k & 0xF;
526 k >>= 4;
527 O[2] = k & 0xF;
528 k >>= 4;
529 O[3] = k & 0xF;
530 k >>= 4;
531 O[4] = k & 0xF;
532 k >>= 4;
533 O[5] = k & 0xF;
534 k >>= 4;
535 O[6] = k & 0xF;
536 k >>= 4;
537 O[7] = k & 0xF;
538 }
539
isWon()540 bool FortyeightSolver::isWon()
541 {
542 for ( int i = 0; i < 8; ++i )
543 if ( O[i] != PS_KING )
544 return false;
545 //qCDebug(KPAT_LOG) << "isWon" << getOuts();
546 return true;
547 }
548
getOuts()549 int FortyeightSolver::getOuts()
550 {
551 int total = 0;
552 for ( int i = 0; i < 8; ++i )
553 total += O[i];
554 return total;
555 }
556
FortyeightSolver(const Fortyeight * dealer)557 FortyeightSolver::FortyeightSolver(const Fortyeight *dealer)
558 : Solver()
559 {
560 deal = dealer;
561 }
562
translate_layout()563 void FortyeightSolver::translate_layout()
564 {
565 /* Read the workspace. */
566
567 int total = 0;
568 for ( int w = 0; w < 8; ++w ) {
569 int i = translate_pile(deal->stack[w], W[w], 52);
570 Wp[w] = &W[w][i - 1];
571 Wlen[w] = i;
572 total += i;
573 }
574
575 /* Output piles, if any. */
576 for (int i = 0; i < 8; ++i) {
577 O[i] = NONE;
578 }
579 Osuit[0] = PS_DIAMOND;
580 Osuit[1] = PS_DIAMOND;
581 Osuit[2] = PS_CLUB;
582 Osuit[3] = PS_CLUB;
583 Osuit[4] = PS_HEART;
584 Osuit[5] = PS_HEART;
585 Osuit[6] = PS_SPADE;
586 Osuit[7] = PS_SPADE;
587
588 for (int i = 0; i < 8; ++i) {
589 KCard *c = deal->target[i]->topCard();
590 if (c) {
591 int suit = translateSuit( c->suit() ) >> 4;
592 if (O[suit * 2] == NONE)
593 O[suit * 2] = c->rank();
594 else {
595 if (O[suit * 2] < c->rank()) {
596 O[suit * 2 + 1] = O[suit * 2];
597 O[suit * 2] = c->rank();
598 } else {
599 O[suit * 2 + 1] = c->rank();
600 }
601 }
602 total += c->rank();
603 }
604 }
605 int i = translate_pile( deal->pile, W[NUM_PILE], 80 );
606 Wp[NUM_PILE] = &W[NUM_PILE][i-1];
607 Wlen[NUM_PILE] = i;
608 total += i;
609
610 i = translate_pile( deal->talon, W[NUM_DECK], 80 );
611 Wp[NUM_DECK] = &W[NUM_DECK][i-1];
612 Wlen[NUM_DECK] = i;
613 total += i;
614
615 lastdeal = deal->lastdeal;
616
617 Q_ASSERT( total == 104 );
618 }
619
getClusterNumber()620 unsigned int FortyeightSolver::getClusterNumber()
621 {
622 unsigned int i = O[0] + (O[1] << 4);
623 unsigned int k = i;
624 i = O[2] + (O[3] << 4);
625 k |= i << 8;
626 i = O[4] + (O[5] << 4);
627 k |= i << 16;
628 i = O[6] + (O[7] << 4);
629 k |= i << 24;
630 return k;
631 }
632
translateMove(const MOVE & m)633 MoveHint FortyeightSolver::translateMove( const MOVE &m )
634 {
635 if ( m.from == NUM_DECK || m.to == NUM_DECK )
636 return MoveHint();
637 PatPile *frompile = nullptr;
638 if ( m.from < 8 )
639 frompile = deal->stack[m.from];
640 else
641 frompile = deal->pile;
642
643 Q_ASSERT( frompile );
644 KCard *card = frompile->at( frompile->count() - m.card_index - 1);
645 Q_ASSERT( card );
646 Q_ASSERT( m.to < NUM_PILE );
647 if ( m.totype == W_Type)
648 return MoveHint( card, deal->stack[m.to], m.pri );
649
650 for (int i = 0; i < 8; i++) {
651 KCard *top = deal->target[i]->topCard();
652 if (top) {
653 if (top->suit() == card->suit() && top->rank() + 1 == card->rank())
654 return MoveHint( card, deal->target[i], m.pri );
655 } else {
656 if (card->rank() == PS_ACE)
657 return MoveHint( card, deal->target[i], m.pri );
658 }
659 }
660 Q_ASSERT( false);
661 return MoveHint();
662 }
663
print_layout()664 void FortyeightSolver::print_layout()
665 {
666 FortyeightSolverState d;
667 checkState(d);
668
669 fprintf(stderr, "print-layout-begin\n");
670 for (int w = 0; w < 10; w++) {
671 if ( w == NUM_DECK )
672 fprintf( stderr, "Deck(9): " );
673 else if ( w == 8 )
674 fprintf( stderr, "Pile(8): " );
675 else if ( w < 8 )
676 fprintf( stderr, "Play%d: ", w );
677 for (int i = 0; i < Wlen[w]; i++) {
678 printcard(W[w][i], stderr);
679 }
680 fputc('\n', stderr);
681 }
682 fprintf( stderr, "Off: " );
683 for (int o = 0; o < 8; ++o) {
684 printcard(O[o] + Osuit[o], stderr);
685 }
686 fprintf( stderr, "\nLast-Deal: %d\n", lastdeal );
687 #if 1
688 fprintf( stderr, "FE: %d FS: %d\n", d.firstempty, d.freestores);
689 for (int o = 0; o < 8; ++o) {
690 fprintf( stderr, "Pile%d: empty:%d linedup:%d highestbreak:%d fromscore:%d\n", o, d.empty[o], d.linedup[o], d.highestbreak[o], d.fromscore[o]);
691 }
692 #endif
693 fprintf(stderr, "print-layout-end\n");
694 }
695