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


 

Community Search:
MacTech Search:

Software Updates via MacUpdate

OmniOutliner Pro 4.2 - Pro version of th...
OmniOutliner Pro is a flexible program for creating, collecting, and organizing information. Give your creativity a kick start by using an application that's actually designed to help you think. It's... Read more
VLC Media Player 2.2.1 - 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
Nisus Writer Pro 2.1.1 - Multilingual wo...
Nisus Writer Pro is a powerful multilingual word processor, similar to its entry level products, but brings new features such as table of contents, indexing, bookmarks, widow and orphan control,... Read more
Tinderbox 6.2.0 - Store and organize you...
Tinderbox is a personal content management assistant. It stores your notes, ideas, and plans. It can help you organize and understand them. And Tinderbox helps you share ideas through Web journals... Read more
OmniOutliner 4.2 - Organize your ideas,...
OmniOutliner is a flexible program for creating, collecting, and organizing information. Give your creativity a kick start by using an application that's actually designed to help you think. It's... Read more
Things 2.5.4 - Elegant personal task man...
Things is a task management solution that helps to organize your tasks in an elegant and intuitive way. Things combines powerful features with simplicity through the use of tags and its intelligent... Read more
NeoOffice 2014.10 - Mac-tailored, OpenOf...
NeoOffice is a complete office suite for OS X. With NeoOffice, users can view, edit, and save OpenOffice documents, PDF files, and most Microsoft Word, Excel, and PowerPoint documents. NeoOffice 3.x... Read more
iPhoto Library Manager 4.2 - Manage mult...
iPhoto Library Manager allows you to organize your photos among multiple iPhoto libraries, rather than having to store all of your photos in one giant library. You can browse the photos in all your... Read more
Web Snapper 3.3.8 - Capture entire Web p...
Web Snapper lets you capture Web pages exactly as they appear in your browser. You can send them to a file as images or vector-based, multi-page PDFs. It captures the whole Web page - eliminating the... Read more
TeamViewer 10.0.41404 - 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

The Apple Watch Could Revolutionize the...
It’s not here yet but there’s that developing sneaky feeling that the Apple Watch, despite its price tag and low battery life, might yet change quite a lot about how we conduct our lives. While I don’t think it’s going to be an overnight... | Read more »
Mad Skills Motocross 2 Version 2.0 is He...
Mad Skills Motocross 2 fans got some good news this week as Turborilla has given the game its biggest update yet. Now you'll have access to Versus mode where you can compete against your friends in timed challenges. Turborilla has implemented a... | Read more »
Kids Can Practice Healthy Living With Gr...
Bobaka is releasing a new interactive book called Green Riding Hood  in May. The app teaches kids about yoga and organic style of life through mini-games and a fun take on the classic Little Red Riding Hood fairy tale. | Read more »
Chainsaw Warrior: Lords of the Night has...
It's time to put the Darkness back in its place now that Chainsaw Warrior: Lords of the Night has officially made it to iOS. | Read more »
A World of Ice and Fire Lets You Stalk 2...
George R. R. Martin’s A World of Ice and Fire, by Random House, is a mobile guide to the epic series. The new update gives you the Journeys map feture that will let you track the movements of 25 different characters. But don't worry, you can protect... | Read more »
Gameloft Announces Battle Odyssey, a New...
Battle Odyssey, Gameloft's newest puzzle RPG, is coming to the App Store next week. Set in the world of Pondera, you will need to control the power of the elements to defend the world from evil. You'll be able to entlist over 500 allies to aid you... | Read more »
Here's How You Can Get 5 Free Pro D...
It's only been a couple of days since Gamevil released MLB Perfect Inning 15, so building up a decent roster could still take a little time. If you'd like to speed things up a bit, then we've got a deal for you. How does five free Pro drafts sound?... | Read more »
Fusion - HDR Camera (Photography)
Fusion - HDR Camera 1.0.0 Device: iOS Universal Category: Photography Price: $1.99, Version: 1.0.0 (iTunes) Description: Fusion creates HDR (high dynamic range) photos by capturing different exposures and then combining them into one... | Read more »
Sago Mini Toolbox (Education)
Sago Mini Toolbox 1.1 Device: iOS Universal Category: Education Price: $2.99, Version: 1.1 (iTunes) Description: Come build with the Sago Mini friends! Use a wrench, try a saw, or hammer some nails. From sewing hand puppets to... | Read more »
You Should Probably Grab Hitman GO While...
Hitman GO is a surprisingly cool (yet also incredibly drastic) departure from the Hitman series. It's well worth playing for any puzzle game fans out there, and at the moment you can get your hands - or garrotte if you will - on it for a mere $0.99... | Read more »

