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
$98.38
Apple Inc.
-0.64
MSFT
$43.89
Microsoft Corpora
-0.09
GOOG
$585.61
Google Inc.
-4.99

MacTech Search:
Community Search:

Software Updates via MacUpdate

Drive Genius 3.2.4 - Powerful system uti...
Drive Genius is an OS X utility designed to provide unsurpassed storage management. Featuring an easy-to-use interface, Drive Genius is packed with powerful tools such as a drive optimizer, a... Read more
Vitamin-R 2.15 - Personal productivity t...
Vitamin-R creates the optimal conditions for your brain to work at its best by structuring your work into short bursts of distraction-free, highly focused activity alternating with opportunities for... Read more
Toast Titanium 12.0 - The ultimate media...
Toast Titanium goes way beyond the very basic burning in the Mac OS and iLife software, and sets the standard for burning CDs, DVDs, and now Blu-ray discs on the Mac. Create superior sounding audio... Read more
OS X Yosemite Wallpaper 1.0 - Desktop im...
OS X Yosemite Wallpaper is the gorgeous new background image for Apple's upcoming OS X 10.10 Yosemite. This wallpaper is available for all screen resolutions with a source file that measures 5,418... Read more
Acorn 4.4 - Bitmap image editor. (Demo)
Acorn is a new image editor built with one goal in mind - simplicity. Fast, easy, and fluid, Acorn provides the options you'll need without any overhead. Acorn feels right, and won't drain your bank... Read more
Bartender 1.2.20 - Organize your menu ba...
Bartender lets you organize your menu bar apps. Features: Lets you tidy your menu bar apps how you want. See your menu bar apps when you want. Hide the apps you need to run, but do not need to... Read more
TotalFinder 1.6.2 - Adds tabs, hotkeys,...
TotalFinder is a universally acclaimed navigational companion for your Mac. Enhance your Mac's Finder with features so smart and convenient, you won't believe you ever lived without them. Tab-based... Read more
Vienna 3.0.0 RC 2 :be5265e: - RSS and At...
Vienna is a freeware and Open-Source RSS/Atom newsreader with article storage and management via a SQLite database, written in Objective-C and Cocoa, for the OS X operating system. It provides... Read more
VLC Media Player 2.1.5 - Popular multime...
VLC Media Player is a highly portable multimedia player for various audio and video formats (MPEG-1, MPEG-2, MPEG-4, DivX, MP3, OGG, ...) as well as DVDs, VCDs, and various streaming protocols. It... Read more
Default Folder X 4.6.7 - Enhances Open a...
Default Folder X attaches a toolbar to the right side of the Open and Save dialogs in any OS X-native application. The toolbar gives you fast access to various folders and commands. You just click... Read more

Latest Forum Discussions

See All

