Volume Number: 17 (2001)
Issue Number: 05
Column Tag: Programmer's Challenge

by Bob Boonstra, Westford, MA

I'll admit it. I got into programming in an unusual way. Predating the web by a few (!) years, I didn't start with HTML or Perl. Nor, unlike some of my colleagues, did I start with a PC with toggle switches where the keyboard input should have been and with LED output instead of a video port. No, I actually started by reverse engineering machine code programs, and then discovering assembly language, and only later high level languages like FORTRAN and COBOL.

But somehow, through all that, I missed BASIC as a language, only discovering it much later, and never developing much of an attraction for it. But BASIC hasn't gone away, it is still alive and kicking as a modern object-oriented development environment. This month we're going to have some fun with BASIC, courtesy of the folks at REAL Software.

We've been using CodeWarrior for the Challenge for some time now, starting with C, expanding to C++, and allowing Pascal even though Metrowerks (or should I say Motorola) has deprecated that language. We've accepted Java solutions, although with some restrictions. But we've never even considered BASIC - after all, BASIC is a beginner's language, not used by serious programmers, right? Well, maybe not.

It turns out that there are real applications being written in BASIC. I discovered one, MacDynDNS, when I was forced to change DSL providers to one that didn't grant static IP addresses. So, when I was contacted by the folks at REAL Software about holding a REALbasic Challenge, I decided to experiment with their environment.

We're not in the business of endorsing products, but a little experimentation demonstrates that REALbasic is pretty cool. It converts BASIC into a fully object oriented language, and the environment does a surprising amount of the work required to create an application for you. They provide a nice tutorial that helps you quickly start using the environment. And they offer a free 30-day demo (see http://www.realbasic.com which we're going to take advantage of with this month's Challenge.

The prototype for the code you should write is ..., well, there isn't one. Your task is to build a REALbasic application that lets me play the card game Klondike. Klondike is a solitaire card game, the object of which is to build up all 52 cards onto four foundation piles in ascending order, by suit, from the Ace to the King. As a reference implementation for what constitutes legal play, I'm using the shareware game by Mike Casteel available at www.casteel.org. The requirements? You need to display a graphical representation of the game - the cards in the tableau, the four foundation piles, the deck, and the top three cards revealed from the deck. You need to support playing cards and stacks of cards by dragging them from one pile to another. You should highlight the destination when a card is dragged to a position where it can legally be played and, of course, allow only legal moves to be made. You need to provide multiple levels of Undo and Redo. You should provide menu items to start a new game, to replay the previous game, to save the game state, and to resume playing a previously saved game. Your application should be user friendly, warning the user, for example, when s/he is about to quit an unfinished game. You should provide preference controls that allow me to turn over one card at a time instead of the usual three and control whether scoring is displayed.

How will I score this Challenge? This Challenge will be a departure from our usual reliance on execution time and program size. Apart from the requirement that the solution be "correct", the winner will be chosen based on features, usability, and elegance. As options, you might automatically detect when the game has been won. You can optionally play music. You can add attractive features that you think might gain my favor. The Challenge prize will be divided between the overall winner(s) and the best scoring entry from a contestant that has not won the Challenge recently.

And I'd appreciate hearing from you on what you think of this experiment in language and in scoring. If it proves to be popular, perhaps we'll try some more experiments like this one.

Three Months Ago Winner

Eight people entered the February Trilite Challenge, a two-player game resembling Tic-Tac-Toe, but with the restriction that each player can occupy at most three positions on the board. Congratulations to Jonny Taylor for taking first place, narrowly beating out the entry from Challenge points leader Ernst Munter. Both Jonny and Ernst realized that the player making the first move has a guaranteed win, and each won all of their games when playing first. Jonny, however, lost only to Ernst while playing second, while Ernst's entry earned a draw against a third player after 40000 moves in addition to losing to Jonny. Congratulations also to Cortis Clark, for submitting the best placing entry by someone who has not previously won a Challenge.

Of the eight entries, one crashed during play, so I eliminated that one from the tournament. I then ran a tournament with the remaining seven entries, with each playing the other entries twice, once playing first and once playing second. All of the games took between 8 moves and 18 moves to determine a winner, excepting those against contestant Randy Boring, who excelled in staving off defeat. Randy's entry forced ties with three contestants, including Ernst, using a brute-force approach that also took top honors for using the most execution time.

Jonny's code is sparsely commented and tough to read. The first time it is called, his entry calculates a number of tables of winning positions that are then used on all subsequent calls. The code uses a data structure that allocates 4 bits for each piece on the board for each player. It uses the remaining bits of a long word to encode which player is to move next and 3 bits of information about how far the position is from a forced win. There is space in the data structure for a visit count, apparently intended for use by unimplemented logic to prune the search algorithm. Jonny stretched the rules a bit by using some assembly code intrinsics, but performance turned out not be a discriminator, and I decided to let this indiscretion slide.

Since the play against Randy Boring's entry proved to be decisive, it is worthwhile to examine his games against the top two entries. In the board positions below, the positions occupied by one player are labeled "O" and those of the other player "X", with lower case letters used to indicate the position that will disappear next. The draw between Randy (O) and Ernst (X) looped around a sequence of eight positions:

 1:O—  2:O-O  3:OXO  4: oXO  5 oXO  6:-Xo  7:-xo  8: Ox-
   XXO    XXo    xXo     xX-    -x-    -xO    X-O     X-O
   -ox    —x    —-     -O-    -OX    -OX    -OX     -oX

