Programmer’s Challenge

By Bob Boonstra

Byte Code Interpreter

September is Assembly Language month at the Programmer’s Challenge, and this year we will be accepting solutions in PowerPC Assembly for the first time. This month’s Challenge, suggested by Xan Gregg, is to write an interpreter for a subset of the byte code language used by the Java Virtual Machine.

The prototype for the code you should write is:

void JavaMiniVM(
 void *constant_pool,/* pointer to cp_info array */
 void *fields,   /* pointer to field_info array */
 void *methods,  /* pointer to method_info array */
 void *classFile,/* pointer to class file */
 long methodToExecute,  /* index of method to start executing */
 void *heapSpace,/* preallocated storage for your use */
 void *returnStack /* stack where return values are stored */
);

Your Challenge is to write an efficient interpreter for a subset of the Java byte code instruction set. A Java instruction consists of a single-byte opcode specifying the operation to be performed, followed by zero or more operand bytes. So, for example, in the byte sequence 0x10 0xFF, the opcode 0x10 (bipush) indicates that the operand byte 0xFF is to be pushed onto the operand stack. The instruction 0x60 (iadd) indicates that two integers are to be popped off the operand stack, added, and the result pushed back onto the stack. The virtual machine operates by repeatedly fetching an opcode and performing the indicated action on the operands.

To participate in this Challenge, you don’t need to know anything about Java itself, but you do need to understand the Java Virtual Machine. A Java Virtual Machine executes a .class file, the format of which is too complicated to provide here; it is described in the Java Virtual Machine Specification (release 1.0 Beta) available at http://java.sun.com/java.sun.com/newdocs.html.

The first three parameters passed to your JavaMiniVM routine are pointers to the constants, fields, and methods contained in the .class file that your interpreter is to execute. These parameters are taken directly from the classFile described in Section 2 of the VM specification. A pointer to the classFile is provided as the fourth parameter for those who feel they need direct access to the .class file. The parameter methodToExecute indicates which of the methods your VM is to start executing.

Stack space and execution frames should be established by your virtual machine in the memory provided in heapSpace. Adequate heap space will be allocated by the caller. Your code may include static data that might be needed for lookup tables, etc., to efficiently implement the virtual machine. The parameter returnStack is provided as the stack for the execution environment of the calling routine. It is to be used when executing the various return byte codes to provide the caller access to your results.

To simplify the Challenge, your code need not implement the long, float, and double data types supported by the Java Virtual Machine. You also do not need to process exceptions, breakpoints, monitored code regions, or the wide modifier for Load and Store instructions. Your interpreter should be robust enough to determine the operand size of these unimplemented instructions in order to skip any that are encountered. All methods invoked will be in the single .class file provided to your routine.

Sample test .class files will be provided via the Programmer’s Challenge mailing list, and are also available by writing me at bob_boonstra@mactech.com. If there are any questions about what needs to be implemented, please send me a note at the same email address.

Your code may be written in PowerPC Assembly, 68K Assembly, C, or C++. Testing will be performed on an 8500 using the latest CodeWarrior environment. Because this is a more difficult Challenge than usual, it has been sent to the mailing list earlier than normal to provide additional solution time. For those of you who haven’t had a chance to investigate Java in detail, it is a good opportunity to find out what all the excitement (hype?) is about. I hope you find this Challenge enjoyable and educational.

Two Months Ago Winner

Once again, congratulations go to Ernst Munter (Kanata, Ontario), this time for submitting the fastest entry to the Connect IV Challenge. Recall that the Challenge was to compete in a round-robin tournament against the other solutions in a generalized version of the well-known Connect 4 game. Pieces are inserted into the top of a column in the vertically oriented board, with the winner being the first player to arrange four or more pieces into a vertical, horizontal, or diagonal line.

Of the five entries I received, four worked completely or nearly correctly, although two of these occasionally forfeited a game by making an illegal move or incorrectly claiming victory. The two solutions winning the most tournament points required more execution time than the others, with the winning solution requiring the greatest amount of time for all but the largest board sizes. The winning solution uses a data structure dubbed a quad to denote each possible line of four pieces passing through a given point on the board, and keeps track of whether each quad represents a possible win for either player. Comments in the solution describe heuristics used to prune the recursive search for the best move.

