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

TextSoap 8.4.1 - Automate tedious text d...
TextSoap can automatically remove unwanted characters, fix up messed up carriage returns, and do pretty much anything else that we can think of to text. Save time and effort. Be more productive. Stop... Read more
TextSoap 8.4.1 - Automate tedious text d...
TextSoap can automatically remove unwanted characters, fix up messed up carriage returns, and do pretty much anything else that we can think of to text. Save time and effort. Be more productive. Stop... Read more
Backblaze 4.3.0.44 - Online backup servi...
Backblaze is an online backup service designed from the ground-up for the Mac. With unlimited storage available for $5 per month, as well as a free 15-day trial, peace of mind is within reach with... Read more
Numi 3.15 - Menu-bar calculator supports...
Numi is a calculator that magically combines calculations with text, and allows you to freely share your computations. Numi combines text editor and calculator Support plain English. For example, '5... Read more
EtreCheck 3.3.3 - For troubleshooting yo...
EtreCheck is an app that displays the important details of your system configuration and allow you to copy that information to the Clipboard. It is meant to be used with Apple Support Communities to... Read more
BusyContacts 1.1.8 - Fast, efficient con...
BusyContacts is a contact manager for OS X that makes creating, finding, and managing contacts faster and more efficient. It brings to contact management the same power, flexibility, and sharing... Read more
TunnelBear 3.0.14 - Subscription-based p...
TunnelBear is a subscription-based virtual private network (VPN) service and companion app, enabling you to browse the internet privately and securely. Features Browse privately - Secure your data... Read more
Apple Final Cut Pro X 10.3.4 - Professio...
Apple Final Cut Pro X is a professional video editing solution.Completely redesigned from the ground up, Final Cut Pro adds extraordinary speed, quality, and flexibility to every part of the post-... Read more
Hopper Disassembler 4.2.1- - Binary disa...
Hopper Disassembler is a binary disassembler, decompiler, and debugger for 32-bit and 64-bit executables. It will let you disassemble any binary you want, and provide you all the information about... Read more
Slack 2.6.2 - Collaborative communicatio...
Slack is a collaborative communication app that simplifies real-time messaging, archiving, and search for modern working teams. Version 2.6.2: Fixed Inexplicably, context menus and spell-check... Read more

Latest Forum Discussions

See All