The game between Randy (O) and Jonny (X) took 30 moves, and is provided below. Note that the decisive move was made by "X" in move 28, where he occupied a position that formed a line with his opponent's piece that was about to disappear.

 1:O—  2:O—  3:O-O  4: OXO  5:oXO  6:oXO  7:-Xo  8: -xo
   —-    -X-    -X-     -X-    -X-    -x-    Ox-     O-X
   —-    —-    —-     —-    -O-    XO-    XO-     XO-

 9:Ox- 10:O-X 11:O-X 12: O-X 13:o-X 14:o-x 15:-Ox 16: XO-
   O-X    O-X    o-X     oXx    -Xx    -X-    -X-     -x-
   Xo-    xo-    x-O     —O    O-O    OXO    OXo     OXo

17:XO- 18:XO- 19:XoO 20: xoO 21:x-O 22:—O 23:—o 24: X-o
   Ox-    O-X    O-X     O-X    oOX    oOx    -Ox     -O-
   oX-    ox-    -x-     X—    X—    XX-    XXO     xXO

25:XO- 26:XOX 27:XOX 28: xOX 29:xoX 30:-ox 
   -o-    -o-    O—     O-X    OOX    OOX  
   xXO    -xO    -xo     —o    —-    —X    

The table below lists, for each of the solutions submitted, total execution time, the number of wins and ties achieved, and the total number of points earned (100 for each win, 50 for each tie, minus 1 point for each millisecond of execution time). It also lists the code size, data size, and programming language 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.

Listed here are the Top Contestants for the Programmer's Challenge, including everyone who has accumulated 20 or more points during the past two years. I've changed the format a bit this month. The numbers below include points awarded over the 24 most recent contests, including points earned by this month's entrants, the number of wins over the past 24 months, and the total number of career Challenge points.

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

Here is Jonny's winning Trilite solution: Trilite.cp
Copyright © 2001
Jonny Taylor

#include "Trilite.h"

Ptr            gMemory = 0L;
unsigned short   *gWhiteToMove1, *gWhiteToMove2, *gWhiteToMove3, 
                              *gWhiteToMove4;

#define ASSERT(CONDITION)       //assert(CONDITION)

#define X_MASK      0xCCCCCC
#define Y_MASK      0x333333
#define XY_MASK      X_MASK + Y_MASK

#define BLACKMUSTWIN 0x01

#define WTMFLAGMASK  0xE0
#define WTM5FLAGMASK 0xF0
#define WTM4FLAGMASK 0x00F8
#define WTM3FLAGMASK 0x00FC
#define WTM2FLAGMASK 0x00FE
#define WTM1FLAGMASK 0x00FF

#define BLACK3POS   20
#define BLACK2POS   16
#define BLACK1POS   12
#define WHITE3POS    8
#define WHITE2POS  4
#define WHITE1POS    0

/* These two flags are used to indicate positions where one or both colours have a line WHITEHASLINE 
is also used when both players have a line. If either flag is reached when tracing positions backwards,
that route should be ignored, since you could never  play onwards from a winning position. BLACKHASLINE 
is flagged differently so it can be identified as a move that black should always make (if he can) when
playing a game.  These values will never be encountered in other situations, as long as the Visit count
is limited to a maximum value of 30 */

#define BLACKHASLINE 0xFF
#define WHITEHASLINE 0xFD

/* Black-3 is the most recently-placed one, Black-1 the oldest. When we take back a  move,  we remove 
the most recent (3), 2 becomes 3, 1 becomes 2 and 1 (oldest) us up 
for grabs */

#define BLACK3MASK   0xF00000
#define BLACK2MASK   0x0F0000
#define BLACK1MASK   0x00F000
#define BLACKMASK   0xFFF000
#define WHITE3MASK   0x000F00
#define WHITE2MASK   0x0000F0
#define WHITE1MASK   0x00000F
#define WHITEMASK   0x000FFF

#define SwapColours(POS)      (((POS)>>12) + (((POS)<<12)and0xFFF000))
#define UndoBlacksMove(POS)   (((POS) and WHITEMASK) +    \
                                                   (((POS)<<4)and(BLACK3MASK+BLACK2MASK)))
#define WrappingUndoWhitesMove(POS)            \
      (((POS) and BLACKMASK) | (((POS)<<4)and(WHITE3MASK+WHITE2MASK)) \
                  | (((POS)>>8)andWHITE1MASK))

#define AdvanceWhiteToMove(POS)             \
      (((POS) and BLACKMASK) + (((POS)>>4)and(WHITE1MASK + WHITE2MASK)))
#define AdvanceBlackToMove(POS)             \
      (((POS) and WHITEMASK) + (((POS)>>4)and(BLACK1MASK + BLACK2MASK)))

#define SetWhiteToMoveFlag(FLAG) whiteToMoveData|=(0x80>>(FLAG))
#define SetWhiteToMoveFlag16(FLAG)             \
      whiteToMoveData16 |= (0x80>>(FLAG))

#define SetWhiteToMoveMinDistance(VAL) ASSERT((VAL)<8); \
                     whiteToMoveData and= 0xF1;             \
                              whiteToMoveData |= ((VAL)<<1)

#define SetWhiteToMoveMinDistance16(VAL) ASSERT((VAL)<8); \
                                 whiteToMoveData16 and= 0xFF;            \
                                 whiteToMoveData16 |= ((VAL)<<8)

#define GetWhiteToMoveMinDistance               \
            ((whiteToMoveData and 0x0E)>>1)
#define GetWhiteToMoveMinDistance16               \
            (whiteToMoveData16 >> 8)

#define SetWhiteToMoveMaxDistance(VAL) ASSERT((VAL)<16); ,\
                              whiteToMoveData and= 0x0F;   \
                              whiteToMoveData |= ((VAL)<<4)
                              
#define GetWhiteToMoveMaxDistance               \
            ((whiteToMoveData and 0xF0)>>4)

#define SetWhiteToMoveVisitCount(VAL) ASSERT((VAL)<16);   \
                              whiteToMoveData and= 0x0F;            \
            if ((VAL)>=16);whiteToMoveData |= ((15)<<4);   \
                              else                        whiteToMoveData |= ((VAL)<<4)

