TweetFollow Us on Twitter

Feb 01 Challenge Volume Number: 17 (2001)
Issue Number: 2
Column Tag: Programmer's Challenge

Programmer's Challenge

By Bob Boonstra, Westford, MA

Trilite

Tic-Tac-Toe is a trivial game. There are less than 9! possible games, far fewer if symmetry is taken into account, and certainly few enough for the outcome to be calculated in advance. But there is a variant of Tic-Tac-Toe that allows many more possible move sequences, and for which there may or may not be a guaranteed winning solution. This month you are going to have an opportunity to compete in the game of Trilite against your Challenge peers.

Trilite is like Tic-Tac-Toe in the sense that it is played on a 3x3 board, where two players alternate occupying squares with the objective of occupying three positions in a row. It differs from Tic-Tac-Toe in that a player may occupy only three positions at a time. When a player occupies a fourth position, one of the three previously occupied positions, the one that has been occupied the longest, becomes vacant. So after any move, there are always three vacant positions on the board, and one more that is about to become unoccupied when the current player occupies one of the three vacant positions. Sounds simple, right?

The prototype for the code you should write is:

typedef enum {                        /* numbering system for Board positions */
   kNoPosition=-1,
   kTopLeft=0, kTopCenter, kTopRight, 
   kCenterLeft, kCenter, kCenterRight,
   kBottomLeft, kBottomCenter, kBottomRight
} BoardPosition;

typedef enum {                        /* possible values for a Board Position */
   kEmpty=-1, 
   kPlayer1Staying=0, kPlayer1Disappearing,
   kPlayer2Staying, kPlayer2Disappearing
} PositionValue;

typedef PositionValue Board[9];   /* state of the Board */

BoardPosition PlayTrilite(
   const Board triliteBoard,   /* current state of the Board */
   BoardPosition opponentPreviousPlay,
      /* the BoardPosition your opponent last played */
   int playerNumber,      /* 1 if you are player 1, 2 if you are player 2 */
   Boolean newGame         /* true the first time you are called for a new game */
);

For each game of Trilite, your PlayTrilite routine and that of your opponent will be called alternately until one of you wins by occupying three positions in a row, horizontally, vertically, or diagonally. The first time PlayTrilite is called for a new game, newGame will be set to TRUE. When newGame is TRUE, playerNumber will indicate whether you are the first (playerNumber==1) or second (playerNumber==2) player. Each time PlayTrilite is called, the BoardPosition last occupied by your opponent will be provided as opponentPreviousPlay. Finally, the current state of the Board will be provided to you as triliteBoard.

Trilite board positions have five possible values. Unoccupied positions have the value kEmpty. Positions occupied by player 1 have the value kPlayer1Staying or kPlayer1Disappearing, with the latter value distinguishing positions that will become empty following player 1's next move. Similarly, positions occupied by player 2 have the value kPlayer2Staying or kPlayer2Disappearing.

A sequence of moves works like this. Suppose the game has been going on for at least three pairs of turns, and it is player 1's turn to play. The Board will have six occupied positions, three by player 1 and three by player 2. One position for each player will be marked as "disappearing" on the next move. Player 1 will occupy one of the three remaining unoccupied positions, and - at the same time - the kPlayer1Disappearing position will become kEmpty. If player 1 now occupies three positions in a row, s/he is the winner. Otherwise, player 2 then occupies one of the three empty positions and the kPlayer2Disappearing position becomes kEmpty. Note that a player may not reoccupy the position about to disappear - the opponent is the first player with a chance to occupy that position. The astute reader might detect one element of a potential game strategy here.

Entries will compete against one another in a tournament structured so that each entry plays each other entry an even number of times, half playing first, and half playing second. If the number of entries is large, some other fair tournament scheme will be used. A game will be considered drawn when a time limit and a move count limit, not specified as part of the problem statement, are exceeded.

The winner will be the entry that scores the most points, where each game won is worth 1000 points, each game drawn is worth 500 points, and 1 point is deducted for each millisecond of execution time. The Challenge prize will be divided between the overall winner and the best scoring entry from a contestant that has not won the Challenge recently.

Your code and data must live in an application heap of 40MB. Any nontrivial tables used by your solution must be calculated at run time. Any entry that precalculates any significant part of the solution will be disqualified.

Those of you interested in experimenting with Trilite might want to check out the shareware game by John Mauro, at <http://screech.cs.alfred.edu/~maurojc/software/software.html#Trilite>.

This will be a native PowerPC Challenge, using the CodeWarrior Pro 6 environment. Solutions may be coded in C, C++, or Pascal. You can also provide a solution in Java, provided you also provide a test driver equivalent to the C code provided on the web for this problem.

Three Months Ago Winner

Three people entered the November FreeCell Challenge, where contestants had to write code to solve the FreeCell solitaire puzzle. FreeCell requires players to move cards from eight tableaus to four home piles in ascending order based on suit, but it also provides four "free cells" where cards may be stored temporarily. Congratulations to Ernst Munter (Kanata, Ontario) for his victory in this Programmer's Challenge.

Ernst's entry performs a depth-first search of possible moves, enumerated by the GenerateMoveList routine. Moves are assigned a value that combines a heuristic weight assigned a priori to the type of move (e.g., kFreeToHome), a measure of the degree to which the cards in a tableau are in the correct order, and the presence in a tableau of cards that could be moved home. The code (IsNotRedundant) avoids moves that return a card to the position it occupied previously when no intervening move would have made the return nonredundant. A key to the speed of Ernst's entry is the way it avoids looping back into a previously encountered configuration. The Execute routine computes a hash value for the game state resulting from a prospective move and compares that hash value to that of previously encountered game states. If the prospective move results in a previously encountered state, the move is rejected. Assuming a move is not redundant, the move is made and a new set of possible moves is generated. The move search gives up and restarts if it is forced to backtrack too many times, using the list of previously encountered states to ensure that a different search path results.