Four test cases were used, consisting of different board sizes. Each solution competed twice against each other solution, playing once with the first move and once with the second move. The table below indicates how many points were earned by each entry for each of the board sizes:

The table below summarizes the results for each entry, including tournament points, code size, data size, and execution time. Numbers in parentheses after a person’s name indicate that person’s cumulative point total for all previous Challenges, not including this one.

Top Twenty Contestants

Here are the top twenty contestants for the Programmer’s Challenge. The numbers below include points awarded over the twenty-four most recent contests, including points earned by this month’s entrants.

There are three ways to earn points: (1) scoring in the top five 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 5th place 2 points

2nd place 10 points finding bug 2 points

3rd place 7 points suggesting Challenge 2 points

4th place 4 points

Here is Ernst’s winning solution:

ConnectMove.cp

Copyright © 1996 Ernst Munter

/*
    “Connect IV”

    The challenge is to write code for a well-known game that will compete against 
    other entries, as well as against the clock.  The game board consists of an NxM 
    array into which two players alternate inserting pieces. Pieces are inserted into the 
    top of a column in the vertically oriented board, so that they drop into the lowest 
    unoccupied cell of that column. The objective is to be the first player to arrange 4 
    or more pieces into a vertical, horizontal, or diagonal line.

Solution
--------
    My solution is based on an unsophisticated look-ahead scheme.  We search, depth 
    first, up to a maximum depth, to find the move which will give the highest board 
    score. Dummy moves are executed alternatingly by the 2 players, in a recursive 
    function.

    At each recursion level, the board score accumulated at the deeper levels is 
    subtracted from the value of the move contemplated at this level.

    In a full look-ahead to depth N, and with a board width of
    C columns, we would have C^N moves to examine.

    Two techniques are combined to reduce the number of moves to be examined:

    At each level, the search can stop if a certain threshold is exceeded or a winning 
    (losing) position is reached. Exceeding the threshold would mean that the calling 
    level could not gain a better score, given its best score to this point.

    In order to be able to stop searching (prune the tree), we would like to start with 
    moves which give the better scores, i.e. rather than go from left to right across
    the board, we start at the position of the last move and go alternatingly left and 
    right of that point. This tackles the active area of the board first where it is more 
    likely to find the best move.

Data Representation
-------------------
    The scoring relies entirely on a simple representation of the state of the board.

    The board is visualized as covered with potential lines (horizontal, vertical, 
    diagonal) of 4 adjacent fields.  Each such line is called a “quad”.

    A given field is associated with at least 3 (corner fields)
    and at most 16 such quads (in the center of a large board).

    Each quad can have a state (empty, owned by player 1, owned by player 2, or 
    spoiled). The spoiled state implies this quad contains pieces from both players, and 
    can no longer be a winning quad.

    In addition, a non-empty quad has a value, depending on how many player pieces it 
    contains.

    I have arbitrarily set these values as follows:

    empty 0
    1 piece                   1
    2 pieces   16
    3 pieces   256
    4 pieces   4096

    The value of a placing a piece in a given field, is calculated as the sum of the values 
    of all quads associated with this field.

    To simplify the book keeping, each field has an associated data structure which 
    points to all relevant quads.

    The Field structure also provides local stack space to hold the previous values of its 
    quads while a move is explored.

    A recognized weakness of this approach is that it treats all quads equally, and does 
    not recognize gravity, that is the need to fill columns from the bottom. This effect
    can shadow otherwise good candidates from ever winning. I had no time left to 
    include this consideration in the board scoring.

Running Time
------------
    The depth of the tree dramatically affects the time to compute a move, as does the 
    width of the board.

    A few minor techniques are used to improve running time.

    After each move, all spoiled quads are removed from their field references.

    All full columns are excluded from the move list.

    Empty columns “far away” from the action are also excluded.

    The MAGIC_NR constant can be used to adjust the speed of the program. A higher 
    value increases the search depth and the running time. 
    
    I set MAGIC_NR to 17 for acceptable all-round performance on my computer.

Assumptions
-----------
    At least 7 columns are assumed.
    The calling program should check for wins;
    it is assumed that this function is not called
    if the opponent has already won.

    A move value of -1 is returned when errors are detected, e.g when there are no free 
    fields left.

    This program does not include a randomizer since it is assumed it will play only a 
    few times against computer opponents who, we hope will not be able to take 
    advantage of this.

    In a version to be played by humans, one would randomly choose between equally 
    good moves to make it more interesting.

Note on style
-------------
    This program is basically a C program in spirit, but using C++ structs for 
    convenience in accessing dynamic data.

    No inheritance, operator overloading or the like.

    All simple functions are listed inline, as part of the class. The implementations of 
    functions with loops are listed separately, following the struct declaration.
*/