#define GetWhiteToMoveVisitCount            \
         ((whiteToMoveData and 0xF0)>>4)

static inline unsigned long Minimize(unsigned long gamePos);
static unsigned long InitWhiteLosses(unsigned char *whiteToMove, 
      unsigned long *list1);
static inline unsigned long MakeFreeSpaceMask(
         unsigned long gamePos);
static inline unsigned long MakeFreeSpaceMask5(
         unsigned long gamePos);
static inline unsigned long MakeFreeSpaceMask4(
         unsigned long gamePos);
static inline unsigned long MakeFreeSpaceMask3(
         unsigned long gamePos);
static inline unsigned long MakeFreeSpaceMask2(
         unsigned long gamePos);
static inline unsigned long MakeFreeSpaceMask1(
         unsigned long gamePos);
static inline unsigned long GetMoveFromMask(unsigned long andmask);
static inline unsigned long EncodePos(unsigned long pos);
static inline unsigned long Encode5Pos(unsigned long pos);

//x3: 0,1 or 2(=5)      (2 bits)   13-14      }   could be combined into 4 bits if necessary
//x2: max 8            (3 bits)   10-12      }   
//x1: max 7            (3 bits)   7-9
//y3}   max 6*5 = 30   (5 bits)   2-6
//y2}
//y1: max 4            (2 bits)   0-1
//highest value is 0b101 1111 1111 1111

#define GetWTM(pos)         whiteToMove[EncodePos(pos)]
#define SetWTM(pos,val)      whiteToMove[EncodePos(pos)] = (val)
#define GetWTM5(pos)      whiteToMove5[Encode5Pos((pos)<<4)>>2]
#define SetWTM5(pos,val)   \
         whiteToMove5[Encode5Pos((pos)<<4)>>2] = (val)

MakePosition
static unsigned long MakePosition(long x[6],long y[6])
{
   long ii;
   unsigned long position = 0;
   
   for (ii = 0; ii < 6; ii++)
   {
      position+=((x[ii]<<2)<<(4*ii));
   }
   for (ii = 0; ii < 6; ii++)
   {
      position+=((y[ii])<<(4*ii));
   }
   return(position);
}

EncodePos
static inline unsigned long EncodePos(unsigned long pos)
{
   unsigned long temp,temp2,y3Val,y2Val;
   unsigned long black3,black2,black1,white3,white2,white1;
   unsigned long result = (posand0xF00000) >> (20 - 13);
   if (pos and 0x400000)            //x3 position is 5
      result -= (3 << 13);      //convert 0x5... to 0x2...
   ASSERT(result <= 0x4000);
   ASSERT((result and 0x6000) == result);
   
   black3 = (posandBLACK3MASK)>>BLACK3POS;
   black2 = (posandBLACK2MASK)>>BLACK2POS;
   //encode x2 - if x2 > x3 then decrease value by 1
   temp = black3 - black2;
   temp2 = (pos and BLACK2MASK) - ((temp and 0x80000000)>>15);
   temp2 -= (pos and 0xC0000)>>2;      //as pos 3 and 7 are invalid

   ASSERT((temp2 >> (16 - 10)) <= 0x1C00);
   ASSERT(((temp2 >> (16 - 10)) and 0x1C00) == 
                              (temp2 >> (16 - 10)));
   result |= (temp2 >> (16 - 10));
   
   //encode x1 - if x1 > x3 decrease value by 1, same for > x2.
   black1 = (pos and BLACK1MASK)>>BLACK1POS;
   temp = black3 - black1;
   temp2 = (pos and BLACK1MASK) - ((temp and 0x80000000)>>19);
   temp = black2 - black1;
   temp2 -= ((temp and 0x80000000)>>19);
   temp2 -= (pos and 0xC000)>>2;      //as pos 3 and 7 are invalid

   ASSERT((temp2 >> (12 - 7)) <= 0x380);
   ASSERT(((temp2 >> (12 - 7)) and 0x380) == (temp2 >> (12 - 7)));
   result |= (temp2 >> (12 - 7));
   
   //encode y3 - if y3 > x3 decrease value by 1, same for > x2 and > x1.
   white3 = (pos and WHITE3MASK)>>WHITE3POS;
   temp = black3 - white3;
   y3Val = (pos and WHITE3MASK) - ((temp and 0x80000000)>>23);
   temp = black2 - white3;
   y3Val -= ((temp and 0x80000000)>>23);
   temp = black1 - white3;
   y3Val -= ((temp and 0x80000000)>>23);
   y3Val -= (pos and 0xC00)>>2;      //as pos 3 and 7 are invalid

   //encode y2 - if y3 > x3 decrease value by 1, same for > x2, >x1 and > y3.
   white2 = (pos and WHITE2MASK)>>WHITE2POS;
   temp = black3 - white2;
   y2Val = (pos and WHITE2MASK) - ((temp and 0x80000000)>>27);
   temp = black2 - white2;
   y2Val -= ((temp and 0x80000000)>>27);
   temp = black1 - white2;
   y2Val -= ((temp and 0x80000000)>>27);
   temp = white3 - white2;
   y2Val -= ((temp and 0x80000000)>>27);
   y2Val -= (pos and 0xC0)>>2;      //as pos 3 and 7 are invalid
   y2Val = y2Val << 4;      //to bring into line with y3

   temp = (y3Val * 5 + y2Val) >> (8 - 2);
   ASSERT(temp <= 0x7C);
   ASSERT((temp and 0x7C) == temp);
   result |= temp;
   
   //encode y1 - if y3 > x3 decrease value by 1, same for > x2, >x1 and > y3.
   white1 = (pos and WHITE1MASK)>>WHITE1POS;
   temp = black3 - white1;
   temp2 = (pos and WHITE1MASK) - ((temp and 0x80000000)>>31);
   temp = black2 - white1;
   temp2 -= ((temp and 0x80000000)>>31);
   temp = black1 - white1;
   temp2 -= ((temp and 0x80000000)>>31);
   temp = white3 - white1;
   temp2 -= ((temp and 0x80000000)>>31);
   temp = white2 - white1;
   temp2 -= ((temp and 0x80000000)>>31);
   temp2 -= (pos and 0xC)>>2;      //as pos 3 and 7 are invalid
   
   ASSERT(temp2 <= 0x3);
   result |= temp2;

   ASSERT(result < 0x4700);   
                           //highest position involves b3 in centre and b2 on an edge, so
                           //value is 0b10 001 101 xxxxx xx or 0x46FF
   return(result);
}

