TweetFollow Us on Twitter

Feb 02 Challenge

Volume Number: 18 (2002)
Issue Number: 02
Column Tag: Programmer's Challenge

by Bob Boonstra, Westford, MA

S*xChart

I don't know which is more puzzling, the fact that people write these things, or the fact that I read them. Or perhaps it was just a slow news week, even for Wired. But when your daily headline email is headlined "Sexchart", you've just got to follow the link to see what's on the other side. And I'm always on the lookout for a novel Challenge idea - you never know where they might appear.

You can check out the link
(http://www.wired.com/news/culture/0,1284,48997,00.html) yourself, but the gist of it is this. Someone got the idea of showing just how, well, "connected" one of the more promiscuous members of the internet world was by representing individuals as dots on a two-dimensional graph, and connecting them with a line whenever they had, er, "hooked up". Over time, the graph grew to more than 1400 individuals and their assignations. The definition of what is required to connect two people with a line is provided in the referenced article, something about what sorts of disease can be spread by the contact, but that's not relevant for our purpose.

So what does this have to do with the Challenge? If you look at the SexChart
(http://www.attrition.org/hosted/sexchart/sexchart.9.25), you can see that it has some deficiencies. First, it's done in ASCII, which limits the connecting line segments to a few orientations provided by a small number of characters. Second, the graph has grown up over time and, frankly, it has gotten a little messy. Certainly we can help. Your Challenge this month is to produce a better SexChart.

Entries this month will be complete applications, so there is no prototype for the code you should write. Your program must process a sequence of test cases, the number of which is provided in the file SexChart.in. The input for test case NN begins with a file (namesNN.in) containing the names of everyone in the graph. The first line in the file is the number of names it contains, followed by one name per line.

53
crank
Kissin Tell
Metalchic
Alan Medusa
...
piglet
Wicked Pixie

The rest of the test case input is a file (hookupsNN.in) indicating who is connected with whom. Again, the first line in the file is the number of relationships that follow. The file might look something like this:

40
crank,Alan Medusa
crank,piglet
crank,Handsome Harry
Metalchic,Kissin Tell
Metalchic,Handsome Harry
...
Handsome Harry,Wicked Pixie

Your objective in this Challenge is to place all of the names on a graph and connect them using a multi-segment in a way that minimizes the number of intersections among the connecting lines. If the line connecting names A and B intersects the line connecting C and D, you earn one penalty point for each place that they intersect. Collinear segments (not desirable) earn one point for every unit of overlap length. Your code should produce three output files. The first one (locationsNN.out) contains one line for each name on the graph, with the integer horizontal and vertical coordinates at which the name is placed:

50,100,crank
100,150,Handsome Harry
...
25,150,Wicked Pixie

The second output file (segmentsNN.out) contains a sequence of points connecting each pair of names in hookupsNN.txt. The first and last point in each sequence correspond to the locations of the names being connected. So, for the line connecting crank with Handsome Harry, the segment file might contain this …

3
50,100
75,125
100,150
...followed by this for the connection between Handsome Harry and Wicked Pixie:
2
100,150
25,150

The final output file (logfile.txt) should contain one line for each test case, containing the amount of execution time in milliseconds required to process each test case, measured from before the input is read through the time the output files are generated.

Your solution should display the graph generated for each test case, showing the location where each name has been placed, and the line segments connecting each specified pair of names. You should provide the ability to resize the window in which the graph is drawn, and vertical and horizontal scrolling capability if needed to see the entire graph. You should provide menu control allowing the user to advance to the next test case. You can provide other capabilities as desired to improve the discretionary part of your score (see below).

Scoring will be based on minimizing the number of points your solution incurs. You earn one point for each nontrivial intersection of line segments in each graph that you generate. You incur an additional point for each 100 milliseconds of execution time your solution requires to generate the graph. The time required to display your graph after it has been generated does NOT count and does not incur points. However, the quality of your display along with any additional features provided in your program may earn you a bonus reduction of up to 25% of your points. The bonus will be awarded based on a subjective evaluation of the quality and attractiveness of your application.

This will be a native PowerPC Challenge, using any of the following environments: CodeWarrior, REALbasic (version 3.2.1 or earlier), MetaCard (version 2.3.2 or earlier), Revolution (version 1.1), or Project Builder. You may use another development environment if I can arrange to obtain a copy - email progchallenge@mactech.com to check before you use something else. You can develop for Mac OS 9 or Mac OS X. Your solution should be a complete Macintosh application, and your submission should provide everything needed to build your application, as well as documentation of the features you have implemented, to ensure that I don't overlook anything.

Winner of the November, 2001 Challenge

The November Challenge required contestants to write a player for the ancient game Seega. Seega is played on a 5x5 board (generalized to larger boards for the Challenge), where players capture pieces by moving to positions where an opponent's piece is bracketed by the piece just moved and another of your pieces. Two players entered the November Seega contest. Congratulations to Ernst Munter (Kanata, Ontario) for defeating returning contestant Alan Stenger.

As it turns out, both players played the game very conservatively, and every contest resulted in a stalemate. Both Ernst and Alan observed that stalemates occurred frequently during their testing, and might be an appropriate winning strategy, although neither of them adopted an explicit stalemate strategy in their code. In each of my test cases, the first player to move (the second player to place pieces on the board) was the one who had the most pieces on the board when a stalemate was declared, and therefore was declared the winner of the game. Alan actually won games by a larger cumulative margin, as much as 6 pieces in a 7x7 game, but his code took much longer to execute than Ernst's. But scoring was based on the number of victories, minus one win for each second of cumulative execution time, so Ernst's entry was the winner. Since our second-place finisher has not won a Challenge in the past 24 months, this month's prize will be split evenly between Ernst and Alan.

The table below lists, for each of the solutions submitted, the number of games won, the number of pieces remaining in all games, the total execution time in milliseconds, and the cumulative score. It also lists the code size, data size, and programming language of 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.

Name Wins Pieces Time
(msec)
Ernst Munter (780) 6 156 531.62
Alan Stenger (65) 6 165 197807.9
8
Name Score Code Data Lang
Size Size
Ernst Munter 5.4684 8248 1847 C++
Alan Stenger -191.808 4684 878 C++

Top Contestants...

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. The numbers below include points awarded over the 24 most recent contests, including points earned by this month's entrants.

Rank Name Points Wins Total
(24 mo) (24 mo) Points
1. Munter, Ernst 253 9 800
2. Rieken, Willeke 73 3 134
3. Taylor, Jonathan 59 2 63
4. Wihlborg, Claes 49 2 49
5. Saxton, Tom 35 1 193
7. Maurer, Sebastian 31 1 108
10. Mallett, Jeff 20 1 114
11. Truskier, Peter 20 1 20
12. Cooper, Tony 20 1 20

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

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.

Rank Name Points Total
(24 mo) Points
6. Boring, Randy 32 144
8. Sadetsky, Gregory 22 24
9. Shearer, Rob 21 62
13. Schotsman, Jan 14 14
14. Stenger, Allen 10 75
15. Nepsund, Ronald 10 57
16. Hart, Alan 10 35
17. Day, Mark 10 30
18. Downs, Andrew 10 12
19. Flowers, Sue 10 10
20. Fazekas, Miklos 10 10
21. Desch, Noah 10 10
22. Nicolle, Ludovic 7 55
23. Miller, Mike 7 7
24. Leshner, Will 7 7

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 Seega solution:

Seega.cpp
Copyright © 2001
Ernst Munter, Kanata, ON, Canada

/*
Submission to MacTech Programmer's Challenge for November 2001.

      "Seega"

This file contains the external interface.
"ComputerPlayer.h" provides the implementation of logic.

*/
      
#include "Seega.h"      
#include "ComputerPlayer.h"

static ComputerPlayer* P;
   
void InitGame(
  int boardSize,               
        /* number of rows and columns, odd integer >= 5 */
  char pieceValue,     
       /* value assigned to your pieces, 1..numberOfPlayers */
  Boolean playFirst,   
       /* TRUE if you place pieces first (and move second) */
  int stalemateThreshold
    /* stalemate will be declared after this number of moves without a capture */
)
{
   if (P) delete P;
   P = new ComputerPlayer( boardSize, pieceValue, playFirst, 
                        stalemateThreshold);
}

void PlacePieces(
  const Board board,  
    /* board state before you place pieces */
  Position *placePiece1,       
    /* place a piece at *placePiece1 */
  Position *placePiece2        
    /* place a piece at *placePiece2 */
)
{
   assert(P);
   P->PlacePieces(board,placePiece1,placePiece2);
}

void MovePiece(
  const Board board,     
    /* board state before you move a piece, updated by test code */
  Boolean followUpMove, 
    /* TRUE if you must make another capture with the last piece moved */
  Position *moveFrom,
    /* location you are moving from, (-1,-1) if you cannot move */
  Position *moveTo,
    /* location you are moving to, (-1,-1) if you cannot move */
  Boolean *blocked
    /* return TRUE if you cannot move */
)
{
   assert(P);
   *blocked = 
      !P->MovePiece(board,followUpMove,moveFrom,moveTo);
}

void TermGame(void)
{
   delete P;
}

ComputerPlayer.h

/*
Header file for the SEEGA game.
Copyright © 2001, Ernst Munter, Kanata, ON, Canada.
  
This header file supports "seega.cpp" which contains the external interface.
   
version 0
————-

This is work in progress, and is not likely to get finished by the deadline.
   
Assumptions
—————-
The size of the board is less than about 100 x 100 to allow some variables
to be stored in chars. 
      
*/
      
#ifndef COMPUTER_PLAYER_H
#define COMPUTER_PLAYER_H

#define xNDEBUG
#include <assert.h>
#include <stdlib.h>
#include <string.h>
#include “seega.h”

#define DBG 0
#if DBG
#include "seegaWindow.h" // provides a board display for debugging
extern SeegaBoard*   gDisplay;
#endif


typedef unsigned char uchar;
typedef unsigned long ulong;
typedef unsigned short ushort;

enum {kE=0,kS=1,kW=2,kN=3,
   kEmpty=0,
   kOutside=3,
   
   kCaptureFactor=1
};

inline long Opposite(long dir){return dir ^ 2;}

// Standard CRC based hash method. 
static struct CRC {
     enum {POLYNOMIAL=0x04c11db7L};
     ulong table[256];
     ulong accum;
     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;
       }
        accum=0;
     }
     void Clear(){accum=0;}
   void HashPosition(Position p)
   {
      ulong acc=accum;
       acc=(acc<<8) ^ table[0xFF & ((acc>>24) ^ p.row)]; 
       accum=(acc<<8) ^ table[0xFF & ((acc>>24) ^ p.col)];
   }
   ulong HashResult() const {return accum;}
} crc;