#include <stdlib.h>
#include "viervier.h"

#define maxRow 63
#define maxCol 64

#define maxQuad (((maxRow-3)*maxCol)+\
 ((maxCol-3)*maxRow)+(maxRow-3)*(maxCol-3)*2)
#define empty    0
#define self1
#define opponent 2
#define spoiled  3

#define OTHER_PLAYER (3-player)
#define WIN 4096
#define MAX_MOVES9

#define MAGIC_NR 17

Quad
struct Quad {
 short  status;  //who owns quad
 short  value;   //16 ^ (n-1);

 int  Update(int currentPlayer){
 if (status==empty) {
 status=(short)currentPlayer;
 value=1;
 return value;
 }
 if (status==currentPlayer) {
 value <<= 4;    //higher value
 return value;
 }
 if (status != spoiled) { //other player
 status=spoiled;
 return value;   //plus for us
 }
 return 0;//already spoiled
 }
};
typedef struct Quad Quad;

Field 
struct Field {
 Quad* quadRef[16];//pointers to intersecting quads
 Quad savedState[16];//stack to save quads before move

 void AddQuad(Quad* qp);
 void SaveState();
 void RestoreState();
 int  MakeMove(int currentPlayer);
 void Rationalize();
 int  IsEmpty(){
 if (quadRef[0]->status) return 0;
 return 1;
 }
};
typedef struct Field Field;

Field::AddQuad
void Field::AddQuad(Quad* qp) {    //adds qp to list of quads
int k;
 for (k=0;k<16;k++) {
 if (0==quadRef[k]) {
 quadRef[k]=qp;
 break;
 }
 }
}

Field::SaveState
void Field::SaveState() { //save all quads on stack
Quad* qp;
Quad**  qh=quadRef;
Quad* savePtr=savedState;
intk;
 for (k=0;k<16;k++) {
 if (0 == (qp=*qh++)) break;
 *savePtr++=*qp;
 }
}

Field::RestoreState
void Field::RestoreState() {//restore quads from stack
Quad* qp;
Quad**  qh=quadRef;
Quad* savePtr=savedState;
intk;
 for (k=0;k<16;k++) {
 if (0 == (qp=*qh++)) break;
 *qp=*savePtr++;
 }
}

Field::MakeMove
int Field::MakeMove(int currentPlayer) {
long  sum=0;
long  val;
Quad* qp;
Quad**  qh=quadRef;//move=update all quads
    //return value of move
intk;
 for (k=0;k<16;k++) {
 if (0 == (qp=*qh++)) break;
 val=qp->Update(currentPlayer);
 if (val>=WIN) {
 return WIN;
 }
 sum+=val;
 }
 return sum;
}

Field::Rationalize
void  Field::Rationalize() {
inti=0;
intk;
intnq=0;//remove all spoiled quads

//find number of non-0 quad refs
 for (k=0;k<16;k++) {
 if (quadRef[nq]) nq++;
 else break;
 }

//scan quad refs for spoiled quads, and remove
 while(i<nq) {
 Quad* qp=quadRef[i];
 if (qp->status==spoiled) {
 nq--;
 if (i<nq) quadRef[i]=quadRef[nq];
 quadRef[nq]=0;
 }
 i++;
 }
}