/*
 * See online code listing for Encode5Pos
 */

Minimize
/*******************************************************************
Minimize()
The aim of this function is to find a new value for gamePos that is totally equivalent
(a reflection or rotation of the current one), but which has a smaller value.

We first calculate whether we can minimize it by reflecting the board across its horizontal and/or 
vertical lines of symmetry (x=1 and y=1). We then try reflecting it on a diagonal (x=y). With the 8 
possible combinations of these reflections, we can switch froms every symmetry of the board to every 
other. 

The function uses a rather confusing algorithm in order to minimize conditional branches to improve 
on pipelining.
********************************************************************/

static unsigned long Minimize(unsigned long gamePos)
{
   unsigned long xBitfield, yBitfield;
   unsigned long xCountFromLeft, yCountFromTop;
   unsigned long swapped;
   
   /* By XOR-ing every x bit-pair with 0b01, we have a 1 in an even bit-position
   (counting from MSB, first is zero) if x should be counted from the right, and
   a 1 in an odd bit-position and a 0 in an even bit-position if x should be counted
   from the right. If neither are 1, it does not matter for this x coordinate which
   side we start counting from. */
   xBitfield = gamePos and X_MASK;
   xBitfield ^= 0x444444;         //one in every x field
   /* Now we count the leading zeros on the resultant bit-field.
   If there is an odd number of leading zeros, we should count from the left.
   If there is an even number, we should count from the right. */
   xCountFromLeft = __cntlzw(xBitfield) and 0x01;
   
   /* Do a similar thing for y */
   yBitfield = gamePos and Y_MASK;
   yBitfield ^= 0x111111;         //one in every y field
   yCountFromTop = __cntlzw(yBitfield) and 0x01;
   
   /* If the x fields are to be counted from the right, or the y fields from the
   bottom, we need to subtract the initial value from 2. Two's complement arithmetic
   for each 2-bit field that is to be swapped gives 2+(!value)+1 or 0b11+(0b11^value).
   This always gives a carry-over bit, so to cancel out the overflow we subtract
   0b100 so: 0b11+(0b11^value)-0b100. */
   if (xCountFromLeft == 0 andand yCountFromTop == 0)
   {
      /* need to subtract every field from 2 */
      gamePos = XY_MASK + (XY_MASK ^ gamePos) - 0x1555554;
   }
   else if (xCountFromLeft == 0)
   {
      gamePos = X_MASK + (X_MASK ^ gamePos) - 0x1111110;
   }
   else if (yCountFromTop == 0)
   {
      gamePos = Y_MASK + (Y_MASK ^ gamePos) - 0x444444;
   }
   
   /* It may be that we can make the gamePos value smaller by swapping the x and y
   coordinates. This is equivalent to reflecting the board in the line y=x. The
   quickest way of knowing if we should do this is jsut to try it and see */
   swapped = ((gamePos << 2) and 0xCCCCCC) + 
                        ((gamePos >> 2) and 0x333333);
   if (swapped <= gamePos)
   {
      gamePos = swapped;
   }
   return (gamePos);
}

