diff --git a/main.cpp b/main.cpp index 41be805..b14e9c9 100644 --- a/main.cpp +++ b/main.cpp @@ -1,148 +1,148 @@ /* patience -- main program Copyright (C) 1995 Paul Olav Tvete * Permission to use, copy, modify, and distribute this software and its * documentation for any purpose and without fee is hereby granted, * provided that the above copyright notice appear in all copies and that * both that copyright notice and this permission notice appear in * supporting documentation. * * This file is provided AS IS with no warranties of any kind. The author * shall have no liability with respect to the infringement of copyrights, * trade secrets or any patents by this file or any part thereof. In no * event will the author be liable for any lost revenue or profits or * other special, indirect and consequential damages. */ #include #include #include #include #include #include #include #include #include #include #include "version.h" #include "pwidget.h" #include "dealer.h" #include "patsolve/patsolve.h" #include "cardmaps.h" static const char description[] = I18N_NOOP("KDE Patience Game"); static KCmdLineOptions options[] = { { "solve ", I18N_NOOP("Dealer to solve (debug)" ), 0 }, { "start ", I18N_NOOP("Game range start (default 0:INT_MAX)" ), 0 }, { "end ", I18N_NOOP("Game range end (default start:start if start given)" ), 0 }, { "+file", I18N_NOOP("File to load"), 0 }, KCmdLineLastOption }; int main( int argc, char **argv ) { KAboutData aboutData( "kpat", I18N_NOOP("KPatience"), KPAT_VERSION, description, KAboutData::License_GPL, "(c) 1995, Paul Olav Tvete\n" "(c) 2000 Stephan Kulow"); aboutData.addAuthor("Paul Olav Tvete"); aboutData.addAuthor("Mario Weilguni",0,"mweilguni@kde.org"); aboutData.addAuthor("Matthias Ettrich",0,"ettrich@kde.org"); aboutData.addAuthor("Rodolfo Borges",I18N_NOOP("Some Game Types"),"barrett@9hells.org"); aboutData.addAuthor("Peter H. Ruegg",0,"kpat@incense.org"); aboutData.addAuthor("Michael Koch", I18N_NOOP("Bug fixes"), "koch@kde.org"); aboutData.addAuthor("Marcus Meissner", I18N_NOOP("Shuffle algorithm for game numbers"), "mm@caldera.de"); aboutData.addAuthor("Dr. Tom", I18N_NOOP("Patience Solver"), "http://members.tripod.com/professor_tom/"); aboutData.addAuthor("Stephan Kulow", I18N_NOOP("Rewrite and current maintainer"), "coolo@kde.org"); aboutData.addAuthor("Erik Sigra", I18N_NOOP("Improved Klondike"), "sigra@home.se"); aboutData.addAuthor("Josh Metzler", I18N_NOOP("Spider Implementation"), "joshdeb@metzlers.org"); aboutData.addAuthor("Maren Pakura", I18N_NOOP("Documentation"), "maren@kde.org"); aboutData.addAuthor("Inge Wallin", I18N_NOOP("Bug fixes"), "inge@lysator.liu.se"); KCmdLineArgs::init( argc, argv, &aboutData ); KCmdLineArgs::addCmdLineOptions (options); KCmdLineArgs* args = KCmdLineArgs::parsedArgs(); KApplication application; KGlobal::locale()->insertCatalog("libkdegames"); bool ok = false; int wanted_game = -1; if ( args->isSet( "solve" ) ) wanted_game = args->getOption("solve").toInt( &ok ); if ( ok ) { DealerInfo *di = 0; for (QList::ConstIterator it = DealerInfoList::self()->games().begin(); it != DealerInfoList::self()->games().end(); ++it) { if ( (*it)->gameindex == wanted_game ) { di = *it; break; } } ok = false; int end_index = -1; if ( args->isSet( "end" ) ) end_index = args->getOption("end").toInt( &ok ); if ( !ok ) end_index = -1; ok = false; int start_index = -1; if ( args->isSet( "start" ) ) start_index = args->getOption("start").toInt( &ok ); if ( !ok ) { start_index = 0; end_index = INT_MAX; } else { if ( end_index == -1 ) end_index = start_index; } if ( !di ) { kError() << "There is no game with index " << wanted_game << endl; return -1; } cardMap c; DealerScene *f = di->createGame(); if ( !f->solver() ) { kError() << "There is no solver for " << di->name << endl; return -1; } fprintf( stdout, "Testing %s\n", di->name ); for ( int i = start_index; i <= end_index; i++ ) { f->setGameNumber( i ); f->restart(); - int ret = f->solver()->patsolve(); + int ret = f->solver()->recursive(); if ( ret == Solver::WIN ) fprintf( stderr, "%d won\n", i ); else if ( ret == Solver::NOSOL ) fprintf( stdout, "%d lost\n", i ); else fprintf( stdout, "%d unknown\n", i ); } return 0; } if (application.isSessionRestored()) RESTORE(pWidget) else { pWidget *w = new pWidget; if (args->count()) w->openGame(args->url(0)); else QTimer::singleShot(0, w, SLOT(slotNewGameType())); } return application.exec(); } diff --git a/patsolve/patsolve.cpp b/patsolve/patsolve.cpp index a536bc6..672c75f 100644 --- a/patsolve/patsolve.cpp +++ b/patsolve/patsolve.cpp @@ -1,981 +1,1105 @@ /* Common routines & arrays. */ #include #include #include #include #include #include #include #include #include #include "patsolve.h" #include "../pile.h" #include "memory.h" /* This is a 32 bit FNV hash. For more information, see http://www.isthe.com/chongo/tech/comp/fnv/index.html */ #include #define FNV1_32_INIT 0x811C9DC5 #define FNV_32_PRIME 0x01000193 #define fnv_hash(x, hash) (((hash) * FNV_32_PRIME) ^ (x)) /* Hash a buffer. */ static inline quint32 fnv_hash_buf(quint8 *s, int len) { int i; quint32 h; h = FNV1_32_INIT; for (i = 0; i < len; i++) { h = fnv_hash(*s++, h); } return h; } /* Hash a 0 terminated string. */ static inline quint32 fnv_hash_str(quint8 *s) { quint32 h; h = FNV1_32_INIT; while (*s) { h = fnv_hash(*s++, h); } return h; } #include #include /* Hash a pile. */ void Solver::hashpile(int w) { W[w][Wlen[w]] = 0; Whash[w] = fnv_hash_str(W[w]); /* Invalidate this pile's id. We'll calculate it later. */ Wpilenum[w] = -1; } +#define MAXDEPTH 300 + +bool Solver::recursive(POSITION *parent) +{ + int i, alln, a, numout = 0; + + if ( parent == NULL ) { + translate_layout(); + init(); + recu_pos.clear(); + delete Stack; + Stack = new POSITION[MAXDEPTH]; + } + + /* Fill in the Possible array. */ + + alln = get_possible_moves(&a, &numout); + if (alln == 0) { + if ( isWon() ) { + Status = WIN; + return true; + } + return false; + } + + /* Prioritize these moves. Automoves don't get queued, so they + don't need a priority. */ + + if (!a) { + prioritize(Possible, alln); + } + + /* Now copy to safe storage and return. Non-auto moves out get put + at the end. Queueing them isn't a good idea because they are still + good moves, even if they didn't pass the automove test. So we still + do the recursive solve() on them, but only after queueing the other + moves. */ + + if ( parent && parent->depth >= MAXDEPTH - 2 ) + return false; + + MOVE *mp0 = new_array(MOVE, alln+1); + if (mp0 == NULL) { + return false; + } + MOVE *mp = mp0; + for (i = 0; i < alln; i++) { + if (Possible[i].card_index != -1) { + *mp = Possible[i]; /* struct copy */ + mp++; + } + } + mp->card_index = -1; + ++alln; + + bool fit = false; + for (mp = mp0; mp->card_index != -1; mp++) { + + int depth = 0; + if (parent != NULL) + depth = parent->depth + 1; + + make_move(mp); + + /* Calculate indices for the new piles. */ + pilesort(); + + /* See if this is a new position. */ + + Total_generated++; + POSITION *pos = &Stack[depth]; + pos->queue = NULL; + pos->parent = parent; + pos->node = pack_position(); + quint8 *key = (quint8 *)pos->node + sizeof(TREE); +#if 1 + qint32 hash = fnv_hash_buf(key, mm->Pilebytes); + if ( recu_pos.contains( hash ) ) + { + undo_move( mp ); + mm->give_back_block( (quint8 *)pos->node ); + continue; + } + recu_pos[hash] = true; + if ( recu_pos.count() % 10000 == 0 ) + kDebug() << "positions " << recu_pos.count() << endl; +#else + for ( int i = 0; i < depth; ++i ) + { + quint8 *tkey = (quint8 *)Stack[i].node + sizeof(TREE); + if ( !memcmp( key, tkey, mm->Pilebytes ) ) + { + undo_move( mp ); + mm->give_back_block( (quint8 *)pos->node ); + continue; + } + } +#endif + pos->move = *mp; /* struct copy */ + pos->cluster = 0; + pos->depth = depth; + pos->nchild = 0; + + bool ret = recursive(pos); + fit |= ret; + //kDebug() << "ret " << ret << " " << depth << endl; + undo_move(mp); + mm->give_back_block( (quint8 *)pos->node ); + if ( ret ) + break; + } + + MemoryManager::free_array(mp0, alln); + + if ( parent == NULL ) { + printf( "Total %ld\n", Total_generated ); + delete Stack; + Stack = 0; + } + return fit; +} + /* Generate an array of the moves we can make from this position. */ MOVE *Solver::get_moves(int *nmoves) { int i, n, alln, a, numout = 0; MOVE *mp, *mp0; /* Fill in the Possible array. */ alln = n = get_possible_moves(&a, &numout); #if 0 print_layout(); fprintf( stderr, "moves %d\n", n ); for (int j = 0; j < n; j++) { fprintf( stderr, " " ); if ( Possible[j].totype == O_Type ) fprintf( stderr, "move from %d out (at %d) Prio: %d\n", Possible[j].from, Possible[j].turn_index, Possible[j].pri ); else fprintf( stderr, "move from %d to %d (%d) Prio: %d\n", Possible[j].from, Possible[j].to, Possible[j].turn_index, Possible[j].pri ); } #endif /* No moves? Maybe we won. */ if (n == 0) { /* No more moves - won or lost */ //print_layout(); return NULL; } /* Prioritize these moves. Automoves don't get queued, so they don't need a priority. */ if (!a) { prioritize(Possible, alln); } /* Now copy to safe storage and return. Non-auto moves out get put at the end. Queueing them isn't a good idea because they are still good moves, even if they didn't pass the automove test. So we still do the recursive solve() on them, but only after queueing the other moves. */ mp = mp0 = new_array(MOVE, n); if (mp == NULL) { return NULL; } *nmoves = n; i = 0; if (a || numout == 0) { for (i = 0; i < alln; i++) { if (Possible[i].card_index != -1) { *mp = Possible[i]; /* struct copy */ mp++; } } } else { for (i = numout; i < alln; i++) { if (Possible[i].card_index != -1) { *mp = Possible[i]; /* struct copy */ mp++; } } for (i = 0; i < numout; i++) { if (Possible[i].card_index != -1) { *mp = Possible[i]; /* struct copy */ mp++; } } } return mp0; } - /* Test the current position to see if it's new (or better). If it is, save it, along with the pointer to its parent and the move we used to get here. */ int Posbytes; /* Comparison function for sorting the W piles. */ int Solver::wcmp(int a, int b) { if (m_newer_piles_first) { return Wpilenum[b] - Wpilenum[a]; /* newer piles first */ } else { return Wpilenum[a] - Wpilenum[b]; /* older piles first */ } } void Solver::pilesort(void) { /* Make sure all the piles have id numbers. */ for (int w = 0; w < m_number_piles; w++) { if (Wpilenum[w] < 0) { Wpilenum[w] = get_pilenum(w); if (Wpilenum[w] < 0) { return; } } //fprintf( stderr, "%d ", Wpilenum[w] ); } //fprintf( stderr, "\n" ); } #define NBUCKETS 16381 /* the largest 14 bit prime */ #define NPILES 16384 /* a 14 bit code */ typedef struct bucketlist { quint8 *pile; /* 0 terminated copy of the pile */ quint32 hash; /* the pile's hash code */ int pilenum; /* the unique id for this pile */ struct bucketlist *next; } BUCKETLIST; BUCKETLIST *Bucketlist[NBUCKETS]; int Pilenum; /* the next pile number to be assigned */ BUCKETLIST *Pilebucket[NPILES]; /* reverse lookup for unpack to get the bucket from the pile */ /* Compact position representation. The position is stored as an array with the following format: pile0# pile1# ... pileN# (N = Nwpiles) where each pile number is packed into 12 bits (so 2 piles take 3 bytes). Positions in this format are unique can be compared with memcmp(). The O cells are encoded as a cluster number: no two positions with different cluster numbers can ever be the same, so we store different clusters in different trees. */ int Treebytes; TREE *Solver::pack_position(void) { int j, k, w; quint8 *p; TREE *node; /* Allocate space and store the pile numbers. The tree node will get filled in later, by insert_node(). */ p = mm->new_from_block(Treebytes); if (p == NULL) { Status = FAIL; return NULL; } node = (TREE *)p; p += sizeof(TREE); /* Pack the pile numers j into bytes p. j j +--------+----:----+--------+ |76543210|7654:3210|76543210| +--------+----:----+--------+ p p p */ k = 0; quint16 *p2 = ( quint16* ) p; for (w = 0; w < m_number_piles; w++) { j = Wpilenum[w]; *p2++ = j; } return node; } /* Like strcpy() but return the length of the string. */ static inline int strecpy(unsigned char *d, unsigned char *s) { int i; i = 0; while ((*d++ = *s++) != '\0') { i++; } return i; } /* Unpack a compact position rep. T cells must be restored from the array following the POSITION struct. */ void Solver::unpack_position(POSITION *pos) { int i, k, w; quint8 c; BUCKETLIST *l; unpack_cluster(pos->cluster); /* Unpack bytes p into pile numbers j. p p p +--------+----:----+--------+ |76543210|7654:3210|76543210| +--------+----:----+--------+ j j */ k = w = i = c = 0; quint16 *p2 = ( quint16* )( (quint8 *)(pos->node) + sizeof(TREE) ); while (w < m_number_piles) { i = *p2++; Wpilenum[w] = i; l = Pilebucket[i]; i = strecpy(W[w], l->pile); Wp[w] = &W[w][i - 1]; Wlen[w] = i; Whash[w] = l->hash; w++; } } void Solver::printcard(card_t card, FILE *outfile) { static char Rank[] = " A23456789TJQK"; static char Suit[] = "DCHS"; if (RANK(card) == NONE) { fprintf(outfile, " "); } else { if ( DOWN(card ) ) fprintf(outfile, "|%c%c ", Rank[RANK(card)], Suit[SUIT(card)]); else fprintf(outfile, "%c%c ", Rank[RANK(card)], Suit[SUIT(card)]); } } /* Win. Print out the move stack. */ void Solver::win(POSITION *pos) { int i, nmoves; POSITION *p; MOVE *mp, **mpp, **mpp0; /* Go back up the chain of parents and store the moves in reverse order. */ i = 0; for (p = pos; p->parent; p = p->parent) { i++; } nmoves = i; printf("Winning in %d moves.\n", nmoves); return; mpp0 = new_array(MOVE *, nmoves); if (mpp0 == NULL) { Status = FAIL; return; /* how sad, so close... */ } mpp = mpp0 + nmoves - 1; for (p = pos; p->parent; p = p->parent) { *mpp-- = &p->move; } mp = *mpp0; /* Now print them out in the correct order. */ int count = -1; for (i = 0, mpp = mpp0; i < nmoves; i++, mpp++) { if (count-- == 0) break; mp = *mpp; if (mp->totype == O_Type) { fprintf(stderr, "%d@%d out\n", mp->card_index, mp->from); } else { fprintf(stderr, "%d@%d to %d\n", mp->card_index, mp->from, mp->to); } } MemoryManager::free_array(mpp0, nmoves); } /* Initialize the hash buckets. */ void Solver::init_buckets(void) { int i; /* Packed positions need 3 bytes for every 2 piles. */ i = ( m_number_piles ) * sizeof( quint16 ); i += ( m_number_piles ) & 0x1; mm->Pilebytes = i; memset(Bucketlist, 0, sizeof(Bucketlist)); Pilenum = 0; Treebytes = sizeof(TREE) + mm->Pilebytes; /* In order to keep the TREE structure aligned, we need to add up to 7 bytes on Alpha or 3 bytes on Intel -- but this is still better than storing the TREE nodes and keys separately, as that requires a pointer. On Intel for -f Treebytes winds up being a multiple of 8 currently anyway so it doesn't matter. */ #define ALIGN_BITS 0x7 if (Treebytes & ALIGN_BITS) { Treebytes |= ALIGN_BITS; Treebytes++; } Posbytes = sizeof(POSITION); if (Posbytes & ALIGN_BITS) { Posbytes |= ALIGN_BITS; Posbytes++; } + + memset( Stack, 0, sizeof( Stack ) ); } /* For each pile, return a unique identifier. Although there are a large number of possible piles, generally fewer than 1000 different piles appear in any given game. We'll use the pile's hash to find a hash bucket that contains a short list of piles, along with their identifiers. */ int Solver::get_pilenum(int w) { int bucket, pilenum; BUCKETLIST *l, *last; /* For a given pile, get its unique pile id. If it doesn't have one, add it to the appropriate list and give it one. First, get the hash bucket. */ bucket = Whash[w] % NBUCKETS; /* Look for the pile in this bucket. */ last = NULL; for (l = Bucketlist[bucket]; l; l = l->next) { if (l->hash == Whash[w] && strncmp((char*)l->pile, (char*)W[w], Wlen[w]) == 0) { break; } last = l; } /* If we didn't find it, make a new one and add it to the list. */ if (l == NULL) { if (Pilenum == NPILES) { fprintf(stderr, "Ran out of pile numbers!"); exit( 1 ); return -1; } l = allocate(BUCKETLIST); if (l == NULL) { Status = FAIL; return -1; } l->pile = new_array(quint8, Wlen[w] + 1); if (l->pile == NULL) { Status = FAIL; MemoryManager::free_ptr(l); return -1; } /* Store the new pile along with its hash. Maintain a reverse mapping so we can unpack the piles swiftly. */ strncpy((char*)l->pile, (char*)W[w], Wlen[w] + 1); l->hash = Whash[w]; l->pilenum = pilenum = Pilenum++; l->next = NULL; if (last == NULL) { Bucketlist[bucket] = l; } else { last->next = l; } Pilebucket[pilenum] = l; } /* fprintf( stderr, "get_pile_num %d ", l->pilenum ); for (int i = 0; i < Wlen[w]; i++) { printcard(W[w][i], stderr); } fprintf( stderr, "\n" ); */ return l->pilenum; } void Solver::free_buckets(void) { int i, j; BUCKETLIST *l, *n; for (i = 0; i < NBUCKETS; i++) { l = Bucketlist[i]; while (l) { n = l->next; j = strlen((char*)l->pile); /* @@@ use block? */ MemoryManager::free_array(l->pile, j + 1); MemoryManager::free_ptr(l); l = n; } } } /* Solve patience games. Prioritized breadth-first search. Simple breadth- first uses exponential memory. Here the work queue is kept sorted to give priority to positions with more cards out, so the solution found is not guaranteed to be the shortest, but it'll be better than with a depth-first search. */ void Solver::doit() { int i, q; POSITION *pos; MOVE m; memset( &m, 0, sizeof( MOVE ) ); /* Init the queues. */ for (i = 0; i < NQUEUES; i++) { Qhead[i] = NULL; } Maxq = 0; /* Queue the initial position to get started. */ hash_layout(); pilesort(); m.card_index = -1; m.turn_index = -1; pos = new_position(NULL, &m); if (pos == NULL) { Status = FAIL; return; } queue_position(pos, 0); /* Solve it. */ while ((pos = dequeue_position()) != NULL) { q = solve(pos); if (!q) { free_position(pos, true); } } } /* Generate all the successors to a position and either queue them or recursively solve them. Return whether any of the child nodes, or their descendents, were queued or not (if not, the position can be freed). */ bool Solver::solve(POSITION *parent) { int i, nmoves, qq; MOVE *mp, *mp0; POSITION *pos; bool q; /* If we've won already (or failed), we just go through the motions but always return false from any position. This enables the cleanup of the move stack and eventual destruction of the position store. */ if (Status != NOSOL) { return false; } /* If the position was found again in the tree by a shorter path, prune this path. */ if (parent->node->depth < parent->depth) { Q_ASSERT( false ); // we don't do that return false; } /* Generate an array of all the moves we can make. */ if ((mp0 = get_moves(&nmoves)) == NULL) { if ( isWon() ) { Status = WIN; win( parent ); } return false; } parent->nchild = nmoves; /* Make each move and either solve or queue the result. */ q = false; for (i = 0, mp = mp0; i < nmoves; i++, mp++) { make_move(mp); /* Calculate indices for the new piles. */ pilesort(); /* See if this is a new position. */ if ((pos = new_position(parent, mp)) == NULL) { undo_move(mp); parent->nchild--; continue; } /* If this position is in a new cluster, a card went out. Don't queue it, just keep going. A larger cutoff can also force a recursive call, which can help speed things up (but reduces the quality of solutions). Otherwise, save it for later. */ if (pos->cluster != parent->cluster || !nmoves) { qq = solve(pos); undo_move(mp); if (!qq) { free_position(pos, false); } q |= (bool)qq; } else { queue_position(pos, mp->pri); undo_move(mp); q = true; } } MemoryManager::free_array(mp0, nmoves); /* Return true if this position needs to be kept around. */ return q; } /* We can't free the stored piles in the trees, but we can free some of the POSITION structs. We have to be careful, though, because there are many threads running through the game tree starting from the queued positions. The nchild element keeps track of descendents, and when there are none left in the parent we can free it too after solve() returns and we get called recursively (rec == true). */ void Solver::free_position(POSITION *pos, int rec) { - /* We don't really free anything here, we just push it onto a - freelist (using the queue member), so we can use it again later. */ + /* We don't really free anything here, we just push it onto a + freelist (using the queue member), so we can use it again later. */ - if (!rec) { - pos->queue = Freepos; - Freepos = pos; - pos->parent->nchild--; - } else { - do { - pos->queue = Freepos; - Freepos = pos; - pos = pos->parent; - if (pos == NULL) { - return; - } - pos->nchild--; - } while (pos->nchild == 0); - } + if (!rec) { + pos->queue = Freepos; + Freepos = pos; + pos->parent->nchild--; + } else { + do { + pos->queue = Freepos; + Freepos = pos; + pos = pos->parent; + if (pos == NULL) { + return; + } + pos->nchild--; + } while (pos->nchild == 0); + } } /* Save positions for consideration later. pri is the priority of the move that got us here. The work queue is kept sorted by priority (simply by having separate queues). */ void Solver::queue_position(POSITION *pos, int pri) { /* In addition to the priority of a move, a position gets an additional priority depending on the number of cards out. We use a "queue squashing function" to map nout to priority. */ int nout = getOuts(); static double Yparam[] = { 0.0032, 0.32, -3.0 }; double x = (Yparam[0] * nout + Yparam[1]) * nout + Yparam[2]; pri += (int)floor(x + .5); if (pri < 0) { pri = 0; } else if (pri >= NQUEUES) { pri = NQUEUES - 1; } if (pri > Maxq) { Maxq = pri; } /* We always dequeue from the head. Here we either stick the move at the head or tail of the queue, depending on whether we're pretending it's a stack or a queue. */ pos->queue = NULL; if (Qhead[pri] == NULL) { Qhead[pri] = pos; } else { pos->queue = Qhead[pri]; Qhead[pri] = pos; } } /* Return the position on the head of the queue, or NULL if there isn't one. */ POSITION *Solver::dequeue_position() { int last; POSITION *pos; static int qpos = 0; static int minpos = 0; /* This is a kind of prioritized round robin. We make sweeps through the queues, starting at the highest priority and working downwards; each time through the sweeps get longer. That way the highest priority queues get serviced the most, but we still get lots of low priority action (instead of ignoring it completely). */ last = false; do { qpos--; if (qpos < minpos) { if (last) { return NULL; } qpos = Maxq; minpos--; if (minpos < 0) { minpos = Maxq; } if (minpos == 0) { last = true; } } } while (Qhead[qpos] == NULL); pos = Qhead[qpos]; Qhead[qpos] = pos->queue; /* Decrease Maxq if that queue emptied. */ while (Qhead[qpos] == NULL && qpos == Maxq && Maxq > 0) { Maxq--; qpos--; if (qpos < minpos) { minpos = qpos; } } /* Unpack the position into the work arrays. */ unpack_position(pos); return pos; } Solver::Solver() { mm = new MemoryManager(); Freepos = NULL; m_newer_piles_first = true; /* Work arrays. */ W = 0; Wp = 0; Wlen = 0; Whash = 0; Wpilenum = 0; - + Stack = 0; } Solver::~Solver() { delete mm; } void Solver::init() { init_buckets(); mm->init_clusters(); /* Reset stats. */ Status = NOSOL; Total_positions = 0; Total_generated = 0; depth_sum = 0; } void Solver::free() { free_buckets(); mm->free_clusters(); mm->free_blocks(); Freepos = NULL; } Solver::statuscode Solver::patsolve() { /* Initialize the suitable() macro variables. */ translate_layout(); init(); /* Go to it. */ doit(); printf("%ld positions generated (%f).\n", Total_generated, depth_sum / Total_positions); printf("%ld unique positions.\n", Total_positions); printf("Mem_remain = %ld\n", ( long int )mm->Mem_remain); free(); return Status; } void Solver::showCurrentMoves() { translate_layout(); init(); int alln, a, numout = 0; /* Fill in the Possible array. */ alln = get_possible_moves(&a, &numout); print_layout(); /* No moves? Maybe we won. */ if (alln != 0 ) { if (!a) prioritize(Possible, alln); fprintf( stderr, "moves %d\n", alln ); for (int j = 0; j < alln; j++) { fprintf( stderr, " " ); if ( Possible[j].totype == O_Type ) fprintf( stderr, "move %d from %d out (at %d) Prio:%d\n", Possible[j].card_index + 1, Possible[j].from, Possible[j].turn_index, Possible[j].pri ); else fprintf( stderr, "move %d from %d to %d (%d) Prio: %d\n", Possible[j].card_index + 1, Possible[j].from, Possible[j].to, Possible[j].turn_index, Possible[j].pri); } } free(); } bool Solver::print_layout() { return true; } void Solver::setNumberPiles( int p ) { m_number_piles = p; /* Work arrays. */ W = new card_t*[m_number_piles]; for ( int i = 0; i < m_number_piles; i++ ) { W[i] = new card_t[52]; memset( W[i], 0, sizeof( card_t ) * 52 ); } Wp = new card_t*[m_number_piles]; Wlen = new int[m_number_piles]; Whash = new quint32[m_number_piles]; Wpilenum = new int[m_number_piles]; + memset( Wpilenum, 0, sizeof( int ) * m_number_piles ); } int Solver::translateSuit( int s ) { int suit = s * 0x10; if ( suit == PS_DIAMOND ) return PS_CLUB; else if ( suit == PS_CLUB ) return PS_DIAMOND; return suit; } int Solver::translate_pile(const Pile *pile, card_t *w, int size) { Q_ASSERT( pile->cardsLeft() <= size ); card_t rank, suit; rank = suit = NONE; for ( int i = 0; i < pile->cardsLeft(); ++i ) { Card *c = pile->at( i ); *w = + translateSuit( c->suit() ) + c->rank(); if ( !c->realFace() ) *w += 1 << 7; w++; } return pile->cardsLeft(); } /* Insert key into the tree unless it's already there. Return true if it was new. */ MemoryManager::inscode Solver::insert(int *cluster, int d, TREE **node) { /* Get the cluster number from the Out cell contents. */ int k = getClusterNumber(); *cluster = k; /* Get the tree for this cluster. */ TREELIST *tl = mm->cluster_tree(k); if (tl == NULL) { return MemoryManager::ERR; } /* Create a compact position representation. */ TREE *newtree = pack_position(); if (newtree == NULL) { return MemoryManager::ERR; } Total_generated++; MemoryManager::inscode i2 = mm->insert_node(newtree, d, &tl->tree, node); if (i2 != MemoryManager::NEW) { mm->give_back_block((quint8 *)newtree); } return i2; } POSITION *Solver::new_position(POSITION *parent, MOVE *m) { int depth, cluster; quint8 *p; POSITION *pos; TREE *node; /* Search the list of stored positions. If this position is found, then ignore it and return (unless this position is better). */ if (parent == NULL) { depth = 0; } else { depth = parent->depth + 1; } MemoryManager::inscode i = insert(&cluster, depth, &node); if (i == MemoryManager::NEW) { Total_positions++; depth_sum += depth; } else if (i != MemoryManager::FOUND_BETTER) { return NULL; } /* A new or better position. insert() already stashed it in the tree, we just have to wrap a POSITION struct around it, and link it into the move stack. Store the temp cells after the POSITION. */ if (Freepos) { p = (quint8 *)Freepos; Freepos = Freepos->queue; } else { p = mm->new_from_block(Posbytes); if (p == NULL) { Status = FAIL; return NULL; } } pos = (POSITION *)p; pos->queue = NULL; pos->parent = parent; pos->node = node; pos->move = *m; /* struct copy */ pos->cluster = cluster; pos->depth = depth; pos->nchild = 0; #if 0 QString dummy; quint16 *t = ( quint16* )( ( char* )node + sizeof( TREE ) ); for ( int i = 0; i < m_number_piles; i++ ) { QString s = " " + QString( "%1" ).arg( ( int )t[i] ); dummy += s.right( 5 ); } if ( Total_positions % 1000 == 0 ) print_layout(); // kDebug() << "new " << dummy << endl; #endif p += sizeof(POSITION); return pos; } /* Hash the whole layout. This is called once, at the start. */ void Solver::hash_layout(void) { int w; for (w = 0; w < m_number_piles; w++) { hashpile(w); } } void Solver::prioritize(MOVE *, int ) { } diff --git a/patsolve/patsolve.h b/patsolve/patsolve.h index 9e2878c..ad181c6 100644 --- a/patsolve/patsolve.h +++ b/patsolve/patsolve.h @@ -1,141 +1,146 @@ #ifndef PATSOLVE_H #define PATSOLVE_H #include #include "../hint.h" #include "memory.h" #include +#include class DealerScene; /* A card is represented as ( down << 6 ) + (suit << 4) + rank. */ typedef quint8 card_t; /* Represent a move. */ enum PileType { O_Type = 1, W_Type }; typedef struct { int card_index; /* the card we're moving (0 is the top)*/ quint8 from; /* from pile number */ quint8 to; /* to pile number */ PileType totype; signed char pri; /* move priority (low priority == low value) */ int turn_index; /* turn the card index */ } MOVE; struct POSITION; struct POSITION { POSITION *queue; /* next position in the queue */ POSITION *parent; /* point back up the move stack */ TREE *node; /* compact position rep.'s tree node */ MOVE move; /* move that got us here from the parent */ unsigned short cluster; /* the cluster this node is in */ short depth; /* number of moves so far */ quint8 ntemp; /* number of cards in T */ quint8 nchild; /* number of child nodes left */ }; class MemoryManager; class Solver { public: enum statuscode { FAIL = -1, WIN = 0, NOSOL = 1 }; Solver(); virtual ~Solver(); statuscode patsolve(); void showCurrentMoves(); + bool recursive(POSITION *pos = 0); protected: MOVE *get_moves(int *nmoves); bool solve(POSITION *parent); void doit(); void win(POSITION *pos); virtual int get_possible_moves(int *a, int *numout) = 0; int translateSuit( int s ); int wcmp(int a, int b); void queue_position(POSITION *pos, int pri); void free_position(POSITION *pos, int); POSITION *dequeue_position(); void hashpile(int w); POSITION *new_position(POSITION *parent, MOVE *m); TREE *pack_position(void); void unpack_position(POSITION *pos); void init_buckets(void); int get_pilenum(int w); MemoryManager::inscode insert(int *cluster, int d, TREE **node); void free_buckets(void); void printcard(card_t card, FILE *outfile); int translate_pile(const Pile *pile, card_t *w, int size); virtual bool print_layout(); void pilesort(void); void hash_layout( void ); virtual void make_move(MOVE *m) = 0; virtual void undo_move(MOVE *m) = 0; virtual void prioritize(MOVE *mp0, int n); virtual bool isWon() = 0; virtual int getOuts() = 0; virtual int getClusterNumber() = 0; virtual void translate_layout() = 0; virtual void unpack_cluster( int k ) = 0; void setNumberPiles( int i ); int m_number_piles; void init(); void free(); /* Work arrays. */ card_t **W; /* the workspace */ card_t **Wp; /* point to the top card of each work pile */ int *Wlen; /* the number of cards in each pile */ /* Every different pile has a hash and a unique id. */ quint32 *Whash; int *Wpilenum; /* Position freelist. */ POSITION *Freepos; #define MAXMOVES 64 /* > max # moves from any position */ MOVE Possible[MAXMOVES]; MemoryManager *mm; statuscode Status; /* win, lose, or fail */ #define NQUEUES 127 POSITION *Qhead[NQUEUES]; /* separate queue for each priority */ int Maxq; bool m_newer_piles_first; unsigned long Total_generated, Total_positions; double depth_sum; + + POSITION *Stack; + QMap recu_pos; }; /* Misc. */ #define PS_DIAMOND 0x00 /* red */ #define PS_CLUB 0x10 /* black */ #define PS_HEART 0x20 /* red */ #define PS_SPADE 0x30 /* black */ #define PS_COLOR 0x10 /* black if set */ #define PS_SUIT 0x30 /* mask both suit bits */ #define NONE 0 #define PS_ACE 1 #define PS_KING 13 #define RANK(card) ((card) & 0xF) #define SUIT(card) (( (card) >> 4 ) & 3) #define COLOR(card) ((card) & PS_COLOR) #define DOWN(card) ((card) & ( 1 << 7 ) ) #endif diff --git a/patsolve/spider.cpp b/patsolve/spider.cpp index 8fffc59..426be90 100644 --- a/patsolve/spider.cpp +++ b/patsolve/spider.cpp @@ -1,497 +1,495 @@ /* Common routines & arrays. */ #include #include #include #include #include #include #include #include #include #include "spider.h" #include "../spider.h" #include "../pile.h" #include "../deck.h" #include "memory.h" /* These two routines make and unmake moves. */ #define PRINT 0 #define PRINT2 0 void SpiderSolver::make_move(MOVE *m) { #if PRINT kDebug() << "\n\nmake_move\n"; if ( m->totype == O_Type ) fprintf( stderr, "move %d from %d out (at %d) Prio: %d\n\n", m->card_index, m->from, m->turn_index, m->pri ); else 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 ); print_layout(); #else //print_layout(); #endif int from, to; card_t card = NONE; from = m->from; to = m->to; if ( m->from >= 10 ) { Q_ASSERT( Wlen[from] == 10 ); for ( int i = 0; i < 10; ++i ) { card_t card = *Wp[from]; - Q_ASSERT( DOWN( card ) ); card = ( SUIT( card ) << 4 ) + RANK( card ); ++Wp[i]; *Wp[i] = card; --Wp[from]; Wlen[i]++; hashpile( i ); } Wlen[from] = 0; hashpile( from ); #if PRINT print_layout(); #endif return; } if (m->totype == O_Type) { O[to] = SUIT( *Wp[from] ); Wlen[from] -= 13; Wp[from] -= 13; hashpile( from ); if ( Wlen[from] && DOWN( *Wp[from] ) ) { *Wp[from] = ( SUIT( *Wp[from] ) << 4 ) + RANK( *Wp[from] ); - Q_ASSERT( m->turn_index >= 0 ); } #if PRINT print_layout(); #endif return; } for ( int l = m->card_index; l >= 0; l-- ) { card = W[from][Wlen[from]-l-1]; Wp[from]--; if ( m->totype != O_Type ) { Wp[to]++; *Wp[to] = card; Wlen[to]++; } } Wlen[from] -= m->card_index + 1; if ( m->turn_index == 0 ) { if ( DOWN( card ) ) card = ( SUIT( card ) << 4 ) + RANK( card ); else card += ( 1 << 7 ); W[to][Wlen[to]-m->card_index-1] = card; } else if ( m->turn_index != -1 ) { card_t card2 = *Wp[from]; if ( DOWN( card2 ) ) card2 = ( SUIT( card2 ) << 4 ) + RANK( card2 ); *Wp[from] = card2; } hashpile(from); hashpile(to); #if PRINT print_layout(); #endif } void SpiderSolver::undo_move(MOVE *m) { #if PRINT kDebug() << "\n\nundo_move\n"; if ( m->totype == O_Type ) fprintf( stderr, "move %d from %d out (at %d)\n\n", m->card_index, m->from, m->turn_index ); else fprintf( stderr, "move %d from %d to %d (%d)\n\n", m->card_index, m->from, m->to, m->turn_index ); print_layout(); #endif int from, to; card_t card; from = m->from; to = m->to; if ( m->from >= 10 ) { Q_ASSERT( Wlen[from] == 0 ); for ( int i = 0; i < 10; ++i ) { card_t card = *Wp[i]; Q_ASSERT( !DOWN( card ) ); card = ( SUIT( card ) << 4 ) + RANK( card ) + ( 1 << 7 ); ++Wp[from]; --Wp[i]; *Wp[from] = card; Wlen[from]++; Wlen[i]--; hashpile( i ); } hashpile( from ); #if PRINT print_layout(); #endif return; } if (m->totype == O_Type) { if ( m->turn_index >= 0 ) { Q_ASSERT( !DOWN( *Wp[from] ) ); card_t card = *Wp[from]; card = ( SUIT( card ) << 4 ) + RANK( card ) + ( 1 << 7 ); *Wp[from] = card; } for ( int j = PS_KING; j >= PS_ACE; j-- ) { Wp[from]++; *Wp[from] = ( O[to] << 4 ) + j; Wlen[from]++; } O[to] = 0; hashpile( from ); #if PRINT print_layout(); #endif return; } /* Add to 'from' pile. */ if ( m->turn_index > 0 ) { card_t card2 = *Wp[from]; if ( !DOWN( card2 ) ) card2 = ( SUIT( card2 ) << 4 ) + RANK( card2 ) + ( 1 << 7 ); *Wp[from] = card2; } for ( int l = m->card_index; l >= 0; l-- ) { card = W[to][Wlen[to]-l-1]; Wp[from]++; *Wp[from] = card; Wlen[from]++; *Wp[to]--; } Wlen[to] -= m->card_index + 1; hashpile(to); if ( m->turn_index == 0 ) { card_t card = *Wp[from]; if ( DOWN( card ) ) card = ( SUIT( card ) << 4 ) + RANK( card ); else card += ( 1 << 7 ); *Wp[from] = card; } hashpile(from); #if PRINT print_layout(); #endif } /* Get the possible moves from a position, and store them in Possible[]. */ int SpiderSolver::get_possible_moves(int *a, int *numout) { MOVE *mp; /* Check for moves from W to O. */ int n = 0; mp = Possible; for (int w = 0; w < 10; w++) { if (Wlen[w] >= 13 && RANK( *Wp[w] ) == PS_ACE ) { int ace_suit = SUIT( *Wp[w] ); bool stroke = true; for ( int l = 0; l < 13; l++ ) { if ( RANK( W[w][Wlen[w]-l-1] ) != l+1 || SUIT( W[w][Wlen[w]-l-1] ) != ace_suit ) { stroke = false; break; } } if ( !stroke ) continue; mp->card_index = 0; mp->from = w; int o = 0; while ( O[o] ) o++; // TODO I need a way to tell spades off from heart off mp->to = o; mp->totype = O_Type; mp->pri = 0; /* unused */ mp->turn_index = -1; if ( Wlen[w] > 13 && DOWN( W[w][Wlen[w]-13-1] ) ) mp->turn_index = 1; n++; mp++; /* If it's an automove, just do it. */ if ( mp->turn_index != -1 ) return 1; } } /* No more automoves, but remember if there were any moves out. */ *a = false; *numout = n; int conti[10]; for ( int j = 0; j < 10; j++ ) { conti[j] = 0; for ( ; conti[j] < Wlen[j]-1; ++conti[j] ) { if ( SUIT( *Wp[j] ) != SUIT( W[j][Wlen[j]-conti[j]-2] ) || DOWN( W[j][Wlen[j]-conti[j]-2] )) break; if ( RANK( W[j][Wlen[j]-conti[j]-1] ) != RANK( W[j][Wlen[j]-conti[j]-2] ) - 1) break; } conti[j]++; } bool foundgood = false; for(int i=0; i<10; i++) { int len = Wlen[i]; for (int l=0; l < len; ++l ) { card_t card = W[i][Wlen[i]-1-l]; if ( DOWN( card ) ) break; if ( l > 0 ) { card_t card_on_top = W[i][Wlen[i]-l]; if ( RANK( card ) != RANK( card_on_top ) + 1 ) break; if ( SUIT( card ) != SUIT( card_on_top ) ) break; } bool wasempty = false; for (int j = 0; j < 10; j++) { if (i == j) continue; bool allowed = false; if ( Wlen[j] > 0 && RANK(card) == RANK(*Wp[j]) - 1 ) { allowed = true; if ( ( SUIT( card ) != SUIT( *Wp[j] ) ) && foundgood ) allowed = false; // make the tree simpler } if ( Wlen[j] == 0 && !wasempty ) { if ( l != Wlen[i]-1 ) { allowed = true; wasempty = true; } } if ( allowed && Wlen[i] >= l+2 && Wlen[i] > 1 ) { Q_ASSERT( Wlen[i]-l-2 >= 0 ); card_t card_below = W[i][Wlen[i]-l-2]; if ( SUIT( card ) == SUIT( card_below ) && !DOWN( card_below ) && RANK( card_below ) == RANK( card ) + 1 ) { #if 0 printcard( card_below, stderr ); printcard( card, stderr ); fprintf( stderr, "%d %d %d %d %d\n", i, j, conti[i], conti[j],l ); #endif if ( conti[j]+l != 13 || conti[i]>conti[j]+l || SUIT( card ) != SUIT( *Wp[j] ) ) { // fprintf( stderr, "continue\n" ); continue; } } } if ( allowed ) { mp->card_index = l; mp->from = i; mp->to = j; mp->totype = W_Type; mp->turn_index = -1; if ( Wlen[i] > l+1 && DOWN( W[i][Wlen[i]-l-2] ) ) mp->turn_index = 1; int cont = conti[j]; if ( Wlen[j] ) cont++; if ( cont ) cont += l; mp->pri = 8 * cont + qMax( 0, 10 - Wlen[i] ); - if ( SUIT( card ) != SUIT( *Wp[j] ) ) + if ( Wlen[j] && SUIT( card ) != SUIT( *Wp[j] ) ) mp->pri = 1; else foundgood = true; if ( mp->turn_index > 0) mp->pri += 7; else if ( Wlen[i] == l+1 ) mp->pri += 4; else mp->pri += 2; n++; mp++; } } } } /* check for redeal */ for ( int i = 0; i < 5; ++i ) { if ( !Wlen[10+i] || foundgood ) continue; mp->card_index = 0; mp->from = 10+i; mp->to = 0; // unused mp->totype = W_Type; mp->pri = 0; mp->turn_index = -1; n++; mp++; break; // one is enough } return n; } void SpiderSolver::unpack_cluster( int k ) { // TODO: this only works for easy for ( int i = 0; i < 8; ++i ) { if ( i < k ) O[i] = PS_SPADE; else O[i] = 0; } } bool SpiderSolver::isWon() { // maybe won? for (int o = 0; o < 8; o++) if (!O[o]) return false; return true; } int SpiderSolver::getOuts() { int k = 0; for (int o = 0; o < 8; o++) if (O[o]) k += 13; return k / 2; } SpiderSolver::SpiderSolver(const Spider *dealer) : Solver() { // 10 play + 5 redeals setNumberPiles( 15 ); deal = dealer; } /* Read a layout file. Format is one pile per line, bottom to top (visible card). Temp cells and Out on the last two lines, if any. */ void SpiderSolver::translate_layout() { /* Read the workspace. */ int total = 0; for ( int w = 0; w < 10; ++w ) { int i = translate_pile(deal->stack[w], W[w], 52); Wp[w] = &W[w][i - 1]; Wlen[w] = i; total += i; } for ( int w = 0; w < 5; ++w ) { int i = translate_pile( deal->redeals[w], W[10+w], 52 ); Wp[10+w] = &W[10+w][i-1]; Wlen[10+w] = i; total += i; } for (int i = 0; i < 8; i++) { O[i] = 0; Card *c = deal->legs[i]->top(); if (c) { total += 13; O[i] = translateSuit( c->suit() ); } } } int SpiderSolver::getClusterNumber() { int k = 0; for ( int i = 0; i < 8; ++i ) if ( O[i] ) k++; return k; } bool SpiderSolver::print_layout() { int i, w, o; fprintf(stderr, "print-layout-begin\n"); for (w = 0; w < 15; w++) { Q_ASSERT( Wp[w] == &W[w][Wlen[w]-1] ); if ( w < 10 ) fprintf( stderr, "Play%d: ", w ); else fprintf( stderr, "Deal%d: ", w-10 ); for (i = 0; i < Wlen[w]; i++) { printcard(W[w][i], stderr); } fputc('\n', stderr); } fprintf( stderr, "Off: " ); for (o = 0; o < 8; o++) { if ( O[o] ) printcard(( O[o] << 4 ) + PS_KING, stderr); } fprintf(stderr, "\nprint-layout-end\n"); bool broke = false; if ( broke ) exit( 1 ); return broke; }