class MyCell
class MyCell
{
   uchar   row;
   uchar   col;
   uchar   pValue;
   uchar    state;   // MSB indicates center cell
   enum {kCenter=0x80};
   MyCell*   one[4];   // one move away, east to north
   MyCell* two[4];   // two moves away, east to north
   MyCell*   next;   // linked list of mine or opponent's cells
public:
   void Init(int r,int c,int size,MyCell* outside)
   {
      one[kE]=(c&#60;size-1)   ?(this+1)      :(outside);
      one[kS]=(r&#60;size-1)   ?(this+size)   :(outside);
      one[kW]=(c&#62;0)      ?(this-1)      :(outside);
      one[kN]=(r&#62;0)      ?(this-size)   :(outside);
      
      two[kE]=(c&#60;size-2)   ?(this+2)      :(outside);
      two[kS]=(r&#60;size-2)   ?(this+2*size)   :(outside);
      two[kW]=(c&#62;1)      ?(this-2)      :(outside);
      two[kN]=(r&#62;1)      ?(this-2*size)   :(outside);
      
      row=r;
      col=c;
      pValue=kEmpty;   
      if ((r==c) && (r==size/2))
         state=kCenter;
      else state=0;
   }
   void SetOutside()
   {
      memset(this,0,sizeof(*this));
      pValue=kOutside;
   }
   bool IsCenter() const {return (state & kCenter);}
   bool IsEmpty() const {return pValue==0;}
   long PValue() const {return pValue;}
   MyCell* Next() const {return next;}
   Position Pos() const {
      Position pos;
      pos.row=row;
      pos.col=col;
      return pos;
   }
   MyCell* One(int dir) const {return one[dir];}
   MyCell* Two(int dir) const {return two[dir];}
   bool HasNeighbor(long x) const 
   {
      if (one[0]->pValue==x) return true;
      if (one[1]->pValue==x) return true;
      if (one[2]->pValue==x) return true;
      if (one[3]->pValue==x) return true;
      return false;
   }
   long Threat() const {return state;}
   
   void SetPvalue(long x) {pValue=x;}
   void Link(MyCell* & C) {next=C; C=this;}
   
   bool Captures(MyCell* target,long pid,int dir) const
// returns true if ‘this' cell (moved onto by pid) captures the target.
   {
      if ((two[dir]->pValue != pid) ||
         (target->pValue+pid != 3) ||
          target->IsCenter()
         )
         return false;
      return true;
   }   
   
   long Distance(MyCell* C) const 
   {
      long dRow=(row>C->row)?row-C->row:C->row-row;
      long dCol=(col>C->col)?col-C->col:C->col-col;
      return dRow+dCol;
   }
   void SetThreat(long caps){state=caps;}
};

struct SaveCell
{
   MyCell* C;
   long   v;
   void Init(MyCell* CC,long vv){C=CC;v=vv;}
};

class MyBoard
class MyBoard
{
protected:
   long   size;
   long   length;//=size*size
   MyCell*   cells;
   MyCell* sentinel;
   MyCell*   cellList[3];// [of pValue = 0, 1, 2]
   long   numPieces;
   ulong   opponentHash;
   ulong   opponentHasMoved;
public:
   MyBoard(long boardSize):
      size(boardSize),
      length(boardSize*boardSize),
      cells(new MyCell[length+1]),// 1 extra for outside sentinel
      numPieces(0),
      opponentHash(0),
      opponentHasMoved(0)
   {
      MyCell* C=cells;
      sentinel=&cells[boardSize*boardSize];
      for (int row=0;row&#60;size;row++)
      {
         for (int col=0;col&#60;size;col++)
         {
            C-&#62;Init(row,col,size,sentinel);
            C++;
         }
      }
      sentinel->SetOutside();
   }
   ~MyBoard()
   {
      delete [] cells;
   }
   MyCell* CenterCell() const {return cells+length/2;}
   ulong ComputeOpponentHash(long pid)
   {
      crc.Clear();
      MyCell* C=cellList[3-pid];
      while (C)
      {
         crc.HashPosition(C->Pos());
         C=C->Next();
      }
      return crc.HashResult();
   }
   bool Refresh(const Board& board,long pid)
// returns true if numPieces changed
   {
      assert(board.boardSize==size);
      MyCell* C=cells;
      cellList[0]=cellList[1]=cellList[2]=0;
      const char* E=board.cell;
      long lastNumPieces=numPieces;
      long nPieces=0;
      while (C&#60;sentinel)
      {
         long pValue=(uchar)(*E++);
         assert(pValue&#62;=0);
         assert(pValue<=2);
         if (pValue)
            nPieces++;
         C->SetPvalue(pValue);
         C->Link(cellList[pValue]);
         C++;
      }
      numPieces=nPieces;
      ulong oldHash=opponentHash;
      ulong newHash=ComputeOpponentHash(pid);
      opponentHasMoved=(oldHash ^ newHash);
      opponentHash=newHash;
      return (lastNumPieces != nPieces);
   }
};

class MyMove
class MyMove
{
   MyCell*   from;
   short   direction;
   short   value;
public:
   void Init(MyCell* f,long d,long v)
   {
      from=f;
      direction=d;
      value=v;
   }
   long Value() const {return value;}
   MyCell* ToCell() const {return from->One(direction);}
   MyCell* FromCell() const {return from;}
   void ConvertMove(Position* moveFrom,Position* moveTo)
   {
      *moveFrom=from->Pos();
      *moveTo=ToCell()->Pos();
   }
   int operator- (MyMove& b) const {return b.value-value;}
};


inline int CmpMoves(const void* a,const void* b)
{
   MyMove* ma=(MyMove*) a;
   MyMove* mb=(MyMove*) b;
   int d=*ma - *mb;
   return d;
}

class ComputerPlayer
class ComputerPlayer:public MyBoard
{
public:
   ComputerPlayer(int boardSize, char pieceValue, 
                     Boolean playFirst,int stalemateThreshold):
      MyBoard(boardSize),
      playerId(pieceValue),
      first(playFirst),
      limit(stalemateThreshold),
      staleness(0),
      lastToCell(0),
      cellStackStorage(new SaveCell[length]),
      cellStack(cellStackStorage),
      cellStackEnd(cellStackStorage+length),
      maxNumMoves(2*length),
      moveList(new MyMove[maxNumMoves]),
      endMoveList(moveList+maxNumMoves)
   {
      cellStackStorage->Init(0,0);
   }
   
   void PlacePieces(const Board& board,Position* piece1,
                                             Position* piece2)
   {
      Refresh(board,playerId);
      
      MyCell* C1=PlacePiece();
      C1->SetPvalue(playerId);
      MyCell* C2=PlacePiece();
      *piece1 = C1->Pos();
      *piece2 = C2->Pos();
   }
   
   bool MovePiece(const Board& board,bool followUpMove,
      Position* moveFrom,Position* moveTo)
   {
      bool restartTimer=Refresh(board,playerId);
      if (restartTimer)
      { // indicating a capture since the last turn
      //   staleness=0;
         opponentHasMoved=1;
      } //else staleness++;
      // staleness value was planned to select a different strategy when
      // no useful moves are being made.  Not implemented
         
      LookForTrouble(playerId);// identify vulnerable pieces
      
      long numMoves;
      if (followUpMove)
      {
         numMoves=MakeFollowUpMoveList(moveList,playerId,true);
      } else if (!opponentHasMoved)
      {
         numMoves=MakeUnblockingMoveList(moveList,playerId);
      } else numMoves=MakeMoveList(moveList,playerId,true,0,0);
      
      if (numMoves<=0)
         return false;
      if (numMoves>1)
         qsort(moveList,numMoves,sizeof(MyMove),CmpMoves);
      
      MyMove* bestMove=RandomizeEquals(numMoves);
      bestMove->ConvertMove(moveFrom,moveTo);
      lastToCell=bestMove->ToCell();
      return true;
   }
   
private:
   
   MyCell* PlacePiece()
// intended to return a ‘good' spot to place a piece
   {
      long numMoves=MakePlaceList(moveList,playerId);
      if (numMoves>1)
      {
         qsort(moveList,numMoves,sizeof(MyMove),CmpMoves);
      }
      MyMove* bestMove=RandomizeEquals(numMoves);
      return bestMove->FromCell();
   }
   
   long MakePlaceList(MyMove* M,long pid)
// returns number of moves in a move list, to be used for placement
   {
      MyCell* fromC=CenterCell();
      MyCell* toC=cellList[0];// all (other) empty cells
      long numMoves=0;
      long maxMoves=endMoveList-M;
      if (first) // second player will have moved first into the center
         fromC->SetPvalue(3-pid);
      else
         fromC->SetPvalue(pid);
      while (toC)
      {
         if ((toC != fromC) && (toC->IsEmpty()))
         {
            bool lookAhead=true;
            bool mustCapture=false;
            long moveValue = EvaluateMove( M+numMoves, fromC, toC, pid, 
                           lookAhead, mustCapture);
            
            M[numMoves].Init(toC,0,moveValue);
            numMoves++;
            if (numMoves >= maxMoves)
               numMoves=PruneMovelist(M,numMoves);
         }
         toC=toC->Next();
      }
      return numMoves;
   }
   
   long DoMove(MyCell* fromCell,MyCell* toCell,long pid)
// returns number of captures;
// leaves all changed cells on the stack.
   {
      Save2Cells(fromCell,toCell);
      toCell->SetPvalue(pid);
      fromCell->SetPvalue(kEmpty);
      long numCaps=0;
      for (int capDir=0;capDir<4;capDir++)
      {
         MyCell* target=toCell->One(capDir);
         if (toCell->Captures(target,pid,capDir))
         {
            PushCell(target);
            target->SetPvalue(kEmpty);
            target->SetThreat(1);
            numCaps++;
         }
      }
// stack=...,fromCell,toCell,captured target1,captured target2,etc
      
      long bestFollowUps=0;
      if (numCaps)// check possible followUps
      {
         SaveCell* mark=cellStack;// mark cell stack so we can unwind
         for (int d2=0;d2<4;d2++)
         {
            MyCell* xCell=toCell->One(d2);
            if (xCell->IsEmpty())
            {
               long followUpCaps=DoMove(toCell,xCell,pid);
               if (followUpCaps > bestFollowUps)
               {
                  bestFollowUps=followUpCaps;
                  // keep first followUp found on stack and quit
                  break;
                  // (ideally should save on a separate stack, 
                  //   so we can undo, and keep only the best choice)
               } 
               RestoreToMark(mark);
            }
         }
      }
// when we return we should have the board in the state after the move
// and all changed cells on the stack.  
// Unrolling the stack will later undo the move.
      return numCaps+bestFollowUps;
   }
   
   long CountLosses(MyMove* M,MyCell* toCell,long pid)
// On entry, my move (toCell) has been made on my board.
// Now we simulate the opponent's responses, but only in the vicinity of my move.
// Returns maximum number of pieces opponent can capture after my move.
   {
      long foe=3-pid;
      long distance=(toCell)?2:0;
      SaveCell* mark=cellStack;
      long numMoves=MakeMoveList(M,foe,false,distance,toCell);
      if (numMoves)
      {
         if (numMoves>1)
         {
            qsort(M,numMoves,sizeof(MyMove),CmpMoves);
         }
         MyMove* bestMove=M;
         return M->Value();
      }
      return 0;
   }
   
   long PruneMovelist(MyMove* M,long numMoves)
// if allocated movelist gets full, this routine is used to:
//    remove the lower value moves to reduce list by 1/4
   {
      qsort(M,numMoves,sizeof(MyMove),CmpMoves);
      return numMoves/2 + numMoves/4;
   }
   
   long MakeUnblockingMoveList(MyMove* M,long pid)
// returns moves which might free a blocked opponent
   {
      MyCell* fromC=cellList[pid];
      long numMoves=0;
      long maxMoves=endMoveList-M;
      while (fromC)
      {
         if ((fromC->PValue()==pid) && 
            (fromC->HasNeighbor(3-pid)))
         for (int dir=0;dir<4;dir++)
         {
            MyCell* toC=fromC->One(dir);
            if (toC->PValue())
               continue;
               
            long moveValue = EvaluateMove(M+numMoves, fromC, toC, pid, 
                                                      true, false);
            
            M[numMoves].Init(fromC,dir,moveValue);
            numMoves++;
            if (numMoves >= maxMoves)
               numMoves=PruneMovelist(M,numMoves);
         }
         fromC=fromC->Next();
      }
      return numMoves;
   }
   
   long MakeMoveList(MyMove* M,long pid,bool lookAhead,long distance,MyCell* xCell)
// returns number of moves in list
   {
      MyCell* fromC=cellList[pid];
      long numMoves=0;
      long maxMoves=endMoveList-M;
      while (fromC)
      {
         if ((fromC->PValue()==pid) && 
            ((distance==0) || (fromC->Distance(xCell)<=distance)))
         {
            for (int dir=0;dir<4;dir++)
            {
               MyCell* toC=fromC->One(dir);
               if (toC->PValue())
                  continue;
            
               bool mustCapture=false;
               long moveValue =    EvaluateMove(M+numMoves, fromC, toC, 
                        pid, lookAhead,mustCapture);
               
               M[numMoves].Init(fromC,dir,moveValue);
               numMoves++;
               if (numMoves >= maxMoves)
                  numMoves=PruneMovelist(M,numMoves);
            }
         }
         fromC=fromC->Next();
      }
      return numMoves;
   }
   
   long MakeFollowUpMoveList(MyMove* M,long pid,bool lookAhead)
   {
// generates only capturing moves by the last piece moved.
// should only be called with followUp after another move
      MyCell* fromC=lastToCell;
      assert(fromC);
      long numMoves=0;
      long maxMoves=endMoveList-M;
      for (int dir=0;dir<4;dir++)
      {
         MyCell* toC=fromC->One(dir);
         if (!toC->IsEmpty())
            continue;
            
         bool mustCapture=true;
         long moveValue = EvaluateMove(M+numMoves, fromC, toC, pid, 
                        lookAhead, mustCapture);
         
         M[numMoves].Init(fromC,dir,moveValue);
         numMoves++;
         if (numMoves >= maxMoves)
            numMoves=PruneMovelist(M,numMoves);
      }
      assert(numMoves);
      return numMoves;
   }
   
   long EvaluateMove(MyMove* M,MyCell* fromC, MyCell* toC, 
                     long pid, bool lookAhead, bool mustCapture)
// executes a move and accounts captures and losses into a ‘moveValue'
   {
      SaveCell* mark=cellStack;
      long numCaps=DoMove(fromC,toC,pid);
      if (mustCapture && numCaps<=0)
      {
         RestoreToMark(mark);
         return -length*kCaptureFactor;
      }
#if DBG
      RedrawBoard();
#endif
      long numLost=(lookAhead)?CountLosses(M,toC,pid):0;
      RestoreToMark(mark);
#if DBG
      RedrawBoard();
#endif
      long moveValue = kCaptureFactor*
                                    (fromC->Threat()+numCaps-numLost);
      return moveValue;
   }
   
   MyMove* RandomizeEquals(long numMoves)
// instead of always taking the first move from the list, we choose randomly
// among the first equal valued moves.
   {
      long numEqual=1;
      MyMove* endMove=moveList+numMoves;
      MyMove* m=moveList;
      long bestValue=m->Value();
      while (++m < endMove)
      {
         if (m->Value() >= bestValue) 
         {
            numEqual++;
         } else break;
      }
      assert(numEqual);
      if (numEqual>1)
         return moveList+(rand()%numEqual);
      return &moveList[0];   
   }
   
   void ClearThreats()
   {
      MyCell* C=cells;
      while (C&#60;sentinel)
      {
         C-&#62;SetThreat(0);
         C++;
      }
   }
   
   void LookForTrouble(long pid)
// Assign a ‘threat' value of 1 to all pieces that could be taken by the opponent
// This is done implicitely by creating a dummy moveList for the opponent.
   {
      ClearThreats();
      MakeMoveList(moveList,3-pid,false,0,0);
   }
   
// Stack operations for saving and restoring cell states during move exploration
   void PushCell(MyCell* C)
   {
      assert(cellStack+1&#60;cellStackEnd);
      (++cellStack)-&#62;Init(C,C-&#62;PValue());
   }
   void PushBlank()
   {
      assert(cellStack+1&#60;cellStackEnd);
      (++cellStack)-&#62;Init(0,0);
   }
   void Save2Cells(MyCell* C1,MyCell* C2)
   {
      PushCell(C1);
      PushCell(C2);
   }
   void PopCell()
   {
      MyCell* C=cellStack->C;
      assert(C);
      C->SetPvalue(cellStack->v); 
      cellStack—;
   }
   void Restore2Cells()
   {
      PopCell();
      PopCell();
   }
   void RestoreCells(long n)
   {
      for (int i=0;i&#60;n;i++)
         PopCell();
   }
   void RestoreToMark(SaveCell* mark)
   {
      while (cellStack&#62;mark)
      {
         PopCell();
      }
   }
#if DBG   
   void RedrawBoard()
   {
      Position p;
      MyCell* C=cells;
      for (p.row=0;p.row&#60;size;p.row++)
      {
         for (p.col=0;p.col&#60;size;p.col++,C++)
         {
            long pvalue=C-&#62;PValue();
            gDisplay-&#62;PaintSquare(p,pvalue);
         }
      }
      gDisplay->Run(p);
   }
#endif
   uchar    playerId;// 1 or 2
   bool    first;
   long    limit;
   long   staleness;
   MyCell* lastToCell;
   SaveCell*   cellStackStorage;
   SaveCell*   cellStack;
   SaveCell*   cellStackEnd;
   long   maxNumMoves;
   MyMove* moveList;
   MyMove* endMoveList;
};

#endif

SeegaWindow.h

#ifndef SEEGA_WINDOW_H
#define SEEGA_WINDOW_H


#include "seega.h"
#include &#60;assert.h&#62;
#include &#60;string.h&#62;
#include &#60;stdio.h&#62;
   
typedef unsigned char uchar;
typedef unsigned long ulong;
   
enum {
   kMaxSpacing   = 32,
   kMinSpacing = 5,
   kLegendSpace= 12,
   kInset      = 2,
   
   kSelf      = 16,
   kOpponent   = 32,
   kInvalidSquare = 64,
   
   kSelectColor = 2
};

const RGBColor RGBGreen={0x0000,0xCFFF,0x0000};// center box
const RGBColor RGBRed=   {0xAFFF,0x0000,0x0000}; // player[1] boxes
const RGBColor RGBLightRed=   {0xFFFF,0x8000,0x0000};
         // selected player[1] boxes
const RGBColor RGBBlue= {0x0000,0x0000,0xAFFF};// player[0] boxes
const RGBColor RGBLightBlue= {0x0000,0x8000,0xFFFF};
         // selected player[0] boxes
const RGBColor RGBWhite={0xFFFF,0xFFFF,0xFFFF};
const RGBColor RGBGray={0x1FFF,0x1FFF,0x1FFF};
const RGBColor RGBBlack={0,0,0};

const RGBColor gBoxColor[5] = 
         // color for empty, first and second players
{
   RGBWhite,RGBBlue,RGBRed,RGBLightBlue,RGBLightRed
};


struct SeegaBoard
{
   long       gSpacing;
   long       gMargin;
   long      size;
   WindowPtr    window;
   long      mySquares;
   long      oppSquares;
   
   Board*      board;   // logical board
   
   SeegaBoard(long boardSize,WindowPtr colorWindow,Board* brd):
      size(boardSize),
      window(colorWindow),
      mySquares(0),
      oppSquares(0),
      board(brd)
   {   
      long windowWidth=window->portRect.right-window->portRect.left;
      long windowHeight=window->portRect.bottom-window->portRect.top;
      gSpacing=(windowWidth<=windowHeight)?windowWidth:windowHeight;
      assert(gSpacing>(kInset+kInset)*size);
      gSpacing/=(size+1);
      gMargin=gSpacing/2;
      SetPort(window);
      DrawGrid();
      Position centerP={size/2,size/2};
      PaintSquare(centerP,0);
   }
   
   void LabelSquare(Position p,unsigned long colorValue,long labelValue)
   {
      PaintSquare(p,colorValue);
      long L=gMargin+kInset+p.col*gSpacing;
      long T=gMargin+kInset+p.row*gSpacing+gSpacing/2;
      MoveTo(L,T);
      Str255 str;
      if (colorValue==0)
         RGBForeColor(&RGBBlack);
      else
         RGBForeColor(&RGBWhite);
      NumToString(labelValue,str);
      DrawString(str);
   }
   
   void PaintSquare(Position p,unsigned long value)
   {
      assert(value < 5);
      RGBColor color=gBoxColor[value];
      RGBForeColor (&color);
      long L=gMargin+kInset+p.col*gSpacing;
      long T=gMargin+kInset+p.row*gSpacing;
      long R=L+gSpacing-1-kInset;
      long B=T+gSpacing-1-kInset;
      Rect rect={T,L,B,R};
      PaintRect(&rect);
      if ((p.row==size/2) && (p.col==p.row))
      {
         RGBForeColor (&RGBGreen);
         Rect center={T+gSpacing/4,L+gSpacing/4,B-gSpacing/4,R-gSpacing/4};
         PaintRect(&center);
      }
   }
   
   void DrawGrid()
   {
      SetPort(window);
      RGBColor   gridColor=RGBGray;   //{0x1FFF,0x1FFF,0x1FFF};
      RGBForeColor (&gridColor);
      for (long row=0;row<=size;row++)
      {
         long x=gMargin;
         long y=gMargin+row*gSpacing;
         MoveTo(x,y);
         LineTo(x+gSpacing*size,y);
      }
         
      for (long col=0;col<=size;col++)
      {
         long x=gMargin+col*gSpacing;
         long y=gMargin;
         MoveTo(x,y);
         LineTo(x,y+gSpacing*size);
      }
   }
   
   bool ClosestPosition(const Point mouse,Position & p)
   // returns false if clicked outside of active window
   {
      long hdist=mouse.h-gMargin;
      if ((hdist<0) || (hdist>=gSpacing*size))
         return false;
      p.col=hdist/gSpacing;
      if (p.col<0) p.col=0;
      if (p.col>(size-1)) p.col=size-1;
      
      long vdist=mouse.v-gMargin;
      if ((vdist<0) || (vdist>=gSpacing*size))
         return false;
      p.row=vdist/gSpacing;
      if (p.row<0) p.row=0;
      if (p.row>(size-1)) p.row=size-1;
                  assert(p.row>=0 && p.col>=0);
                  assert(p.row&#60;size &#38;&#38; p.col&#60;size);
      return true;
   }
   
   bool Run(Position &#38; p) //returns true if position selected
   {
      Boolean      gotEvent;
      EventRecord   event;
      do {
         SystemTask();
         gotEvent = GetNextEvent(everyEvent, &#38;event);
      
         if ( gotEvent ) {
            int rc=DoEvent(&#38;event,p);
            if (rc)
            {
               if (rc&#62;0)
               {
                  assert(p.row&#62;=0 &#38;&#38; p.col&#62;=0);
                  assert(p.row&#60;size &#38;&#38; p.col&#60;size);
               }
               return (rc&#62;0);
            }
         }
      
      } while ( true );   
      return false;
   }
   
   int DoEvent(EventRecord* event,Position & p)
   // returns 1 if mouse click inside field 
   // returns -1 if key hit or mouse click outside field
   // else returns 0 
   {
      switch ( event->what ) {
         case mouseDown:
         {
            long part = FindWindow(event->where, &window);
            if ( part == inContent)
            {
               Point mouse = event->where;   // get the click position 
               GlobalToLocal(&mouse);
               long L=mouse.h;
               long T=mouse.v;
               if (!ClosestPosition(mouse,p))
                  return -1;
                  
                  assert(p.row>=0 && p.col>=0);
                  assert(p.row&#60;size &#38;&#38; p.col&#60;size);
               return 1;
            }
            break;
         }
         case keyDown:   assert(0);
         case autoKey:  return -1;
      }
      return 0;
   }
};

#endif


 
AAPL
$524.75
Apple Inc.
-6.95
MSFT
$39.69
Microsoft Corpora
-0.30
GOOG
$526.94
Google Inc.
-7.87

MacTech Search:
Community Search:

Software Updates via MacUpdate

MacFamilyTree 7.1.6 - Create and explore...
MacFamilyTree gives genealogy a facelift: it's modern, interactive, incredibly fast, and easy to use. We're convinced that generations of chroniclers would have loved to trade in their genealogy... Read more
EtreCheck 1.9.9 - For troubleshooting yo...
EtreCheck is a simple little app to display the important details of your system configuration and allow you to copy that information to the Clipboard. It is meant to be used with Apple Support... Read more
TeamViewer 9.0.28116 - Establish remote...
TeamViewer gives you remote control of any computer or Mac over the Internet within seconds, or can be used for online meetings. Find out why more than 200 million users trust TeamViewer! Free for... Read more
Viber 4.1.0 - Send messages and make cal...
Viber lets you send free messages and make free calls to other Viber users, on any device and network, in any country! Viber syncs your contacts, messages and call history with your mobile device,... Read more
Apple iOS 7.1.1 - The latest version of...
The latest version of iOS can be downloaded through iTunes. Apple iOS 7 brings an all-new design and all-new features. Simplicity Simplicity is often equated with minimalism. Yet true simplicity is... Read more
1Password 4.3 - Powerful password manage...
1Password is a password manager that uniquely brings you both security and convenience. It is the only program that provides anti-phishing protection and goes beyond password management by adding Web... Read more
Lens Blur 1.3.0 - True out-of-focus boke...
Let Lens Blur transform your existing photo into true SLR-quality out-of-focus bokeh effect! Everyone needs a gorgeous personalized background for a social profile, blog, Web/UI design, presentation... Read more
VMware Fusion 6.0.3 - Run Windows apps a...
VMware Fusion allows you to create a Virtual Machine on your Mac and run Windows (including Windows 8.1) and Windows software on your Mac. Run your favorite Windows applications alongside Mac... Read more
BitTorrent Sync 1.3.93 - Sync files secu...
BitTorrent Sync allows you to sync unlimited files between your own devices, or share a folder with friends and family to automatically sync anything. File transfers are encrypted. Your information... Read more
Tweetbot 1.5.1 - Popular iOS twitter cli...
Tweetbot is a full-featured OS X Twitter client with a lot of personality. Whether it's the meticulously-crafted interface, sounds and animation, or features like multiple timelines and column views... Read more

Latest Forum Discussions

See All

Leo's Fortune (Games)
Leo's Fortune 1.0.2 Device: iOS Universal Category: Games Price: $4.99, Version: 1.0.2 (iTunes) Description: Leo’s Fortune is a platform adventure game where you hunt down the cunning and mysterious thief that stole your gold.... | Read more »
iOOTP Baseball 2014 Edition Review
iOOTP Baseball 2014 Edition Review By Carter Dotson on April 23rd, 2014 Our Rating: :: SOLID CONTRACTUniversal App - Designed for iPhone and iPad The long-running baseball simulator returns to mobile with a much-improved entry in... | Read more »
148Apps Live on Twitch: Soccer Rally 2 w...
Soccer Rally 2 from IceFlame Games officially releases on Thursday, bringing perhaps the most realistic car soccer action to the App Store since the original released. David Deacon of IceFlame Games will join us on our Twitch channel to talk about... | Read more »
NightCap Pro Review
NightCap Pro Review By Jennifer Allen on April 23rd, 2014 Our Rating: :: NIGHT TIME SNAPPINGUniversal App - Designed for iPhone and iPad Taking photos in low light conditions has always been tricky, but NightCap Pro has just made... | Read more »
Plague Inc. has Mutated Yet Again – We’r...
Plague Inc. has Mutated Yet Again – We’re All Doomed Even More than Usual Posted by Rob Rich on April 23rd, 2014 [ permalink ] Universal App - Designed for iPhone and iPad | Read more »
Intake from Cipher Prime Coming to iPad...
Cipher Prime’s Inake is coming to iPad on May 1, as exclusively revealed yesterday on our Twitch channel. | Read more »
Gusto Email App Review
Gusto Email App Review By Jennifer Allen on April 23rd, 2014 Our Rating: :: POWERFUL SEARCHINGiPhone App - Designed for the iPhone, compatible with the iPad Focusing on making it easy to browse files and photos attached to your... | Read more »
New Update Adds Two More Cars to Fishlab...
New Update Adds Two More Cars to Fishlabs’ Sports Car Challenge 2 Posted by Rob Rich on April 23rd, 2014 [ permalink ] Universal App - Designed for iPhone and iPad | Read more »
What’s Up with Readdle? – The Verge Exam...
What’s Up with Readdle? | Read more »
Knight Saves Queen Review
Knight Saves Queen Review By Jennifer Allen on April 23rd, 2014 Our Rating: :: PUZZLING MASH UPUniversal App - Designed for iPhone and iPad Mixing up puzzle elements with Chess-based sensibilities is a fun move for this simplistic... | Read more »

Price Scanner via MacPrices.net

iPad Sales “Lull” A Reality Correction Of Unm...
I have lots of time for Jean-Louis Gassée, the former Apple Computer executive (1981 to 1990) who succeeded Steve Jobs as head of Macintosh development when the latter was dismissed in 1985. Mr.... Read more
Apple Makes OS X Betas Available To All – Wit...
Apple’s OS X Beta Seed Program, which lets you install the latest pre-release builds, try it out, and submit your feedback, is now open to anyone who wants to sign on rather than to developers and... Read more
Apple Releases iOS 7.1.1 Update
The latest iOS 7.1.1 update contains improvements, bug fixes and security updates, including: • Further improvements to Touch ID fingerprint recognition • Fixes a bug that could impact keyboard... Read more
Logitech Announces Thinner, Lighter, More Fle...
Logitech has announced an update to its Ultrathin for iPad Air, iPad mini and iPad mini with Retina display, improving the flexibility and design of its award-winning predecessor with an even thinner... Read more
Logitech Introduces Hinge, Big Bang and Turna...
Logitech has announced expansion of its tablet product line with three new cases – the Logitech Hinge, the Logitech Big Bang and the Logitech Turnaround – each for the iPad Air, iPad mini and iPad... Read more
WaterField’s Rough Rider Leather Messenger Ba...
WaterField Designs have announced the new 15-inch size of their popular Rough Rider leather messenger bag, a vintage-looking bag that combines Old West charm and ruggedness with distinctly modern... Read more
New Mac Pro on sale, save $100 on the 4-Core...
J&R has the new 4-Core Mac Pro in stock today and on sale for $2899 including free shipping plus NY sales tax only. Their price is $100 off MSRP, and it’s the lowest price available for this... Read more
Apple refurbished iMacs available for up to $...
The Apple Store has Apple Certified Refurbished 2013 iMacs available for up to $300 off the cost of new models. Apple’s one-year warranty is standard, and shipping is free. - 27″ 3.4GHz iMac – $1699... Read more
Updated iPad Price Trackers
We’ve updated our iPad Price Tracker and our iPad mini Price Tracker with the latest information on prices and availability from Apple and other resellers. Using a mobile device? We’ve also updated... Read more
Everything You Wanted To Know And Probably Mo...
Macworld UK’s Lou Hattersley takes a look inside Apple’s A7 System On Chip (SoC) , noting that its processor module is much more powerful than other smartphone chipsets. He notes that the A7 was a... Read more

Jobs Board

*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
Position Opening at *Apple* - Apple (United...
…customers purchase our products, you're the one who helps them get more out of their new Apple technology. Your day in the Apple Store is filled with a range of 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
*Apple* Inc. Research Data Specialist - Appl...
…of Worldwide Market Research & Intelligence. The team is responsible for conducting Apple branded consumer market research. It is also responsible for analyzing data Read more
*Apple* Automotive Parts Department position...
Apple Automotive is one of the fastest growing dealer…and it shows. Consider making the switch to the Apple Automotive Group today! At Apple Automotive, we Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.