InitWhiteLosses
static unsigned long InitWhiteLosses(unsigned char *whiteToMove, unsigned long *list1)
{
   /* first is most significant */
   long winningLineX[9][3]={   {0,1,2}, {0,2,1}, {1,0,2},
                        {0,0,0}, {0,0,0}, {0,0,0},
                        {0,1,2}, {0,2,1}, {1,0,2} };
   long winningLineY[9][3]={   {0,1,2}, {0,2,1}, {1,0,2},
                        {0,1,2}, {0,2,1}, {1,0,2},
                        {1,1,1}, {1,1,1}, {1,1,1} };
   long full[3][3];
   long skip;
   long i,ii,jj,xIncr,yIncr;
   long list1Pos = 0;
   unsigned long pos1,pos2,pos3;
   long whiteHasLine;
   unsigned long pos,minimizedPos;

   for (i=0;i<0x4700;i+=32)      //0x01 and 0x02 are valid
      __dcbz(whiteToMove,i);
   
DoneInit:
   for (i=0;i<9;i++)
   {      
      long x[6]={0,0,0,0,0,0};
      long y[6]={0,0,0,0,0,0};
      x[0]=0;x[1]=0;x[2]=0;x[3]=0;x[4]=0;x[5]=0;
      y[0]=0;y[1]=0;y[2]=0;y[3]=0;y[4]=0;y[5]=0;

      x[5]=winningLineX[i][0];
      x[4]=winningLineX[i][1];
      x[3]=winningLineX[i][2];
      y[5]=winningLineY[i][0];
      y[4]=winningLineY[i][1];
      y[3]=winningLineY[i][2];
      
      while(1)
      {
         while(1)
         {
            for(ii=0;ii<3;ii++)
               for(jj=0;jj<3;jj++)
                  full[ii][jj]=0;
            for (ii = 0; ii < 6; ii++)
            {
               full[x[ii]][y[ii]]++;
            }
            skip = false;
            for(ii=0;ii<3;ii++)
               for(jj=0;jj<3;jj++)
                  if (full[ii][jj]>1)
                     skip = true;
            
            if(!skip)
            {
               pos=MakePosition(x,y);
               minimizedPos=Minimize(pos);
               
               if (minimizedPos == pos)
               {
                  pos1 = ((pos and WHITE1MASK)>>WHITE1POS);
                  pos2 = ((pos and WHITE2MASK)>>WHITE2POS);
                  pos3 = ((pos and WHITE3MASK)>>WHITE3POS);
                  whiteHasLine = false;
                  if ((pos1 and 0x3) == (pos2 and 0x03) andand
                     (pos1 and 0x3) == (pos3 and 0x03))
                     whiteHasLine = true;
                  if ((pos1 and 0xC) == (pos2 and 0x0C) andand
                     (pos1 and 0xC) == (pos3 and 0x0C))
                     whiteHasLine = true;
                  if ((pos1 and 0x3) == ((pos1 and 0x0C)>>2) andand
                     (pos2 and 0x3) == ((pos2 and 0x0C)>>2) andand
                     (pos3 and 0x3) == ((pos3 and 0x0C)>>2))
                     whiteHasLine = true;
                     
                  if (whiteHasLine)
                  {
               ASSERT(GetWTM(pos)==0 || GetWTM(pos)==WHITEHASLINE);
                     SetWTM(pos,WHITEHASLINE);
//                     whiteToMove[pos] = WHITEHASLINE;
                  }
                  else
                  {
            ASSERT(GetWTM(pos)==0 || GetWTM(pos)==BLACKHASLINE);
                     pos1 = Minimize(SwapColours(pos));
            ASSERT(GetWTM(pos1)==0 || GetWTM(pos1)==WHITEHASLINE);
                     SetWTM(pos1,WHITEHASLINE);
//                     whiteToMove[pos1] = WHITEHASLINE;
                     
                     list1[list1Pos++] = pos;
                     SetWTM(pos,BLACKHASLINE);
//                     whiteToMove[pos] = BLACKHASLINE;
                  }
               }            
            }
            
            xIncr = 0;
            while(++(x[xIncr]) == 3)
            {
               x[xIncr]=0;
               xIncr++;
               if(xIncr == 3)
                  break;
            }
            if (xIncr == 3) break;
         }
         yIncr = 0;
         while(++(y[yIncr]) == 3)
         {
            y[yIncr]=0;
            yIncr++;
            if(yIncr == 3)
               break;
         }
         if (yIncr == 3) break;
      }
   }
   return(list1Pos);
}

/*
 * See online code listing for InitWhiteLosses5
 */


MakeFreeSpaceMask
static inline unsigned long MakeFreeSpaceMask(unsigned long gamePos)
{
   unsigned long mask = 0xEEE00000;
   
   mask ^= ((unsigned long)1<<31)>>
                        ((gamePosandBLACK3MASK)>>BLACK3POS);
   mask ^= ((unsigned long)1<<31)>> 
                         ((gamePosandBLACK2MASK)>>BLACK2POS);
   mask ^= ((unsigned long)1<<31)>> 
                         ((gamePosandBLACK1MASK)>>BLACK1POS);
   mask ^= ((unsigned long)1<<31)>> 
                         ((gamePosandWHITE3MASK)>>WHITE3POS);
   mask ^= ((unsigned long)1<<31)>> 
                         ((gamePosandWHITE2MASK)>>WHITE2POS);
   mask ^= ((unsigned long)1<<31)>> 
                         ((gamePosandWHITE1MASK)>>WHITE1POS);
   
   return(mask);
}

/*
 * See online code listing for MakeFreeSpaceMaskX, X==1..5
 */

GetMoveFromMask
static inline unsigned long GetMoveFromMask(unsigned long andmask)
{
   unsigned long freePos = __cntlzw(mask);
   (mask) ^= ((unsigned long)(1<<31)>>freePos);
   return(freePos);
}