PrivateData 
struct PrivateData {
 int  nextMove;  //next real move to do
 int  numCols;   //number of columns
 int  numRows;   //number of rows
 int  numFree;   //number of fields free
 int  level;//recursion depth
 int  numMoves;  //number of moves in move list
 Field* endOfBoard;//sentinel pointer
 int  numHistory;//move counter
 int  history[maxCol*maxRow]; //move history
 int  moveList[maxCol];   //list of columns
 Field* nextField[maxCol];//next free field in column
 Field  board[maxCol*maxRow]; //array of all fields
 Quad quadSet[maxQuad];   //array of all quads

 void Initialize(long nCols,long nRows);
 void FirstMove() {nextMove = numCols >> 1;}
 void MakeMoveList(int move);
 int  BestMove(int level,int player,int threshold);
 void Rationalize(int move);
 int  CannedMove();
 void RecordMove(int move) {
 if (numHistory==0)
 history[numHistory++]=move;
 else history[numHistory++]=move-history[0];
 }
 void AdjustLevel() {
 level=MAGIC_NR - numMoves;
 if (numMoves<=7) level--;
 if (level>=numFree) level=numFree-1;
 }
 int  UpdateBoard(int move,int player) {
 Field* fp=nextField[move];
 long score=fp->MakeMove(player);
 nextField[move]=fp+numCols;
 Rationalize(move);
 numFree--;
 return score;
 }
};
typedef struct PrivateData PrivateData;

/*
field numbering example (6-by-7)

35             36 37  38         39 40  41               5           |
                        |
28             29 30  31         32 33  34               4           |
                        r
21             22 23  24         25 26  27               3           o
                        w
14             15 16  17         18 19  20               2           s
                        |
7        8           9           10  11         12 13  1    |
                        |
0        1           2           3           4           5           6           0           |
    -- columns --
*/

PrivateData::Initialize
void PrivateData::Initialize(long nCols,long nRows){
intcol,row;
Field*  field;
Quad*   qp;

 numCols=nCols;
 numRows=nRows;
 numFree = nCols*nRows;

 endOfBoard=board+numFree;

 field=board;
 for (col=0;col<nCols;col++)
 nextField[col]=field++;

 field=board;
 qp=quadSet;
 for (row=0;row<nRows;row++) {//set up quad references
 for (col=0;col<nCols;col++) {
 int direction,delta;
 for (direction=0;direction<4;direction++) {
 //right, up-right, up, up-left

 switch (direction) {
 //eliminate all that don’t fit
case 0: if (col>=nCols-3) continue;break;
case 1: if (col>=nCols-3) continue;
case 2: if (row>=nRows-3) continue;break;
case 3: if ((row>=nRows-3) || (col<3)) continue;
 }

 for (delta=0;delta<4;delta++) {
 Field* fp;
 switch (direction) {
case 0: fp=field+row*nCols+(col+delta);break;
case 1: fp=field+(row+delta)*nCols+(col+delta);break;
case 2: fp=field+(row+delta)*nCols+col;break;
case 3: fp=field+(row+delta)*numCols+(col-delta);break;
 }
 fp->AddQuad(qp);
 }
 qp++;
 }
 }
 }
}

PrivateData::Rationalize
void  PrivateData::Rationalize(int move) {

//remove spoiled quads from all free fields in the vicinity of a recent move

int i=move-3,j=move+4;
 if (i<0) i=0;
 if (j>numCols) j=numCols;
 for (;i<j;i++) {
 Field* fp=nextField[i];
 while (fp<endOfBoard) {
 fp->Rationalize();
 fp+=numCols;
 }
 }
}