As the top-placing contestant without a previous Challenge win, Greg Sadetsky wins a share of this month's Developer Depot merchandise credit prize. His second place solution also keeps track of past game states, but in a very large array instead of in a hash value. Greg employs a number of devices to reduce the storage required, but the resulting logic for detecting a repeat game state is more complex and time consuming. Greg's entry generates move sequences that are about 50% longer on average than those generated by Ernst's entry. It cuts off the search after 10 seconds, the point at which the time penalty exceeded the point value of solving the hand. As a result, his solution gave up on about 6% of the test cases.

The third entry I received this month was a recursive solution only slightly slower than the winning entry, but it crashed for 9 of the test cases. Even after I increased the heap and stack sizes significantly, the code crashed with heap corruption after apparently entering a recursion loop. To measure performance on the remaining cases, I needed to modify the test code to bypass the problematic hands and, for that reason, the entry was disqualified.

I tested the entries to this Challenge with more than 20,000 deals, including roughly one third of the 32,000 deals included in the Linux xfreecell package, 10,000 random deals, and a few manually constructed deals. Ernst's solution solved all but two of the test cases, both of which were a single deal that is known to be unsolvable. His solution required just over three minutes to run the entire set of tests, and generated an average of 156 moves to solve each deal. As you can see in the table below, a small number of test cases required more than 1500 moves to solve - the most complicated deal, excluding the ones that could not be solved, required 1863 moves.