GenerateWhiteToMoveData
static unsigned long GenerateWhiteToMoveData(unsigned char *whiteToMove, unsigned long *fullList, 
unsigned long fullListLen)
{
   unsigned long distanceFromWin = 0;
   unsigned long fullListPos = 0;
   unsigned long depthMax = fullListLen;
      //depthMax is the first list member belonging to the current depth

   while(fullListPos < depthMax)
   {
      unsigned long ii;
      unsigned long gamePos = fullList[fullListPos++];
      unsigned long mask1 = MakeFreeSpaceMask(gamePos);
         //mask1 is a mask of the free spaces that black could have just moved from
      
      //remove black's most recent move
      gamePos = (gamePos and WHITEMASK) | 
                        ((gamePos << 4) and (BLACK3MASK | BLACK2MASK));

      //do for the 3 places the most recent black move could have come from
      for (ii=0;ii<3;ii++)
      {
         unsigned long whiteToMoveData, mask2, oldWhitePos, jj, 
                     partEncodedLastRoundPos;
         
         //get a position from the mask
         unsigned long blackPiece1 = GetMoveFromMask(mask1);
         //get position as it was before black moved
         unsigned long prevGamePos = gamePos | 
                        (blackPiece1 << BLACK1POS);
         
         //get the data for black on the position with black about to move
         //to do this, swap the colours, minimize, and read from the whiteToMove data
         unsigned long tempGamePos = ((prevGamePos>>12) + 
                        ((prevGamePos<<12)and0xFFF000));
         
         tempGamePos = Minimize(tempGamePos);
   whiteToMoveData = GetWTM(tempGamePos);//whiteToMove[tempGamePos];
         if ((whiteToMoveData and BLACKMUSTWIN) andand
            (GetWhiteToMoveMinDistance < distanceFromWin))
         {
            /* Look if the position is one white can force a win from before black has
            a chance of forcing a win. If it is, give up on that position */
            continue;
         }
         
         /* convert a position of the form 321CBA to 321BAC. This lets us minimize 
            the position as it will be when we take back white's last move, and still know 
            where   that move we are taking back was from - even though the position 
            code may have been changed by minimization */
         prevGamePos = (prevGamePos and BLACKMASK) | 
                        ((prevGamePos<<4) and (WHITE3MASK+WHITE2MASK))
                                 | ((prevGamePos>>8) and WHITE1MASK);
         prevGamePos = Minimize(prevGamePos);
         mask2 = MakeFreeSpaceMask(prevGamePos);
         oldWhitePos = (prevGamePos and 0xF);
         prevGamePos and= (~WHITE1MASK);

         /*encode as much of prevGamePos as we can at this stage. We will encode the 
            last 2 bits (white1), and only that, in the inner loop */         
   partEncodedLastRoundPos = (EncodePos(prevGamePos) and 0xFFFC);

         //undo whites last move to each of the 3 places it could have come from
         for (jj=0;jj<3;jj++)
         {
            unsigned long mask3, possibleMove, encLastRoundPos;
            unsigned long whitePiece = GetMoveFromMask(mask2);
            unsigned long lastRoundPos = prevGamePos | 
                              (whitePiece << WHITE1POS);
            
            //whiteToMoveData = 
            //      GetWTM(lastRoundPos);//whiteToMove[lastRoundPos];
            {
               unsigned long temp = ((lastRoundPos and 0xF00000)>>20) - 
                                                            whitePiece;
               unsigned long temp2 = whitePiece - 
                                                ((temp and 0x80000000)>>31);
            temp = ((lastRoundPos and 0xF0000)>>16) - whitePiece;
            temp2 -= ((temp and 0x80000000)>>31);
            temp = ((lastRoundPos and 0xF000)>>12) - whitePiece;
            temp2 -= ((temp and 0x80000000)>>31);
            temp = ((lastRoundPos and 0xF00)>>8) - whitePiece;
            temp2 -= ((temp and 0x80000000)>>31);
            temp = ((lastRoundPos and 0xF0)>>4) - whitePiece;
            temp2 -= ((temp and 0x80000000)>>31);
            temp2 -= (lastRoundPos and 0xC)>>2;   //as pos 3 and 7 are invalid
               
               ASSERT(temp2 <= 0x3);
               encLastRoundPos = partEncodedLastRoundPos | temp2;
            }
            //encLastRoundPos = EncodePos(lastRoundPos);
            whiteToMoveData = whiteToMove[encLastRoundPos];

            if (whiteToMoveData == BLACKHASLINE ||
               whiteToMoveData == WHITEHASLINE)
               continue;
                     /*don't bother to track back to positions where a
                              player has a line (someone has already won) */
            if (whiteToMoveData and WTMFLAGMASK == 0)
            {
               //record the minimum number of rounds until black makes a line
               SetWhiteToMoveMinDistance(distanceFromWin);
            }
            if (whiteToMoveData and BLACKMUSTWIN)
            {
            //don't do anything more for this position if we already know it is a winner
               continue;
            }
            
            /* Get the new free-space mask and work out which one is the one we juse 
               took back white's move from (oldWhitePos) */
            mask3 = MakeFreeSpaceMask(lastRoundPos);
            possibleMove = GetMoveFromMask(mask3);
            if (possibleMove == oldWhitePos)
               SetWhiteToMoveFlag(0);
            possibleMove = GetMoveFromMask(mask3);
            if (possibleMove == oldWhitePos)
               SetWhiteToMoveFlag(1);
            possibleMove = GetMoveFromMask(mask3);
            if (possibleMove == oldWhitePos)
               SetWhiteToMoveFlag(2);
            
            if (whiteToMoveData >= WTMFLAGMASK)
            {
               fullList[fullListLen++]=lastRoundPos;
               whiteToMoveData++;
               SetWhiteToMoveMaxDistance(distanceFromWin);
            }
//            whiteToMove[lastRoundPos] = whiteToMoveData;
            //SetWTM(lastRoundPos,whiteToMoveData);
            ASSERT((whiteToMoveData and 0xFF00) == 0);
            whiteToMove[encLastRoundPos] = whiteToMoveData;

         }
      }
      if (fullListPos < depthMax)
         continue;

      depthMax = fullListLen;
      
      /* Increase distanceFromWin. We must limit it to 7 to fit in a space of
      3 bits for min-distance. It would not be the end of the world if there
      was a cap on this value; and as it happens there are no definite winning
      setups with a minimum distance of >7. */
      if (distanceFromWin < 7)
         distanceFromWin++;
   }
   
   return(fullListLen);
}

/*
 * See online code listing for GenerateWhiteToMoveXData, X==1..5
 */