PrivateData::MakeMoveList
void PrivateData::MakeMoveList(int move) {
intm=move;
intn=0;
intk=0;

//build the move sequence, starting from the center
//out to the limits while skipping full columns.

 do {
 if (nextField[m]<endOfBoard) moveList[n++]=m;
 if (n>=MAX_MOVES) goto done;
 k++;
 if (0>(m=m-k)) goto go_right;
 if (nextField[m]<endOfBoard) moveList[n++]=m;
 if (n>=MAX_MOVES) goto done;
 k++;
 if (numCols<=(m=m+k)) goto go_left;
 } while(1);

go_left:
 if (0>(m=m-k-1)) goto done;
 do {
 if (nextField[m]<endOfBoard) moveList[n++]=m;
 if (n>=MAX_MOVES) goto done;
 m--;
 } while(m>=0);
 goto done;

go_right:
 if (numCols<=(m=m+k+1)) goto done;
 do {
 if (nextField[m]<endOfBoard) moveList[n++]=m;
 if (n>=MAX_MOVES) goto done;
 m++;
 } while(m<numCols);

done:
 numMoves=n;
}

PrivateData::CannedMove
int PrivateData::CannedMove() {
#define H0 (history[0])
 switch (numHistory) {
case 1: if (H0>=3) return H0;
 if (H0+3<numCols) return H0;
 return numCols/2;
case 2: switch (history[1]) {
 case 0:return H0;
 case 1:if (H0>=3) return H0-3; else return H0;
 case -1:if (numCols-H0>3) return H0+3; else return H0;
 case 2:case -2:return H0;
 case 3:if (H0>=1) return H0-1; else return H0-1;
 case -3:if (numCols-H0>1) return H0+1; else return H0+1;
 default:if (H0>=2) return H0-1; else return H0+3;
 }
case 3: if (history[1]==0) {
 if (history[2]>=0) return H0-1;
 if (history[2]<0) {
 if (H0+1<numCols) return H0+1;
 }
 }
 }
 return -1;
}

PrivateData::BestMove
int PrivateData::BestMove(
 int level,int player,int threshold) {
inti;
intbestMove=-1;
intmoveValue;
intscore;
intbestV=-0x4000L;

//this routine is called recursively to return the value of the best move. The class //variable “nextMove” holds 
the column number for the “best” move.

 for (i=0;i<numMoves;i++) {
 int m=moveList[i];//work from list
 Field* fp=nextField[m];
 if (fp < endOfBoard) {   //else column is full
 fp->SaveState();
 nextField[m]+=numCols;
 moveValue = fp->MakeMove(player);

 if (moveValue>=WIN) {    //win here: return right away
 nextField[m]=fp;
 fp->RestoreState();
 nextMove=m;
 return WIN*2;
 }

 if (level) {    //descend to next level

 score=BestMove(level-1,OTHER_PLAYER,moveValue-bestV);
 if (score>=WIN) {
 moveValue=-score+1024;   //bias for depth
 goto skip;
 }
 moveValue -= score; //and accumulate score
 }

 if (moveValue>=threshold) {
 //no need to search further
 nextField[m]=fp;
 fp->RestoreState();
 nextMove=m;
 return moveValue;
 }
skip:
 if (moveValue>bestV) {   //keep track of best so far
 bestV=moveValue;
 bestMove=m;
 }

 nextField[m]=fp;
 fp->RestoreState();
 }
 }
 nextMove=bestMove;
 return bestV;
}

ConnectMove
long ConnectMove (
 long numCols,
 long numRows,
 void *privStorage,
 long prevMove,
 Boolean newGame,
 Boolean *victory) {

PrivateData* PD=(PrivateData*)privStorage;

 if (newGame) {  //initialize on first call
 PD->Initialize(numCols,numRows);
 if (prevMove==-1) {
 PD->FirstMove();//standard first move
 goto finish;
 }
 }


 PD->UpdateBoard(prevMove,2);
 PD->RecordMove(prevMove);

 if (PD->numFree<=0) return -1;    //the board is full

 if ((PD->nextMove=PD->CannedMove())<0) {

 PD->MakeMoveList(prevMove);

 PD->AdjustLevel();

 PD->BestMove(PD->level,1,WIN);
 }
finish:
 *victory=(WIN<=PD->UpdateBoard(PD->nextMove,1));
 PD->RecordMove(PD->nextMove);
 return PD->nextMove;
}