>100 Moves (# of cases)>500 Moves (# of cases)>1000 Moves (# of cases)>1500 Moves (# of cases)No Solution (# of cases)
Ernst Munter181904442472
Greg Sadetsky1941078449111274
C. W.20303000278

The table below lists, for each of the solutions submitted, the number of test cases solved by each entry, the total execution time, the number of points earned, and the number of moves generated to solve the entire test suite. It also provides the code size, data size, and programming language used for each entry. As usual, the number in parentheses after the entrant's name is the total number of Challenge points earned in all Challenges prior to this one. The solution marked with an asterisk was disqualified for reasons explained above.

NameTest Cases SolvedTest Cases UnsolvedTime (secs)Points x100000Moves x1000Code SizeData SizeLang
Ernst Munter (681)206942181.1206.8322098001793C++
Greg Sadetsky (2)19422127424399.2169.84705815618.31MC
C. W. (*)20409278198.2203.9410372761858C

Top Contestants...

Listed here are the Top Contestants for the Programmer's Challenge, including everyone who has accumulated 10 or more points during the past two years. The numbers below include points awarded over the 24 most recent contests, including points earned by this month's entrants.

Rank Name Points
1. Munter, Ernst 271
2. Saxton, Tom 76
3. Maurer, Sebastian 68
4. Rieken, Willeke 65
5. Boring, Randy 52
6. Shearer, Rob 48
7. Taylor, Jonathan 36
8. Wihlborg, Charles 29

... and the Top Contestants Looking For a Recent Win

Starting this month, in order to give some recognition to other participants in the Challenge, we are also going to list the high scores for contestants who have accumulated points without taking first place in a Challenge. Listed here are all of those contestants who have accumulated 6 or more points during the past two years.

9. Downs, Andrew 12
10. Jones, Dennis 12
11. Day, Mark 10
12. Duga, Brady 10
13. Fazekas, Miklos 10
14. Flowers, Sue 10
15. Sadetsky, Gregory 10
16. Selengut, Jared 10
17. Strout, Joe 10
18. Hala, Ladislav 7
19. Miller, Mike 7
20. Nicolle, Ludovic 7
21. Schotsman, Jan 7
22. Widyyatama, Yudhi 7
23. Heithcock, JG 6

There are three ways to earn points: (1) scoring in the top 5 of any Challenge, (2) being the first person to find a bug in a published winning solution or, (3) being the first person to suggest a Challenge that I use. The points you can win are:

1st place 20 points
2nd place 10 points
3rd place 7 points
4th place 4 points
5th place 2 points
finding bug 2 points
suggesting Challenge 2 points

Here is Ernst's winning FreeCell solution:

FreeCell.cp
Copyright © 2000
Ernst Munter, Kanata, ON, Canaca

/*
Solves FreeCell games by a guided trial and error search.  

At each stage, all possible moves are listed, ranked according to a fixed heuristic which
prefers moves towards home, and towards aggregating strings of alternating colors on the
tableau.

All reached states are recorded in a database to avoid loops.  The hash method to compress
states takes care of some redundancies;  for example it does not care which column a
particular set of cards is in, and it distinguishes cards only bycolor, not suit.  

If a search is making little progress, it is cut off after a specific number of undo
steps, and a fresh search started.  The same happens when the maximum number of moves has
been reached.  The new search still respects the accumulated database of previously seen
states, and so is forced to take a different path, improving its chances.  

The resulting move sequences are not optimal, and certainly not elegant.  The search also
does not include macro moves (moving columns of several cards).  I tried this but it was
counter-productive:  by listing the macro moves, the move lists became longer, and more
false paths ended up being explored. 

Version 2 changes
---------
- replaced the STL set<> with a simpler, faster custom set;
- replaced qsort (of move lists) with an integrated custom heap sort;
- policy constants tuned.

Version 3 change
--------
Reduced the amount of redundant moves by scanning back through the move stack to avoid any
move that would simple put a card back where it was earlier.  Such moves are truly
redundant if the to- and from- card positions were not used by intermediate moves of other
cards.  This strategy improved both time, and average number of moves to solve, by about
18%.
*/

#include "FreeCell.h"
#define NDEBUG
#include <assert.h>
#include <string.h>   // for memset()

#define VERSION 3

// I need to have the suits in alternating red-black order.
enum {  
   mySpade=0,myHeart=16,myClub=32,myDiamond=48,mySuits=48,
                              myRed=16,
   myNull=0,myA=1,my2,my3,my4,my5,my6,my7,my8,my9,myT,myJ,myQ,myK,
   mySpots=15,   kSignificant=myRed|mySpots
};

typedef unsigned char MyCard;// 2 bits suit + 4 bits spot 
typedef unsigned char uchar;
typedef unsigned long ulong; 
typedef unsigned short ushort; 

enum {
   kFreeCell=0,   // a single set of 16 card stacks defines the tableau
   kTableau=4,      // card stack offsets
   kHome=12,      // home must be last group
   
   kAvgMoveListLength=16,// just an estimate
   
// Policy constants affect the order in which moves are tried:
   kFreeToHome=10000,
   kTableauToHome=10000,
   kTableauToTableau=2000,
   kFreeToTableau=500,
   kFreeToEmptyTableau=500,
   kTableauToEmptyTableau=50,
   kTableauToFree=24,   
   kSrcPriority=2000,
   kBlockedOnly=0,
   
   kLongestPossibleMoveList=63,// actually no more than 31 have been observed
   kUndoLimitMul=16,
   kMaxRestartsDiv=65536
};

inline MyCard MakeCard(int spot,int suit)
      {return spot | (suit<<4);}
inline int MySuit(MyCard c) {return c>>4;}

struct CRC
// Standard CRC based hash method.  
static struct CRC {
     enum {POLYNOMIAL=0x04c11db7L};
     ulong table[256];
     CRC() 
     {
       long i,j,x;
       for (i=0;i<256;i++) {
            x=i<<24;
            for (j=0;j<8;j++) {
              if (x<0) x=(x<<1) ^ POLYNOMIAL;
              else x=(x<<1); 
            }
            table[i]=x;
       }
     }
   ulong HashFunction(const uchar* ufrg,int frgLen,int type) const
   {
// Uses CRC on length type, and all chars of a fragment
        ulong accum=table[frgLen]; 
       for (int i=0;i<frgLen;i++)
          accum=(accum<<8) ^ table[(accum>>24) ^ 
                           (kSignificant & ufrg[i])];
       accum=(accum<<8) ^ table[(accum>>24) ^ type];
       return type + accum;
   }
} crc;

struct Legal
// A pair of lookup tables to indicate legality of placng one card upon another.
static struct Legal {
   bool   redBlack[64][64];         // legal to put second card on (first) in tableau
   bool   inSequence[64][64];      // legal to send second card home (first)
   Legal()
   // setup  red-black and inSequence card lookup tables
   {
      for (int first=(myNull|mySpade);
                  first<=(myK|myDiamond);first++)
      {
         for (int second=(myA|mySpade);
                        second<=(myK|myDiamond);second++)
         {
            if ( ((mySpots & (first - second))==1) && 
                ((myRed & (first ^ second))==myRed) )
               redBlack[first][second]=true;
            // else =0;
            if ( ((mySpots & (second - first))==1) && 
                ((mySuits & (first ^ second))==0) )
               inSequence[first][second]=true;
            // else =0;
         }
      }
   }
} gLegal;

inline MyCard Convert2MyCard(const Card c)
// converts a "Card" defined in "FreeCell.h" to an instance of "MyCard"
{
   switch (c.suit)
   {
case kSpade:   return mySpade   | c.spot; 
case kHeart:   return myHeart   | c.spot;
case kDiamond:   return myDiamond | c.spot;
case kClub:      return myClub    | c.spot;
   }
   return 0;
}

struct CardStack
struct CardStack {
// Generic card stack, serving for tableau, freecell, and home columns
   MyCard*   SP;   
   uchar   stackType;
   MyCard   cards[27];// only 19 needed, struct is padded out to 32 bytes 
   void Init(const Tableau * theTableau,int num,int type)
   {
      stackType=type;
      SP=cards;
      if (theTableau)
      for (int i=0;i<num;i++)
         *SP++=Convert2MyCard(theTableau->theCard[i]);
   }
   void InitHome(int suit)
   {
      stackType=kHome;
      SP=cards+1;
      cards[0]=MakeCard(myNull,suit);// null card of correct suit to build upon
   }
   MyCard TopCard() const {return SP[-1];}
   ulong Hash() const 
   {
      return crc.HashFunction(cards,NumCards(),stackType);
   }
   bool IsEmpty() const {return SP==cards;}
   void Add(MyCard c)
   {
      assert(NumCards()<19);
      *SP++=c;   
   }
   MyCard Remove()
   {   
      assert(SP>cards);
      return *-SP;   
   }
   int AllInOrder() 
   // If the entire tableau stack is in order, returns numCards.
   // If not, this function returns 0.
   {
      int num=0;
      if (SP>cards)
      {
         num++;
         MyCard* c1=SP-1;
         while (c1>cards)
         {
            MyCard* c2=c1-1;
            if (!gLegal.redBlack[*c2][*c1])
               return 0;
            num++;
            c1=c2;
         }
      }
      return num;
   }
   int NumInOrder()
   // Returns the number of cards at the top of the stack which are in order.
   {
      int num=0;
      if (SP>cards)
      {
         num++;
         MyCard* c1=SP-1;
         while (c1>cards)
         {
            MyCard* c2=c1-1;
            if (!gLegal.redBlack[*c2][*c1])
               break;
            num++;
            c1=c2;
         }
      }
      return num;
   }
   int SourcePriority(MyCard home[])
// Scans the stack including (or excluding) the top card, to set a priority value 
// for the stack if it contains cards that could go home right away.
// kBlockedOnly=1 limits priority to blocked cards.
// Returns the priority value
   {
      int srcPriority=0;
      MyCard* cp=cards;
      for (;cp<SP-kBlockedOnly;cp++)
      {
         MyCard c=*cp;
         for (int k=0;k<4;k++)
         {
            if (c==home[k])
               srcPriority+=kSrcPriority;
         }
      }
      return srcPriority;
   }
   int NumCards() const {return SP-cards;}
};

struct MyMove
struct MyMove {
// My move is represented in a  32-bit ulong
   ulong   gameValue:16;   // value of this move or cardToMove
   ulong   toPile:8;
   ulong   fromPile:8;   
   void Init(int from,int to,int val)
   {
      gameValue=val;
      toPile=to;
      fromPile=from;
   }
   void Clear() {fromPile=toPile=gameValue=0;}
   ulong IsValid() const {return Int();}// Null-move indicated by all-0 fields
   ulong FromPile() const {return fromPile;}
   ulong ToPile() const {return toPile;}
   void SetValue(MyCard c) {gameValue=c;}
   bool IsInverseOf(MyMove m) const {
      return ((fromPile == m.toPile) && (toPile == m.fromPile));
   }
   bool ToHome() const {return (toPile>=kHome);}
   void MoveCard(CardStack* stacks)
   {
      assert(stacks[fromPile].NumCards());
      assert(stacks[toPile].NumCards()<19);
      MyCard c=stacks[fromPile].Remove();
      stacks[toPile].Add(c);
   }
   void UndoMove(CardStack* stacks)
   {
      assert(stacks[toPile].NumCards());
      assert(stacks[fromPile].NumCards()<19);
      MyCard c=stacks[toPile].Remove();
      stacks[fromPile].Add(c);
   }
   void Convert(Move* m)
   // Converts this instance of "MyMove" to a "Move" as defined in "FreeCell.h"
   {
      m->theSource = Source(fromPile-kFreeCell+dFreeCellA);
      m->theDestination = (toPile>=kHome) ? dHome:
         Destination(toPile-kFreeCell+dFreeCellA);
   }
   int Int() const {return *((int*)this);}// cast all three fields as single int
};
typedef MyMove* MyMovePtr;

inline bool operator > (const MyMove & a,const MyMove & b) {return a.Int() > b.Int();}

struct MoveHeap
// The custom heap for sorting moves.
struct MoveHeap {
   int      heapSize;
   MyMove   heapBase[kLongestPossibleMoveList];
   MoveHeap() : heapSize(0) {}
   int Size() const {return heapSize;}
   
   void Insert(MyMove k) 
   {
       int i=++heapSize;
       int j=i>>1;
       MyMove z;
       while (j && ((z=heapBase[j]) > k) )
       {
            heapBase[i]=z;     
             i=j;
            j=i>>1;
       }
       heapBase[i]=k;    
     }
  
     MyMove Pop() 
     {
       MyMove rc=heapBase[1];
       MyMove k=heapBase[heapSize-];
       if (heapSize<=1) {
            heapBase[1]=k;            
            return rc;
       }
       int i=1,j=2;
       while (j<=heapSize) 
       {
            if ((j<heapSize)
            && (heapBase[j] > heapBase[j+1]))
           j++;
            if (heapBase[j] > k)
              break;
            heapBase[i]=heapBase[j];  
            i=j;j+=j;
       }
       heapBase[i]=k;        
       return rc;
     }
};

struct Bucket
// The set (MySet below) is implemented as a hash table of buckets.
// Each bucket can hold kBucketSize values, and can be extended indefinetely
// by linking to additional buckets.
enum {kBucketSize=17,kNumBuckets=1024};
struct Bucket {
   int      numEntries;
   Bucket*   link;
   ulong   entry[kBucketSize];
   // bucket size of 9 or 17 makes full use of allocated memory (CW 6)
   Bucket(ulong firstEntry) :
      numEntries(1),link(0) {entry[0]=firstEntry;}
   ~Bucket() {if (link) delete link;}
   void Insert(ulong x)
   // Insert x only if x is not in the set already
   {
      Bucket* b=Find(x);
      if (b==0) return;
      b->Add(x);
   }
   Bucket* Find(ulong x)
   // Scans this and linked buckets looking for x 
   // Returns 0 if found, returns this if not found
   {
      ulong* ep=entry+numEntries;
      do {
         if (*-ep == x) return 0;
      } while (ep>entry);
      if (link) return link->Find(x);
      return this;
   }
   void Add(ulong x)
   {
      if (numEntries < kBucketSize)
         entry[numEntries++]=x;
      else
         link=new Bucket(x);
   }
};

struct MySet
struct MySet {
// A set to record all states (represented by their hash value) which have occurred.
   Bucket*   buckets[kNumBuckets];
   MySet(){memset(buckets,0,sizeof(buckets));}
   ~MySet(){
      for (int i=0;i<kNumBuckets;i++) 
      {
         Bucket* b=buckets[i];
         if (b) delete b;
      }
   }
   void Insert(ulong x)
   {
      Bucket* b=buckets[x % kNumBuckets];
      if (b==0) 
      {
         b=new Bucket(x);
         buckets[x % kNumBuckets]=b;
      } else   b->Insert(x);
   }
   bool Find(ulong x)
   {
      Bucket* b=buckets[x % kNumBuckets];
      return (b && (0==b->Find(x)));
   }
};

struct MyGame
struct MyGame {
// MyGame is the top level struct which holds all local data
   CardStack   stacks[16];   //    my version of the tableau, the current state
   ulong      hashedState;      //   current state, compressed 
   long      numCardsOutstanding;
   MyMove*      movePool;         //   single pool allocated for movelists
   MyMove*     endMovePool;   
   MyMovePtr*   moveStack;      //   move stack tracks the history of executed moves
   MyMovePtr*   moveStackPointer;
   MyMovePtr*   lastMoveStack;
   MyCard       nextHome[4];   //    next cards (1 per suit) to go home
   MySet      stateSet;            //   all visited states are recorded in this set, as hash values
   MyGame(long maxMoves) :
      movePool(new MyMove[kLongestPossibleMoveList+
                                 maxMoves*kAvgMoveListLength]),
      endMovePool(movePool+kLongestPossibleMoveList+
                                 maxMoves*kAvgMoveListLength),
      moveStack(new MyMovePtr[maxMoves]),
                                 moveStackPointer(moveStack),
      lastMoveStack(moveStack+maxMoves-1)
   {}
   
   ~MyGame(){
      delete [] moveStack;
      delete [] movePool;
   }
   
   void InitTableau(const Tableau theTableau[8])
// Copies the initial tableau to the local representation
   {
      for (int tid=0;tid<8;tid++) 
         stacks[tid+kTableau].Init(&theTableau[tid],
                                                         7-tid/4,kTableau);
      numCardsOutstanding=52;
      for (int i=0;i<4;i++)
      {
         stacks[i+kFreeCell].Init(0,0,kFreeCell);
         stacks[i+kHome].InitHome(i);
         nextHome[i]=MakeCard(myA,i);
      }
      hashedState=Hash();
   }
   
MyGame::Hash
   ulong Hash() const
// Hashes the game state into a single 32-bit integer
   {
      const CardStack* cs=stacks;
      ulong h=cs->Hash();
      for (int i=1;i<16;i++,cs++)
         h ^= cs->Hash();
      return h;
   }
   
MyGame::GenerateMoveList
   MyMove* GenerateMoveList(MyMove* mp)
   {
//   Lists all legal moves in a list, starting with a null-move;
//   sorts the moves and returns the highest value move on the list 
//   Each move is given a "value" reflecting its relative merit. 
      if (mp+kLongestPossibleMoveList >= endMovePool)             
         return 0; // no room for movelist, should not really happen
                             // but if it does, we just have to backtrack   
      MyMove m;
      MoveHeap heap;
      int src,dest;
      CardStack* srcPtr;
      CardStack* destPtr;
      int cardToMove,topCardDest,value,srcPriority;
      
      for (src=kFreeCell,srcPtr=stacks+src;
                     src<kFreeCell+4;src++,srcPtr++)
      // from any freecell to: home, or tableau
      {                                                   
         if (srcPtr->IsEmpty()) continue;
         cardToMove=srcPtr->cards[0];
         srcPriority=srcPtr->SourcePriority(nextHome);
         
         topCardDest=stacks[kHome+MySuit(cardToMove)].TopCard();
         if (gLegal.inSequence[topCardDest][cardToMove])
                                       // to correct home
         {
            value = kFreeToHome + 
                              srcPriority;
            m.Init(src,MySuit(topCardDest)+kHome,value); 
            heap.Insert(m); 
         }
         
         bool toEmptyFlag=true;
         for (dest=kTableau,destPtr=stacks+dest;
                        dest<kTableau+8;dest++,destPtr++)   
         // to every matching tableau
         {                                                                              
            if (destPtr->IsEmpty())
            {
               if (toEmptyFlag)
               {
                  value = kFreeToEmptyTableau + 
                                    (2<<(cardToMove&mySpots)) +
                                    srcPriority;
                  m.Init(src,dest,value);
                  heap.Insert(m);       
                  toEmptyFlag=false;
               }
               continue;
            }
            topCardDest=destPtr->TopCard();
            if (gLegal.redBlack[topCardDest][cardToMove])
            {
               value = kFreeToTableau + 
                                 destPtr->AllInOrder() +
                                 srcPriority;   
               m.Init(src,dest,value);
               heap.Insert(m); 
            }
         }
      }            

      for (src=kTableau,srcPtr=stacks+src;
                     src<kTableau+8;src++,srcPtr++)
      // from any tableau to: freecell, home or tableau 
      {                                                      
         if (srcPtr->IsEmpty()) continue;
         int srcInOrder=srcPtr->AllInOrder();
         int longestInOrder=srcPtr->NumInOrder();
         srcPriority=srcPtr->SourcePriority(nextHome);
         int maxBlock=0;
         
         cardToMove=srcPtr->TopCard();// single card moves
         topCardDest=stacks[kHome+MySuit(cardToMove)].TopCard();
         if (gLegal.inSequence[topCardDest][cardToMove])
                                          // to matching home 
         {
            value = kTableauToHome +
               srcPriority;
            m.Init(src,MySuit(topCardDest)+kHome,value);
            heap.Insert(m);    
         }
         
         for (dest=kFreeCell,destPtr=stacks+dest;
                        dest<kFreeCell+4;dest++,destPtr++)   
         // to first available freecell
         {                                                   
            if (destPtr->IsEmpty())
            {
               value = kTableauToFree - 
                  srcInOrder - 
                  4*longestInOrder + 
                  srcPriority;
               m.Init(src,dest,value);      
               heap.Insert(m);    
               break;   
            }
         }
         
         bool toEmptyFlag=true;
         for (dest=kTableau,destPtr=stacks+dest;
                     dest<kTableau+8;dest++,destPtr++)   
         // to every matching tableau
         {                                                   
            if (src==dest) continue;
            if (destPtr->IsEmpty()) // to empty tableau
            {
               if (toEmptyFlag)
               {
                  value = kTableauToEmptyTableau + 
                     srcInOrder +
                     (2<<(mySuits & cardToMove)) +
                     srcPriority;
                  m.Init(src,dest,value);      
                  heap.Insert(m);    
                  toEmptyFlag=false;
               }
               continue;
            }
            
            topCardDest=destPtr->TopCard();
            if (gLegal.redBlack[topCardDest][cardToMove])
            {         
               value = kTableauToTableau +
                  destPtr->AllInOrder() -
                  4*srcInOrder +
                  srcPriority;
               m.Init(src,dest,value);
               heap.Insert(m); 
            }
         }
      }      
      
      mp->Clear();               // puts a sentinel 0-move at the start of the movelist
      
      while (heap.Size())   // sorts moves from heap into the movelist space
         *++mp = heap.Pop();
      
      return mp;
   }
   
   void PushMove(MyMove* m){
      *moveStackPointer++=m;
   }
   
   MyMove* PopMove()
   {
      assert(moveStackPointer>moveStack);
      return *-moveStackPointer;
   } 
   
MyGame::Execute
   int Execute(MyMove* mp)
   {
// Attempts to execute one move.
// Return codes:
//      -2:  failed, cannot push the last move because the move stack is full
//      -1:    failed, would have reached a previous state
//       0:  success, final move and game solved
//       >0:  normal execution succeeded
      MyMove m=*mp;
      stateSet.Insert(hashedState);   // save last state in hashed state set         
      
      if (moveStackPointer >= lastMoveStack)
         return -2;
         
      if (m.ToHome() && (numCardsOutstanding==1)) // The game is solved.
      {
         PushMove(mp);      
         return 0;
      }       
      
      // do the move and compute a new hashed state
      ulong newHash=hashedState ^ 
         stacks[m.FromPile()].Hash() ^ 
         stacks[m.ToPile()].Hash();
      
      MyCard cardToMove=stacks[m.FromPile()].TopCard();
      m.MoveCard(stacks);
      
      newHash ^= 
         stacks[m.FromPile()].Hash() ^ 
         stacks[m.ToPile()].Hash();
   
      if (stateSet.Find(newHash))
      {
         m.UndoMove(stacks);            
         return -1;
      } else 
      {
         hashedState=newHash;// record new hash value
         mp->SetValue(cardToMove);
         PushMove(mp); 
         if (m.ToHome())
         {
            nextHome[m.ToPile()-kHome]++;
            numCardsOutstanding-;
         }
      }
      return 1;
   }
   
   MyMove* Undo()
// Undoes the last stacked move, returns this move, or 0 if no move found   
   {
      MyMove* mp=PopMove();
      if (mp==0) return mp;
      MyMove m=*mp;
      ulong newHash=hashedState ^ 
         stacks[m.FromPile()].Hash() ^ 
         stacks[m.ToPile()].Hash();

      m.UndoMove(stacks);
      if (m.ToHome())
      {
         nextHome[m.ToPile()-kHome]-;
         numCardsOutstanding++;
      }
      
      hashedState=newHash ^ 
         stacks[m.FromPile()].Hash() ^ 
         stacks[m.ToPile()].Hash();
      
      return mp;
   }
   
   long CopyMovesBack(Move theMoves[])
// Scans movestack, converts MyMoves to Moves, and returns the number of moves   
   {
      int numMoves=0;
      MyMovePtr* endMoveStack=moveStackPointer;
      for (MyMovePtr* index=moveStack+1;index<endMoveStack;index++)
      {
         MyMove* mp=*index;
         mp->Convert(theMoves+numMoves);
         numMoves++;
      }
      return numMoves;
   }
   
   int IsNotRedundant(MyMove m)
   {
      int from=m.FromPile();
      int to=m.ToPile();
      MyCard cardToMove=stacks[from].TopCard();
       MyMovePtr* mps=moveStackPointer;
      while (mps>moveStack)
      {
         MyMove* oldMove=*-mps;
         int oldFrom=oldMove->FromPile();
         int oldTo=oldMove->ToPile();
         MyCard oldCard=oldMove->gameValue;
         if (oldCard==cardToMove)
         {
            return ((oldTo^from) | (oldFrom^to));
         } else
         {
            if ((oldFrom==to)||(oldTo==to)||(oldFrom==from))
               break;
         }
      }
      return 1;
   }
   
   long Solve(const Tableau theTableau[8],Move theMoves[],long maxMoves)
   {
// Solves the game by systematic depth-first exploration of the move tree
// Several fresh starts are possible if the move stack is exhausted
// or if the search seems to be stuck with a large number of backtracks
// In any case, all visited states are recorded in the hashed state set,
// and never entered twice.  The hash is not perfect, and some states might
// be accidentally excluded.  It is hoped that there is always enough redundancy in
// the possible solution sequences to allow an alternative solution to be found.
      int cycle=kMaxRestartsDiv/maxMoves,rc;
      do {
         int undoLimit=kUndoLimitMul*maxMoves;
         InitTableau(theTableau);
         moveStackPointer=moveStack;   
         // Put a sentinel null move at start of move stack      
         PushMove(0);
         MyMove* moveList=movePool;
#if VERSION<3
         MyMove previousMove;
         previousMove.Clear();
#endif
         
get_new_movelist:   
         MyMove* nextMove=GenerateMoveList(moveList);
      // moveList to nextMove defines a movelist which always starts with a 0-move
      // and is processed in order nextMove, nextMove-1, ... until 0-move is found
         for (;;) 
         {
            while (nextMove && nextMove->IsValid())
            {
#if VERSION>=3
               if (!IsNotRedundant(*nextMove))
#else
               if (nextMove->IsInverseOf(previousMove))
#endif
               {
                  nextMove-;
                  continue; // while
               } 
               rc=Execute(nextMove);
               if (rc==-1) // would have reached a previous state
               {
                  nextMove-;   // use next best move in list            
                  undoLimit-;
                  if (undoLimit<=0) // enough! let's restart
                     goto restart_search;
               } else
                  
               if (rc>0)// move was executed, get next movelist
               {   
                  moveList=1+nextMove;
#if VERSION<3   
                  previousMove=*nextMove;   
#endif   
                  goto get_new_movelist;
               } else 
                  
               if (rc==0) // copy moves back for the caller and return
                  return CopyMovesBack(theMoves);
                  
               else // else rc<=-2: move stack is full
               {
                  goto restart_search; 
               }
                  
            } // end while
            
         // no move is possible, try to backtrack
            do {
               MyMove* prevMove=Undo();
               if (!prevMove)  // no solution!, stack is completely unwound
                  return 0;
               
            // try to use the last move:
               nextMove = prevMove-1;
               assert(nextMove>=movePool);
               assert(nextMove<moveList);
            } while (!nextMove->IsValid());
            
            moveList=nextMove;
            while ((moveList>=movePool) && (moveList->IsValid()))
               moveList-;
            assert(moveList>=movePool);
         }
restart_search:;   
      } while (-cycle > 0);    // restart only so many times
      return 0;            // then give up and return 0
   }
};

FreeCell
long  FreeCell(   // returns the number of moves in theMoves[]
   const Tableau   theTableau[8],
   Move    theMoves[],
   long   maxMoves
) {
   MyGame* G=new MyGame(maxMoves);                        
   long numMoves=G->Solve(theTableau,theMoves,maxMoves);         
   delete G;
   return numMoves;
}
 
AAPL
$98.81
Apple Inc.
-0.37
MSFT
$45.76
Microsoft Corpora
-0.14
GOOG
$564.44
Google Inc.
-3.83

MacTech Search:
Community Search:

Software Updates via MacUpdate

TextSoap 7.4.2 - Flexible text editing u...
TextSoap is for people who work with text. TextSoap effortlessly cleans up text from endlessly different formats. Wash away unwanted characters, spaces, tabs. Fix paragraphs with hard returns at the... Read more
Dropbox 2.10.30 - Cloud synchronization...
Dropbox is an application that creates a special Finder folder that automatically syncs online and between your computers. It allows you to both backup files and keep them up-to-date between systems... Read more
Twitter 3.1 - Official Twitter client fo...
Twitter (was Tweetie) is a Twitter client with a variety of features. Important Note: As of January 2011, AteBit's Tweetie application has been acquired and renamed by Twitter. Version 1.2.8 of the... Read more
Cocktail Family License (5 Macs) 7.6.1 -...
Cocktail is a general purpose utility for OS X that lets you clean, repair and optimize your Mac. It is a powerful digital toolset that helps hundreds of thousands of Mac users around the world get... Read more
Cocktail 8.0 Beta 2 - General maintenanc...
Cocktail is a general purpose utility for OS X that lets you clean, repair and optimize your Mac. It is a powerful digital toolset that helps hundreds of thousands of Mac users around the world get... Read more
QuickBooks 2015 16.0.0.1352 R1 - Financi...
QuickBooks 2015 helps you manage your business easily and efficiently. Organize your finances all in one place, track money going in and out of your business, and spot areas where you can save.... Read more
Mac DVDRipper Pro 5.0.1 - Copy, backup,...
Mac DVDRipper Pro is the DVD backup solution that lets you protect your DVDs from scratches, save your batteries by reading your movies from your hard disk, manage your collection with just a few... Read more
Apple OS X bash Update 1.0 - Fix for sec...
The OS X bash Update fixes a security flaw in the bash UNIX shell on OS X 10.9.5 (also on OS X 10.8 and 10.7 [see Related Links below]). OS X 10.9.5 or later Downloads for OS X 10.8 and OS X 10.7 in... Read more
SyncTwoFolders 2.0.5 - Syncs two user-sp...
SyncTwoFolders simply synchronizes two folders. It supports synchronization across mounted network drives and it is a possibility to run a simulation showing in a log what will be done. Please visit... Read more
FinderPop 2.5.7 - Classic Mac utility, n...
FinderPop is a Universal preference pane that extends OS X's contextual menus using a FinderPop Items folder much as the Apple Menu Items folder used to do for the Apple menu. It has other features... Read more

Latest Forum Discussions

See All

PDF Expert 5 Has Been Updated for iOS 8
PDF Expert 5 Has Been Updated for iOS 8 Posted by Jessica Fisher on October 2nd, 2014 [ permalink ] Universal App - Designed for iPhone and iPad | Read more »
A.R. Witham on Black Jack – The ‘World’s...
iBooks and the Kindle app do a great job of ensuring that there’s always something new to read while you’re on the move. They work well in complementing the traditional physical book. There’s still room for more interactive and animated fare though... | Read more »
Kawaii Killer Plushy Edition (Games)
Kawaii Killer Plushy Edition 1.22 Device: iOS Universal Category: Games Price: $2.99, Version: 1.22 (iTunes) Description: Kawaii Killer is an intuitive & fun game taking place in the Kawaii Forest, which is plagued by evil... | Read more »
Ms.Pac-Man Goes Pink for National Breast...
Ms.Pac-Man Goes Pink for National Breast Cancer Foundation Campaign Posted by Ellis Spice on October 2nd, 2014 [ permalink ] | Read more »
The Maze Runner Review
The Maze Runner Review By Lee Hamlet on October 2nd, 2014 Our Rating: :: A NICE CHANGE OF PACEUniversal App - Designed for iPhone and iPad The Maze Runner is a surprisingly enjoyable movie tie-in that will succeed in keeping... | Read more »
RPG Soul of Deva (Games)
RPG Soul of Deva 1.0.0 Device: iOS Universal Category: Games Price: $3.99, Version: 1.0.0 (iTunes) Description: SPECIAL PRICE56% OFF(USD 8.99 -> USD 3.99)!!! Demons attack humans, and humans live in fear of them...Set off on a... | Read more »
Banner Saga (Games)
Banner Saga 1.0.17 Device: iOS Universal Category: Games Price: $9.99, Version: 1.0.17 (iTunes) Description: NOTE: The Banner Saga does NOT run on iPhone 4. iPhone 4S and more modern devices recommended. | Read more »
Beatbuddy HD (Games)
Beatbuddy HD 1.0.2 Device: iOS Universal Category: Games Price: $4.99, Version: 1.0.2 (iTunes) Description: **IMPORTANT** Beatbuddy runs only on iPhone 6, 6 Plus, 5, 5c, 5s, iPad 4, iPad Mini Retina and iPad Air. | Read more »
Spirits of Spring (Games)
Spirits of Spring 1.0.1 Device: iOS Universal Category: Games Price: $4.99, Version: 1.0.1 (iTunes) Description: From the creators of the award-winning empathy game, Papo & Yo, comes a tale about finding strength. | Read more »
I am a brave knight (Games)
I am a brave knight 1.0 Device: iOS Universal Category: Games Price: $.99, Version: 1.0 (iTunes) Description: Do you have ten minutes to live a life? | Read more »

Price Scanner via MacPrices.net

Apple drops prices on refurbished 27-inch iMa...
The Apple Store has dropped prices on Apple Certified Refurbished 27″ iMacs, now available for up to $340 off the cost of new models. Apple’s one-year warranty is standard, and shipping is free: - 27... Read more
Logitech Type+ iPad Air Keyboard Case: Laptop...
If you want to make your iPad Air look and feel more like a laptop for productivity use, as well as protect it from impacts, spills, and scratches while on the move, the new Logitech Type+, a... Read more
ASUS, Lenovo, and Amazon Slug It Out For Tabl...
According to market intelligence firm ABI Research, Apple and Samsung have led the touchscreen tablet market by a substantial margin since Apple energized the category back in 2010. However, ABI says... Read more
Branded Tablet Growth Expected to Disappoint...
ABI Research says the 200 million annual shipments milestone for branded tablets continues to elude OEM vendors, and overall growth for 2014 is set to come in at a disappointing 2.5 percent. Apple... Read more
Amazon offers 13-inch MacBook Air for $899, $...
Amazon.com has the 13″ 1.4GHz 128GB MacBook Air on sale for $100 off MSRP including free shipping: - 13″ 1.4GHz 128GB MacBook Air: $899.99 Read more
Apple resting On Its iPhone Laurels? – The ‘B...
Apple calls its new iPhone 6 and 6 Plus “The Biggest Advancements in iPhone History,” but does reality live up to the hype? “Seldom have so many waited so breathlessly for so little,” tweeted veteran... Read more
Roundup of Apple Mac and iPad Education disco...
Purchase a new Mac or iPad at The Apple Store for Education and take up to $300 off MSRP. All teachers, students, and staff of any educational institution qualify for the discount. Shipping is free,... Read more
Apple Boycotts German Magazine Computer Bild...
Apple has revoked its PR accreditation of Germany’s Computer Bild, Europe’s best-selling PC magazine, in reaction to Bild’s posting of a “#Bentgate” YouTube video. Axel Telzerow, editor in chief of... Read more
iPhone 6 & iPhone 6 Plus Available in Chi...
Apple has announced that iPhone 6 and iPhone 6 Plus will be available in China beginning Friday, October 17 from the Apple Online Store (http://www.apple.com), Apple’s retail stores, and an expansive... Read more
MacBook Airs on sale for $100 off MSRP, start...
Best Buy has the new 2014 MacBook Airs on sale for $100 off MSRP on their online store. Choose free home shipping or free local store pickup (if available). Prices valid for online orders only, in-... Read more

Jobs Board

*Apple* Retail - Multiple Positions (US) - A...
Sales Specialist - Retail Customer Service and Sales Transform Apple Store visitors into loyal Apple customers. When customers enter the store, you're also the Read more
*Apple* Retail - Multiple Positions (US) - A...
Job Description: Sales Specialist - Retail Customer Service and Sales Transform Apple Store visitors into loyal Apple customers. When customers enter the store, Read more
Senior Event Manager, *Apple* Retail Market...
…This senior level position is responsible for leading and imagining the Apple Retail Team's global event strategy. Delivering an overarching brand story; in-store, Read more
*Apple* Solutions Consultant (ASC) - Apple (...
**Job Summary** The ASC is an Apple employee who serves as an Apple brand ambassador and influencer in a Reseller's store. The ASC's role is to grow Apple Read more
Project Manager / Business Analyst, WW *Appl...
…a senior project manager / business analyst to work within our Worldwide Apple Fulfillment Operations and the Business Process Re-engineering team. This role will work Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.