BestMove6Pieces
//static unsigned long GetBestMove(unsigned long gamePos, 
//   unsigned char *whiteToMove)
static unsigned long BestMove6Pieces(
      unsigned long gamePos, unsigned char *whiteToMove)
{
   unsigned long blackPiece3,whitePiece3;
   unsigned long nextGamePos,gp2,colourSwappedPosition;
   unsigned long whiteToMoveData,minDistance;
   unsigned long mask1,mask2;
   long score,bestScore;
   long bestMove;
   long ii,jj;
   
   bestScore = -10000;
   mask1 = MakeFreeSpaceMask(gamePos);
   gamePos = AdvanceBlackToMove(gamePos);      
   for (ii = 0; ii < 3; ii++)
   {
      score = 0;
      blackPiece3 = GetMoveFromMask(mask1);
      nextGamePos = (gamePos and (~BLACK3MASK)) | 
                                    (blackPiece3 << BLACK3POS);
      
      whiteToMoveData = GetWTM(Minimize(nextGamePos));
      if (whiteToMoveData == BLACKHASLINE)
         //can win instantly by making a line
      {
         //printf("%ld wins outright!\n",blackPiece3);
         return (blackPiece3);
      }
      minDistance = GetWhiteToMoveMinDistance;
      
      if (whiteToMoveData and 0x1)         
               //can win in the future starting with this move
      {
         /* Highest score goes to smallest distance we are sure to win in (max-distance)
          */
         //printf("%ld wins in %ld-%ld 
         //rounds\n",blackPiece3,GetWhiteToMoveMinDistance,
         //            GetWhiteToMoveMaxDistance);
         score = 10000-GetWhiteToMoveMaxDistance;
      }
      else                           //look at possibilities for white's next move
      {
         mask2 = MakeFreeSpaceMask(nextGamePos);
         nextGamePos = AdvanceWhiteToMove(nextGamePos);
         for (jj = 0; jj < 3; jj++)
         {
            whitePiece3 = GetMoveFromMask(mask2);
            gp2 = (nextGamePos and (~WHITE3MASK)) | 
                           (whitePiece3 << WHITE3POS);
            /* gp2 is now one of 3 possible black-to-move positions arising from
            the current immediate black moves. */
            colourSwappedPosition = SwapColours(gp2);
      whiteToMoveData = GetWTM(Minimize(colourSwappedPosition));
            if (whiteToMoveData and 1)
            {
               /* The worst situation is that one of the positions is a black-loses
               position with a small min-distance (i.e. one that the opponent is
               very likely to see). */
               if (whiteToMoveData == BLACKHASLINE)
                  score = -101;
               else if (score != -101)
                  score = -100 + GetWhiteToMoveMinDistance;
            }
         }
         if (score == 0)
         {
            /* **** add support for not visiting the same location over and over ****/
            /* if we have not yet scored for anything, the best bet is a black move for 
               which some of the subsequent moves white could make are fatal, with a 
               large min-distance.
               This represents moves that white could easily not notice are fatal, and play 
               by mistake */
            score = minDistance;
         }
      }
      if (score > bestScore)
      {
         bestMove = blackPiece3;
         bestScore = score;
      }
   }
   return(bestMove);
}

/*
 * See online code listing for BestMoveXPieces, X==0..5
 */

unsigned long gCurrentGamePosition, gCurrentRound;


