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
$116.47
Apple Inc.
+0.16
MSFT
$47.98
Microsoft Corpora
-0.72
GOOG
$537.50
Google Inc.
+2.67

MacTech Search:
Community Search:

Software Updates via MacUpdate

Cobook 3.0.7 - Intelligent address book....
Cobook Contacts is an intuitive, engaging address book. Solve the problem of contact management with Cobook Contacts and its simple interface and powerful syncing and integration possibilities.... Read more
StatsBar 1.9 - Monitor system processes...
StatsBar gives you a comprehensive and detailed analysis of the following areas of your Mac: CPU usage Memory usage Disk usage Network and bandwidth usage Battery power and health (MacBooks only)... Read more
Cyberduck 4.6 - FTP and SFTP browser. (F...
Cyberduck is a robust FTP/FTP-TLS/SFTP browser for the Mac whose lack of visual clutter and cleverly intuitive features make it easy to use. Support for external editors and system technologies such... Read more
Maya 2015 - Professional 3D modeling and...
Maya is an award-winning software and powerful, integrated 3D modeling, animation, visual effects, and rendering solution. Because Maya is based on an open architecture, all your work can be scripted... Read more
Evernote 6.0.1 - Create searchable notes...
Evernote allows you to easily capture information in any environment using whatever device or platform you find most convenient, and makes this information accessible and searchable at anytime, from... Read more
calibre 2.11 - Complete e-library manage...
Calibre is a complete e-book library manager. Organize your collection, convert your books to multiple formats, and sync with all of your devices. Let Calibre be your multi-tasking digital... Read more
Herald 5.0.1 - Notification plugin for M...
Note: Versions 2.1.3 (for OS X 10.7), 3.0.6 (for OS X 10.8), and 4.0.8 (for OS X 10.9) are no longer supported by the developer. Herald is a notification plugin for Mail.app, Apple's Mac OS X email... Read more
Firetask 3.7 - Innovative task managemen...
Firetask uniquely combines the advantages of classical priority-and-due-date-based task management with GTD. Stay focused and on top of your commitments - Firetask's "Today" view shows all relevant... Read more
TechTool Pro 7.0.6 - Hard drive and syst...
TechTool Pro is now 7, and this is the most advanced version of the acclaimed Macintosh troubleshooting utility created in its 20-year history. Micromat has redeveloped TechTool Pro 7 to be fully 64... Read more
PhotoDesk 3.0.1 - Instagram client for p...
PhotoDesk lets you view, like, comment, and download Instagram pictures/videos! (NO Uploads! / Image Posting! Instagram forbids that! AND you *need* an *existing* Instagram account). But you can do... Read more

Latest Forum Discussions

See All

Ubisoft Gives Everyone Two New Ways to E...
Ubisoft Gives Everyone Two New Ways to Earn In-Game Stuff for Far Cry 4 Posted by Jessica Fisher on November 21st, 2014 [ permalink ] | Read more »
Golfinity – Tips, Tricks, Strategies, an...
Dig this: Would you like to know what we thought of being an infinite golfer? Check out our Golfinity review! Golfinity offers unlimited ways to test your skills at golf. Here are a few ways to make sure your score doesn’t get too high and your... | Read more »
Dark Hearts, The Sequel to Haunting Meli...
Dark Hearts, The Sequel to Haunting Melissa, is Available Now Posted by Jessica Fisher on November 21st, 2014 [ permalink ] Universal App - Designed for iPhone and iPad | Read more »
Meowza! Toyze Brings Talking Tom to Life...
Meowza! | Read more »
Square Enix Announces New Tactical RPG f...
Square Enix Announces New Tactical RPG for Mobile, Heavenstrike Rivals. Posted by Jessica Fisher on November 21st, 2014 [ permalink ] With their epic stories and gorgeous graphics, | Read more »
Quest for Revenge (Games)
Quest for Revenge 1.0.0 Device: iOS Universal Category: Games Price: $4.99, Version: 1.0.0 (iTunes) Description: The great Kingdom of the west has fallen. The gods ignore the prayers of the desperate. A dark warlord has extinguished... | Read more »
Threadz is a New Writing Adventure for Y...
Threadz is a New Writing Adventure for You and Your Friends Posted by Jessica Fisher on November 21st, 2014 [ permalink ] In the tradition of round-robin storytelling, | Read more »
SteelSeries Stratus XL Hardware Review
Made by: SteelSeries Price: $59.99 Hardware/iOS Integration Rating: 4 out of 5 stars Usability Rating: 4.5 out of 5 stars Reuse Value Rating: 4.25 out of 5 stars Build Quality Rating: 4.5 out of 5 stars Overall Rating: 4.31 out of 5 stars | Read more »
ACDSee (Photography)
ACDSee 1.0.0 Device: iOS iPhone Category: Photography Price: $1.99, Version: 1.0.0 (iTunes) Description: Capture, perfect, and share your photos with ACDSee. The ACDSee iPhone app combines an innovative camera, a powerful photo... | Read more »
ProTube for YouTube (Entertainment)
ProTube for YouTube 2.0.2 Device: iOS Universal Category: Entertainment Price: $1.99, Version: 2.0.2 (iTunes) Description: ProTube is the ultimate, fully featured YouTube app. With it's highly polished design, ProTube offers ad-free... | Read more »

Price Scanner via MacPrices.net

15″ 2.2GHz Retina MacBook Pro on sale for $17...
 B&H Photo has the 2014 15″ 2.2GHz Retina MacBook Pro on sale today for $1749. Shipping is free, and B&H charges NY sales tax only. B&H will also include free copies of Parallels Desktop... Read more
27-inch 3.5GHz 5K iMac in stock today and on...
 B&H Photo has the new 27″ 3.5GHz 5K iMac in stock today and on sale for $2299 including free shipping plus NY sales tax only. Their price is $200 off MSRP, and it’s the lowest price available... Read more
21-inch 1.4GHz iMac on sale for $979, save $1...
B&H Photo has the new 21″ 1.4GHz iMac on sale for $979.99 including free shipping plus NY sales tax only. Their price is $120 off MSRP. B&H will also include free copies of Parallels Desktop... Read more
13-inch 1.4GHz/256GB MacBook Air on sale for...
B&H Photo has lowered their price on the 13″ 1.4GHz/256GB MacBook Air to $1059.99 including free shipping plus NY sales tax only. Their price is $140 off MSRP, and it’s the lowest price for this... Read more
Save up to $400 with Apple refurbished 2014 1...
The Apple Store has restocked Apple Certified Refurbished 2014 15″ Retina MacBook Pros for up to $400 off the cost of new models. An Apple one-year warranty is included with each model, and shipping... Read more
New 13-inch 1.4GHz MacBook Air on sale for $8...
 Adorama has the 2014 13″ 1.4GHz/128GB MacBook Air on sale for $899.99 including free shipping plus NY & NJ tax only. Their price is $100 off MSRP. B&H Photo has the 13″ 1.4GHz/128GB MacBook... Read more
Apple Expected to Reverse Nine-Month Tablet S...
Apple and Samsung combined accounted for 62 percent of the nearly 36 million branded tablets shipped in 3Q 2014, according to early vendor shipment share estimates from market intelligence firm ABI... Read more
Stratos: 30 Percent of US Smartphone Owners t...
Stratos, Inc., creator of the Bluetooth Connected Card Platform, has announced results from its 2014 Holiday Mobile Payments Survey. The consumer survey found that nearly one out of three (30 percent... Read more
2014 1.4GHz Mac mini on sale for $449, save $...
 B&H Photo has lowered their price on the new 1.4GHz Mac mini to $449.99 including free shipping plus NY tax only. Their price is $50 off MSRP, and it’s the lowest price available for this new... Read more
Check Apple prices on any device with the iTr...
MacPrices is proud to offer readers a free iOS app (iPhones, iPads, & iPod touch) and Android app (Google Play and Amazon App Store) called iTracx, which allows you to glance at today’s lowest... 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
*Apple* Solutions Consultant (ASC)- Retail S...
**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, *Apple* Financial Services...
**Job Summary** Apple Financial Services (AFS) offers consumers, businesses and educational institutions ways to finance Apple purchases. We work with national and Read more
*Apple* Store Leader Program - College Gradu...
Job Description: Job Summary As an Apple Store Leader Program agent, you can continue your education as you major in the art of leadership at the Apple Store. You'll Read more
*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
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.