The best new games we played this week
We were quite busy this week. A bunch of big mobile games launched over the past few days, alongside a few teeny surprises. There're lots of quality games to load your phone with. We've gone and picked out five of our favorites for the week. [... | Read more »
Magikarp Jump beginner's guide
Magikarp Jump is a mystifying little game. Part Tamagotchi, part idle clicker, there's not a whole lot of video game there, per se, but for some reason we can't help coming back to it again and again. Your goal is to train up a little Magikarp to... | Read more »
Goat Simulator PAYDAY (Games)
Goat Simulator PAYDAY 1.0 Device: iOS Universal Category: Games Price: $4.99, Version: 1.0 (iTunes) Description: ** IMPORTANT - SUPPORTED DEVICES **iPhone 4S, iPad 2, iPod Touch 5 or better Goat Simulator: Payday is the most... | Read more »
GRID Autosport delayed until autumn
Sorry mobile racing fans -- GRID Autosport has been delayed a few months. The game is now expected to launch this fall on iOS. Feral Interactive announced that they wanted more time to work on the game's UI and overall performance before launching... | Read more »
Zombie Gunship Survival Beginner's...
The much anticipated Zombie Gunship Survival is here. In this latest entry in the Zombie Gunship franchise, you're tasked with supporting ground troops and protecting your base from the zombie horde. There's a lot of rich base building fun, and... | Read more »
Mordheim: Warband Skirmish (Games)
Mordheim: Warband Skirmish 1.2.2 Device: iOS Universal Category: Games Price: $3.99, Version: 1.2.2 (iTunes) Description: Explore the ruins of the City of Mordheim, clash with other scavenging warbands and collect Wyrdstone -... | Read more »
Mordheim: Warband Skirmish brings tablet...
Legendary Games has just launched Mordheim: Warband Skirmish, a new turn-based action game for iOS and Android. | Read more »
Magikarp Jump splashes onto Android worl...
If you're tired ofPokémon GObut still want something to satisfy your mobilePokémon fix,Magikarp Jumpmay just do the trick. It's out now on Android devices the world over. While it looks like a simple arcade jumper, there's quite a bit more to it... | Read more »
Purrfectly charming open-world RPG Cat Q...
Cat Quest, an expansive open-world RPG from former Koei-Tecmo developers, got a new gameplay trailer today. The video showcases the combat and exploration features of this feline-themed RPG. Cat puns abound as you travel across a large map in a... | Read more »
Jaipur: A Card Game of Duels (Games)
Jaipur: A Card Game of Duels 1.0 Device: iOS Universal Category: Games Price: $1.99, Version: 1.0 (iTunes) Description: ** WARNING: iPad 2, iPad Mini 1 & iPhone 4S are NOT compatible. ** *** Special Launch Price for a limited... | Read more »

Price Scanner via MacPrices.net

Memorial Day savings: 13-inch Touch Bar MacBo...
B&H Photo has the 2016 Apple 13″ Touch Bar MacBook Pros in stock today and on sale for up to $150 off MSRP. Shipping is free, and B&H charges NY & NJ sales tax only: - 13″ 2.9GHz/512GB... Read more
Apple refurbished 13-inch MacBook Airs availa...
Apple has Certified Refurbished 2016 13″ MacBook Airs available starting at $849. An Apple one-year warranty is included with each MacBook, and shipping is free: - 13″ 1.6GHz/8GB/128GB MacBook Air: $... Read more
Apple restocks refurbished 11-inch MacBook Ai...
Apple has Certified Refurbished 11″ MacBook Airs (the latest models recently discontinued by Apple), available for up to $170 off original MSRP. An Apple one-year warranty is included with each... Read more
12-inch 1.2GHz Retina MacBooks on sale for up...
B&H has 12″ 1.2GHz Retina MacBooks on sale for up to $150 off MSRP. Shipping is free, and B&H charges NY & NJ sales tax only: - 12″ 1.2GHz Space Gray Retina MacBook: $1449.99 $150 off... Read more
15-inch 2.7GHz Silver Touch Bar MacBook Pro o...
MacMall has the 15-inch 2.7GHz Silver Touch Bar MacBook Pro (MLW82LL/A) on sale for $2569 as part of their Memorial Day sale. Shipping is free. Their price is $230 off MSRP. Read more
Free Tread Wisely Mobile App Endorsed By Fath...
Just in time for the summer driving season, Cooper Tire & Rubber Company has announced the launch of a new Tread Wisely mobile app. Designed to promote tire and vehicle safety among teens and... Read more
Commercial Notebooks And Detachable Tablets W...
Worldwide shipments of personal computing devices (PCDs), comprised of traditional PCs (a combination of desktop, notebook, and workstations) and tablets (slates and detachables), are forecast to... Read more
Best value this Memorial Day weekend: Touch B...
Apple has Certified Refurbished 2016 15″ and 13″ MacBook Pros available for $230 to $420 off original MSRP. An Apple one-year warranty is included with each model, and shipping is free: - 15″ 2.6GHz... Read more
13-inch MacBook Airs on sale for up to $130 o...
Overstock.com has 13″ MacBook Airs on sale for up to $130 off MSRP including free shipping: - 13″ 1.6GHz/128GB MacBook Air (sku MMGF2LL/A): $869.99 $130 off MSRP - 13″ 1.6GHz/256GB MacBook Air (sku... Read more
2.8GHz Mac mini available for $973 with free...
Adorama has the 2.8GHz Mac mini available for $973, $16 off MSRP, including a free copy of Apple’s 3-Year AppleCare Protection Plan. Shipping is free, and Adorama charges sales tax in NY & NJ... Read more

Jobs Board

*Apple* Media Products - Commerce Engineerin...
Apple Media Products - Commerce Engineering Manager Job Number: 57037480 Santa Clara Valley, California, United States Posted: Apr. 18, 2017 Weekly Hours: 40.00 Job Read more
Best Buy *Apple* Computing Master - Best Bu...
**509643BR** **Job Title:** Best Buy Apple Computing Master **Location Number:** 001482- Apple Valley-Store **Job Description:** **What does a Best Buy Apple Read more
*Apple* Media Products - Commerce Engineerin...
Apple Media Products - Commerce Engineering Manager Job Number: 57037480 Santa Clara Valley, California, United States Posted: Apr. 18, 2017 Weekly Hours: 40.00 Job Read more
*Apple* Mac and Mobility Engineer - Infogrou...
Title: Apple Mac and Mobility Engineer Location: Portland, OR Area Type: 12 month contract Job: 17412 Here's a chance to take your skills to the limit, learn new Read more
*Apple* Retail - Multiple Positions, White P...
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.