Note Review
Note Review By Jennifer Allen on July 29th, 2014 Our Rating: :: TOO SIMPLEiPhone App - Designed for the iPhone, compatible with the iPad Note is a note taking app that’s a little too short on features to be worth its asking price... | Read more »
Chainsaw Warrior Goes on Sale & Ther...
Chainsaw Warrior Goes on Sale & There’s a Chance to Win a Copy of the Original Board Game Posted by Jennifer Allen on July 29th, 2014 [ permalink | Read more »
It Came From Canada: Tiny Tower Vegas
If you go to a casino, you might make a lot of money. If you run a casino, you’re guaranteed to make a lot of money. The choice seems pretty obvious. So while waiting for your shady real estate deals to move forward, get prepared with Tiny Tower... | Read more »
Z Hunter Review
Z Hunter Review By Lee Hamlet on July 29th, 2014 Our Rating: :: RIGHT ON TARGETUniversal App - Designed for iPhone and iPad While it might not necessarily break new ground, Z Hunter has enough tricks up its sleeve to ensure that... | Read more »
Huge Update Comes To Duet, Adding 48 New...
Huge Update Comes To Duet, Adding 48 New Stages Posted by Jennifer Allen on July 29th, 2014 [ permalink ] Universal App - Designed for iPhone and iPad | Read more »
Sharknado: The Video Game Available Now....
Sharknado: The Video Game Available Now. Seriously. Posted by Rob Rich on July 29th, 2014 [ permalink ] Universal App - Designed for iPhone and iPad | Read more »
Frog Orbs 2 Review
Frog Orbs 2 Review By Nadia Oxford on July 29th, 2014 Our Rating: :: THIS MAGIC IS A TAD MONOTONOUS Universal App - Designed for iPhone and iPad Frog Orbs 2 is repetitive, but younger players should enjoy it nonetheless.   | Read more »
Puzzix Review
Puzzix Review By Jennifer Allen on July 29th, 2014 Our Rating: :: NICE IDEAUniversal App - Designed for iPhone and iPad A little like Tetris, Puzzix is all about piecing together blocks and watching them vanish. It could do with... | Read more »
Cannonball eMail is Now Live – Works Wit...
Cannonball eMail is Now Live – Works With Gmail, Yahoo, Outlook, Hotmail, and AOL Posted by Jessica Fisher on July 29th, 2014 [ permalink ] | Read more »
To The End Review
To The End Review By Lee Hamlet on July 29th, 2014 Our Rating: :: A VICIOUS CYCLEUniversal App - Designed for iPhone and iPad To The End will test players’ patience, timing, and dedication as they try to navigate all 13 levels in... | Read more »

Price Scanner via MacPrices.net

Up to $250 price drop on leftover 15-inch Mac...
B&H Photo has dropped prices on 2013 15″ Retina MacBook Pros by as much as $250 off original MSRP. Shipping is free, and B&H charges NY sales tax only: - 15″ 2.3GHz Retina MacBook Pro: $2349... Read more
Updated MacBook Pro Price Trackers
We’ve updated our MacBook Pro Price Trackers with the latest information on prices, bundles, and availability on the new 2014 models from Apple’s authorized internet/catalog resellers as well as... Read more
Apple updates MacBook Pros with slightly fast...
Apple updated 13″ and 15″ Retina MacBook Pros today with slightly faster Haswell processors. 13″ models now ship with 8GB of RAM standard, while 15″ MacBook Pros ship with 16GB across the board. Most... Read more
Apple drops price on 13″ 2.5GHz MacBook Pro b...
The Apple Store has dropped their price for the 13″ 2.5GHz MacBook Pro by $100 to $1099 including free shipping. Read more
Apple drops prices on refurbished 2013 MacBoo...
The Apple Store has dropped prices on Apple Certified Refurbished 13″ and 15″ 2013 MacBook Pros, with model now available starting at $929. Apple’s one-year warranty is standard, and shipping is free... Read more
iOS 8 and OS X 10.10 To Support DuckDuckGo As...
Writing for Quartz, Dan Frommer reports that Apple’s forthcoming iOS 8 and OS X 10.10 operating systems version updates will allow users to select DuckDuckGo as their default search engine. He notes... Read more
U.K. Hospital Using iPods and iPads To Record...
British news journal GazetteLive’s. Ian McNeal notes that the old “an apple a day keeps the doctor away” proverb is being turned on its head at http://southtees.nhs.uk/hospitals/james-cook/ James... Read more
13-inch 2.5GHz MacBook Pro on sale for $1099,...
Best Buy has the 13″ 2.5GHz MacBook Pro available for $1099.99 on their online store. Choose free shipping or free instant local store pickup (if available). Their price is $100 off MSRP. Price is... Read more
Roundup of Apple refurbished MacBook Pros, th...
The Apple Store has Apple Certified Refurbished 13″ and 15″ MacBook Pros available for up to $400 off the cost of new models. Apple’s one-year warranty is standard, and shipping is free. Their prices... Read more
Record Mac Shipments In Q2/14 Confound Analys...
A Seeking Alpha Trefis commentary notes that Apple’s fiscal Q3 2014 results released July 22, beat market predictions on earnings, although revenues were slightly lower than anticipated. Apple’s Mac’... Read more

Jobs Board

Sr Software Lead Engineer, *Apple* Online S...
Sr Software Lead Engineer, Apple Online Store Publishing Systems Keywords: Company: Apple Job Code: E3PCAK8MgYYkw Location (City or ZIP): Santa Clara Status: Full 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
Sr. Product Leader, *Apple* Store Apps - Ap...
**Job Summary** Imagine what you could do here. At Apple , great ideas have a way of becoming great products, services, and customer experiences very quickly. Bring 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* 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
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.