PlayTrilite
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 calledfor a new game */
)
{
   unsigned long *list1, *list2, *list3, *list4, *list5, 
                                 *fullList;
   unsigned long list1Len,list2Len,fullListLen;
   unsigned long list3Len,list4Len,list5Len;
   unsigned long ii;

   unsigned char *whiteToMove,*whiteToMove5;
   unsigned short *whiteToMove4, *whiteToMove3, *whiteToMove2, 
                                    *whiteToMove1;
   BoardPosition resultBoardPosition;
   unsigned long bestMove, myOpponentPreviousPlay;
   
   if (gMemory == 0L)            //see if data needs to be generated
   {
      whiteToMove4 = (unsigned short*)NewPtr(0x51B0 * 2);
      whiteToMove3 = (unsigned short*)NewPtr(1310*2);
      whiteToMove2 = (unsigned short*)NewPtr(90*2);
      whiteToMove1 = (unsigned short*)NewPtr(8*2);
      gWhiteToMove4 = whiteToMove4;
      gWhiteToMove3 = whiteToMove3;
      gWhiteToMove2 = whiteToMove2;
      gWhiteToMove1 = whiteToMove1;
      gMemory = NewPtr(70000);
   
      if (gMemory == 0L)            //out of memory (shouldn't happen!)
      {
         DebugStr("\pOut of memory!");
         resultBoardPosition=kNoPosition;
         return(resultBoardPosition);
      }
      //init temporary storage (lists of winning positions)
      list3 = (unsigned long*)NewPtr(4*100);
      list2 = (unsigned long*)NewPtr(4*100);
      list4 = (unsigned long*)NewPtr(4*100);
      list5 = (unsigned long*)NewPtr(4*100);
   whiteToMove = (unsigned char*)(((long)gMemory and 0xFFFFFFE0) + 
                                          32);      //block size 0x4700
   whiteToMove5 = (unsigned char*)((char*)whiteToMove + 0x4700);
            //block size 0x11C0
      fullList = (unsigned long*)((char*)whiteToMove5 + 0x11C0); 
            //block size 0x2000
      list1 = (unsigned long*)((char*)fullList + 0x2000);   
            //block size 0x0800
   /* full has 2026/~7200 winners
      5-piece calcs read from full to list1 (419/1800 winners)
      3-piece calcs read from list1 to list2 (16/60 winners)
      1-piece calcs read from list2 to list5
      4-piece calcs read from full to list3 (58/360 winners)
      2-piece calcs read from list3 to list4   */
            //clear arrays
      for (ii=0;ii<(0x51B0/2);ii++)
         ((unsigned long*)whiteToMove4)[ii] = 0;
      for (ii=0;ii<(1310/2);ii++)
         ((unsigned long*)whiteToMove3)[ii] = 0;
      for (ii=0;ii<(90/2);ii++)
         ((unsigned long*)whiteToMove2)[ii] = 0;
      for (ii=0;ii<(8/2);ii++)
         ((unsigned long*)whiteToMove1)[ii] = 0;
      
   fullListLen = InitWhiteLosses(whiteToMove, fullList);
   fullListLen = GenerateWhiteToMoveData(whiteToMove, fullList, 
                                             fullListLen);
list1Len = InitWhiteLosses5(whiteToMove5, list1);
list1Len = GenerateWhiteToMove5Data(whiteToMove, whiteToMove5,
                                 fullList, fullListLen,
                                 list1, list1Len);
list3Len = GenerateWhiteToMove4Data(whiteToMove, whiteToMove4,
                                 fullList, fullListLen, list3);
      list2Len = GenerateWhiteToMove3Data(whiteToMove5, 
                                 whiteToMove3,
                                 list1, list1Len, list2);
      list4Len = GenerateWhiteToMove2Data(whiteToMove4, 
                              whiteToMove2,
                              list3, list3Len, list4);
      list5Len = GenerateWhiteToMove1Data(whiteToMove3, 
                              whiteToMove1,
                              list2, list2Len, list5);
   }
   else
   {
      //init local variables from globals
      whiteToMove4 = gWhiteToMove4;
      whiteToMove3 = gWhiteToMove3;
      whiteToMove2 = gWhiteToMove2;
      whiteToMove1 = gWhiteToMove1;

   whiteToMove = (unsigned char*)(((long)gMemory and 0xFFFFFFE0) + 
                  32);      //block size 0x4700
   whiteToMove5 = (unsigned char*)((char*)whiteToMove + 0x4700);
                        //block size 0x11C0
      fullList = (unsigned long*)((char*)whiteToMove5 + 0x11C0); 
                        //block size 0x2000
      list1 = (unsigned long*)((char*)fullList + 0x2000);
                        //block size 0x0800
   }

   //opponentPreviousPlay must be converted to the internal representation, where 0, 4 
   // and 8 are the values of the pieces in the left-hand column of the board
   if(opponentPreviousPlay >= kBottomLeft)
myOpponentPreviousPlay = (unsigned long)opponentPreviousPlay + 
                                                               2;
   else if(opponentPreviousPlay >= kCenterLeft)
myOpponentPreviousPlay = (unsigned long)opponentPreviousPlay + 
                                                               1;
   else
   myOpponentPreviousPlay = (unsigned long)opponentPreviousPlay;

   if (newGame)
   {
      if (playerNumber == 1)
      {
         gCurrentRound = 1;
      }
      else if (playerNumber == 2)
      {
         gCurrentRound = 2;
      }
   }
   else
   {
      gCurrentRound += 2;
   }
   
   switch(gCurrentRound)
   {
      case 1:
         gCurrentGamePosition = 0;
         bestMove = BestMove0Pieces(whiteToMove2, whiteToMove1);
         gCurrentGamePosition = bestMove;
         break;

      case 2:
         gCurrentGamePosition = myOpponentPreviousPlay;
         bestMove = BestMove1Piece(gCurrentGamePosition, 
                                    whiteToMove3, whiteToMove2);
         gCurrentGamePosition = (gCurrentGamePosition << 4) | 
                                                      bestMove;   //1 to 1A
         break;

      case 3:
         gCurrentGamePosition = (gCurrentGamePosition << 4) | 
                                                   myOpponentPreviousPlay;
         bestMove = BestMove2Pieces(gCurrentGamePosition, 
                                             whiteToMove4, whiteToMove3);
         gCurrentGamePosition = gCurrentGamePosition | 
                                          (bestMove << 8);   //1A to 21A
         break;

      case 4:
         gCurrentGamePosition = gCurrentGamePosition | 
                                          (myOpponentPreviousPlay << 8);
         bestMove = BestMove3Pieces(gCurrentGamePosition, 
                                             whiteToMove5, whiteToMove4);
         gCurrentGamePosition = ((gCurrentGamePosition << 4) and 
                                                      0xFF00) |
                           (gCurrentGamePosition and 0xF) |
                           (bestMove << 4);      //21A to 21BA
         break;

      case 5:
         gCurrentGamePosition = 
                           ((gCurrentGamePosition << 4) and 0xFF00) |
                           (gCurrentGamePosition and 0xF) |
                           (myOpponentPreviousPlay << 4);
         bestMove = BestMove4Pieces(gCurrentGamePosition, 
                                                whiteToMove, whiteToMove5);
         gCurrentGamePosition = gCurrentGamePosition | 
                              (bestMove << 16);      //21BA to 321BA
         break;

      case 6:
         gCurrentGamePosition = gCurrentGamePosition | 
                              (myOpponentPreviousPlay << 16);
         bestMove = BestMove5Pieces(gCurrentGamePosition, 
                                       whiteToMove);
         gCurrentGamePosition = ((gCurrentGamePosition << 4) and 
                              0xFFF000) |
                           (gCurrentGamePosition and 0xFF) |
                           (bestMove << 8)      //321BA to 321CBA
         break;

      case 7:
         gCurrentGamePosition = 
                        ((gCurrentGamePosition << 4) and 0xFFF000) |
                  (gCurrentGamePosition and 0xFF) |
                           (myOpponentPreviousPlay << 8);
         bestMove = BestMove6Pieces(gCurrentGamePosition, 
                                                whiteToMove);
         gCurrentGamePosition = 
                              AdvanceBlackToMove(gCurrentGamePosition);
         gCurrentGamePosition |= (bestMove << BLACK3POS);
         break;

      default:      // gCurrentRound > 6
         if (playerNumber == 1)
         {
            gCurrentGamePosition = 
                              AdvanceWhiteToMove(gCurrentGamePosition);
            gCurrentGamePosition |= (myOpponentPreviousPlay << 
                                                            WHITE3POS);
            bestMove = BestMove6Pieces(gCurrentGamePosition, 
                                                   whiteToMove);
            gCurrentGamePosition =
                            AdvanceBlackToMove(gCurrentGamePosition);
            gCurrentGamePosition |= (bestMove << BLACK3POS);
         }
         else
         {
            gCurrentGamePosition = 
                           AdvanceBlackToMove(gCurrentGamePosition);
            gCurrentGamePosition |= (myOpponentPreviousPlay << 
                                                            BLACK3POS);
            bestMove = 
                  BestMove6Pieces(SwapColours(gCurrentGamePosition), 
                     whiteToMove);
            gCurrentGamePosition = 
                              AdvanceWhiteToMove(gCurrentGamePosition);
            gCurrentGamePosition |= (bestMove << WHITE3POS);
         }
         break;

   }
   //convert bestMove to external representation
   resultBoardPosition = 
               (BoardPosition)(bestMove - (bestMove / 4));
   return(resultBoardPosition);
}