Price Scanner via MacPrices.net

TigerText Introduces First Secure Enterprise...
TigerText, a provider of secure, real-time messaging for the enterprise, has announced the launch of TigerText for the Apple Watch. TigerText for the Apple Watch enables users to securely send and... Read more
The Conservation Fund Partners with Apple To...
The Conservation Fund has announced that it will partner with Apple to help protect working forests in the United States. The Apple initiative will conserve more than 36,000 acres of working... Read more
Clearance 13-inch 2.6GHz Retina MacBook Pro a...
B&H Photo has clearance 2014 13″ 2.6GHz/128GB Retina MacBook Pros now available for $1099, or $200 off original MSRP. Shipping is free, and B&H charges NY sales tax only. Read more
Apple refurbished 2014 13-inch Retina MacBook...
The Apple Store has Apple Certified Refurbished 2014 13″ Retina MacBook Pros available for up to $400 off original MSRP, starting at $979. An Apple one-year warranty is included with each model, and... Read more
iMacs on sale for up to $205 off MSRP, NY tax...
B&H Photo has 21″ and 27″ iMacs on sale for up to $205 off MSRP including free shipping plus NY sales tax only: - 21″ 1.4GHz iMac: $1019 $80 off - 21″ 2.7GHz iMac: $1189 $110 off - 21″ 2.9GHz... Read more
Sale! 16GB iPhone 5S for $1 with service
Best Buy is offering 16GB iPhone 5Ss for $1.00 with 2-year activation at a participating cellular provider. Choose free home shipping and activation, or buy online and activate during in-store pickup... Read more
Apple refurbished 2014 MacBook Airs available...
The Apple Store has Apple Certified Refurbished 2014 MacBook Airs available starting at $679. An Apple one-year warranty is included with each MacBook, and shipping is free. These are currently the... Read more
27-inch 3.5GHz 5K iMac on sale for $2349, sav...
 Adorama has the 27″ 3.5GHz 5K iMac in stock today and on sale for $2349 including free shipping plus NY & NJ sales tax only. Their price is $150 off MSRP. For a limited time, Adorama will... Read more
Save up to $380 on an iMac with Apple refurbi...
The Apple Store has Apple Certified Refurbished iMacs available for up to $380 off the cost of new models. Apple’s one-year warranty is standard, and shipping is free: - 27″ 3.5GHz 5K iMac – $2119 $... Read more
iFixIt Teardown Awards 12-IInch Retina MacBoo...
iFixIt has posted its illustrated teardown of the new 12-inch MacBook Retina. They note that this new MacBook is less than half the thickness of the last Apple notebook called just “MacBook” back in... Read more

Jobs Board

Sr. Project Engineer, *Apple* Education Pro...
**Job Summary** Apple Professional Services (APS) has an opening for a senior technical position that contributes to Apple 's efforts for strategic and transactional Read more
Event Director, *Apple* Retail Marketing -...
…This senior level position is responsible for leading and imagining the Apple Retail Team's global engagement strategy and team. Delivering an overarching brand 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
Communication Manager - *Apple* Pay - Apple...
**Job Summary** This position works within the Apple Pay Merchant Solutions team to create, as well as oversee the development of, materials for use by Apple Pay Read more
Project Manager / Business Analyst, WW *Appl...
…a senior project manager / business analyst to work within our Worldwide Apple Fulfillment Operations and the Business Process Re-engineering team. This role will work Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.