Nim
Home Page
Work
Sample Code
Word Count
Word Count
Word Count
Remove Tab
Anagram
8 Queen
Permute
Nim
Quicksort
Nim by Harry M. Hardjono
Pseudocode
Pseudocode for Nim
1. Introduction (instructions, init, etc.)
2. While some token still on board.
1. Display board
2. If current PLAYER is human
1. CALL humanmove
3. Else
2. CALL compmove
Note: move is updated within the move subroutine
3. Determine winner and display appropriate messages
1. Human wins
2. Computer wins
4. End Main Subroutine
Note:
All right, I know this isn't the pseudocode discussed in the
class, but I feel this is justified in that it doesn't
display empty board at the end of the game.
Global variables
NX(10) - the playfield. The count of token per row
NROWS - the number of rows in the playfield
PLAYER - current PLAYER - 1 for human
- 0 for computer
Local variables
TLEFT - No. of tokens left. Zero signifies end of game.
WINNER - 1 for human
- 0 for computer
Intro Subroutine
1. Display introductions and rules
2. Determine who goes first
1. Ask "Do you wanna go foist?"
2. If answer (in CHARACTER) starts with "Y" or "y"
1. Human goes first
3. Else Computer goes first
3. Set the board
1. Get number of rows (NROWS) - Error checking point
2. Ask "Do you want me (computer) to set it up?"
3. If answer starts with "Y" or "y"
1. Automatic set-up
1. DO I=1,NROWS
2. NX(I)=NROWS+1-I
3. ENDDO
2. Or manual input.
1. For each row, ask for number of tokens (ntok<=10)
Error checking point
4. End Intro Subroutine
ENDGAME Function
This function will return the number of counters left in the
board. This value will be used to determine the end of the game.
1. Total the numbers in the playfield column (NX()).
2. End ENDGAME
Display Subroutine
This subroutine will display the board to the screen.
1. DO I=1,NROWS
2. WRITE I,' ',('X',J=1,NX(I))
3. ENDDO
4. End Display Subroutine
HumanMove Subroutine
This subroutine will take user input for his moves and update
the board appropriately.
1. Ask for row
1. if out of bounds - Warning - ErrorHandler
2. if no counter - Warning - ErrorHandler
2. Ask for number of counter to be removed (from NX())
1. if 0 or less then no action, back to row input (Step 1)
2. if less than max then subtract
3. if max or more then set counter to zero.
3. End HumanMove Subroutine
Note: It would be nice to show how many counters were taken.
CompMove Subroutine
CompMove will scan the NROWS rows of counters, compute the
binary representation of the rows, determine which
columns of the binary representation results in an
odd sum. If none are odd (STALL=1) a stalling move
is executed. Otherwise (STALL=0), the maximum row
is altered by changing all the columns that contribute
to an odd sum.
1. Convert all decimals (up to nrows) to binary (BIN(10,4))
1. For each row, NUMB=NX(ROW)
1. From power 4 to power 1
1. I=2**(POWR-1)
2. BIN(ROW,POWR)=NUMB/I
3. NUMB=NUMB-(BIN(ROW,POWR)*I)
2. Also find the row containing max num of tokens (MAXRO).
2. Sum all binary columns in BIN(,) to SUM()
3. Determine EVEN-ODDS (ODD(4)) (0 for even, 1 for odd)
1. If no odd bits then
1. Take 1 from row (MAXRO) which has most counters
2. Else continue
4. Find most significant odd sum - yields column number(POWR).
5. Find the appropriate row (ROW)(with 1 in column number (POWR)).
6. Modify the appropriate row
1. Change most significant bit to zero BIN(ROW,POWR)
2. Flip all bits in the odd position in ODD array
1. DO I=POWR,1,-1
2. BIN(ROW,I)=ABS(BIN(ROW,I)-ODD(I))
3. ENDDO
7. Convert binary to decimal
8. End CompMove Subroutine
Note: I know, this isn't your pseudocode. But at least I can
say that it's mine. Also simpler, hopefully, to understand.
It should be equivalent to your code since I have run the
program using your supplied code successfully as well.
Hey, just cut-n-paste!
Local variables used
BIN(10,4) - The binary field, corresponding to the playfield.
The second index refers to power.
1 - least significant
4 - most significant
SUM(4) - The sum for the binary column.
Used to compute Even Odd bits
ODD(4) - The odd array for each power column in binary field
0 - Even
1 - Odd
STALL - 1 - No odd bit in ODD()
0 - otherwise
ROW - Used in BIN(ROW,POWR) or NX(ROW)
POWR - Used in BIN(ROW,POWR)
NUMB - Number, used in decimal-binary conversion
MAXRO - Stalling Row index
ErrorHandler Subroutine
This subroutine will intercept errors and warnings and display
the approprate messages and/or user reaction.
1. Display Errortype
1. Input out of range.
2. Stupid Error#39 (hey, 39 is better than 42!)
3. Otherwise, indeterminant
2. Display Error id
1. Number of row - Init
2. Number of column - Init
3. Row input error - Init
4. No counter
5. Counter input error
6. Otherwise, ErrorHandler error
3. End ErrorHandler
Program Code:
PROGRAM Nim
*****************************************************************
* This program is a game designed to goad people to enjoy
* FORTRAN programming. The game consists of placing any number
* counters (up to ten in this program). Each PLAYER then
* alternately removes any nonzero number of counters from any
* one row. The PLAYER removing the last counter is the winner.
*
* Pseudocode for Nim - main subroutine
* 1. Introduction (instructions, init, etc.)
* 2. While some token still on board.
* 1. Display board
* 2. If current PLAYER is human
* 1. CALL humanmove
* 3. Else
* 2. CALL compmove
* 4. Update move
* 3. Determine winner and display appropriate messages
*
* All right, I know this isn't the pseudocode discussed in the
* class, but I feel this is justified in that it doesn't
* display empty board at the end of the game.
*
*****************************************************************
INTEGER NX,NROWS,PLAYER,TLEFT,WINNER
COMMON /PARAM/NX(10),NROWS,PLAYER
INTEGER ENDGAME
* NX(10) - the playfield. The count of token per row
* NROWS - the number of rows in the playfield
* PLAYER - current PLAYER - 1 for human
* - 0 for computer
* TLEFT - No. of tokens left. Zero signifies end of game.
* WINNER - 1 for human
* - 0 for computer /* Is this really necessary? */
***************************
***** Main Subroutine *****
***************************
* Introduction
*
CALL INTRO
* Start of loop here.
10 CONTINUE
*
* While some token still on board.
*
TLEFT = ENDGAME()
WRITE(*,*)'Counter left = ',TLEFT
IF (TLEFT.LE.0) GOTO 99
*
* Display board
CALL DISPLAY
*
* Determine current PLAYER type
IF (PLAYER.EQ.1) THEN
CALL HUMANMOVE
PLAYER = 0
ELSE
CALL COMPMOVE
PLAYER = 1
ENDIF
*
GOTO 10
*
* 3. Determine winner and display appropriate messages
99 CONTINUE
IF (PLAYER.EQ.0) THEN
* Human wins
WRITE(*,*)'Hrrmmggghhh! You''re just lucky this time!'
WRITE(*,*)'Next time, I will definitely crush you!'
ELSE
* Computer wins
WRITE(*,*)'Arigahto Hohsaimasu! You are a worthy opponent'
WRITE(*,*)'but your skill is still way, way under mine.'
WRITE(*,*)'From now on, you call me Sire!'
ENDIF
STOP
END
***** End Main *****
*
****************************
***** Intro Subroutine *****
*********************************************************************
* This subroutine will do the following:
* 1. Display introductions and rules
* 2. Determine who goes first
* 1. Whether computer or human.
* 3. Set the board
* 1. Select either predetermined.
* 2. Or manual input.
* 1. Ask number of row (nrow<=10)
* 2. For each row, ask for number of tokens (ntok<=10)
*********************************************************************
SUBROUTINE INTRO
INTEGER NX,NROWS,PLAYER
COMMON /PARAM/NX(10),NROWS,PLAYER
INTEGER I,J
CHARACTER*20 TSTR
*
* Display introductions and rules
WRITE(*,*)'The game of Nim - programmed by Harry M. Hardjono'
WRITE(*,*)'Welcome, oh, welcome to the fascinating game of'
WRITE(*,*)'Nim. You are about to be engaged in a game so'
WRITE(*,*)'popular that it has been played since the very'
WRITE(*,*)'ancient times. Who knows? Maybe Pharaohs might'
WRITE(*,*)'be playing the same game as we! So, relax and be'
WRITE(*,*)'prepared to be humiliated, for I am the master'
WRITE(*,*)'PLAYER of Nim! (In fact, if I lose, you can call'
WRITE(*,*)'Meinser.)'
WRITE(*,*)
WRITE(*,*)'Rules of game:'
WRITE(*,*)'The game consists of placing any number'
WRITE(*,*)'counters (up to ten in this program).'
WRITE(*,*)'You and I will then alternately remove any '
WRITE(*,*)'number from 1 to 10 from any ONE row.'
WRITE(*,*)'The player removing the last counter is the'
WRITE(*,*)'winner.'
WRITE(*,*)
WRITE(*,*)'Why don''t you read that for a while?'
PAUSE
DO 10 I=1,24
WRITE(*,*)
10 CONTINUE
* Determine who goes first
WRITE(*,*)'This is a two players game.'
WRITE(*,*)'Do you want to go first (Y/N)'
READ(*,'(A)')TSTR
IF (TSTR(1:1).EQ.'y' .OR. TSTR(1:1).EQ.'Y') THEN
* Human player goesth first
WRITE(*,*)'Fine, thou shall go first'
PLAYER = 1
ELSE
* Computer goes first, yippeee!
WRITE(*,*)'Ha ha ha ha! Do you think you have a chance'
WRITE(*,*)'when I go first?'
PLAYER = 0
ENDIF
*
* Set the board
20 WRITE(*,*)'How many rows (1 to 10) shall the board have, Sire?'
READ(*,*)NROWS
IF (NROWS.LT.1 .OR. NROWS.GT.10) THEN
CALL ERRORHANDLER(1,1)
GOTO 20
ENDIF
*
* Select board construction
WRITE(*,*)'Do you want me to set it up for you?'
READ(*,'(A)')TSTR
IF (TSTR(1:1).EQ.'y' .OR. TSTR(1:1).EQ.'Y') THEN
* Predetermined.
DO 30 I=1,NROWS
NX(I)=NROWS+1-I
30 CONTINUE
ELSE
* Manual input
* For each row, ask for number of tokens (ntok<=10)
DO 50 I=1,NROWS
40 WRITE(*,*)'How many counter should I put in row ',I,'?'
READ(*,*)J
IF (J.LT.1 .OR. J.GT.10) THEN
CALL ERRORHANDLER(1,2)
GOTO 40
ENDIF
NX(I)=J
50 CONTINUE
ENDIF
WRITE(*,*)'All right, let the game begins!'
RETURN
END
***** End Intro *****
*
****************************
***** ENDGAME Function *****
*********************************************************************
* This function will return the number of counters left in the
* board. This value will be used to determine the end of the game.
* Pseudocode: Total the numbers in the column.
*********************************************************************
INTEGER FUNCTION ENDGAME()
INTEGER NX,NROWS,PLAYER
COMMON /PARAM/NX(10),NROWS,PLAYER
INTEGER I,TOTAL
TOTAL = 0
DO 10 I=1,NROWS
TOTAL=TOTAL+NX(I)
10 CONTINUE
ENDGAME=TOTAL
RETURN
END
***** End ENDGAME *****
*
******************************
***** Display Subroutine *****
*********************************************************************
* This subroutine will display the board to the screen.
* This one uses implied loop for aesthetic considerations.
*********************************************************************
SUBROUTINE DISPLAY()
INTEGER NX,NROWS,PLAYER
COMMON /PARAM/NX(10),NROWS,PLAYER
INTEGER I,J
DO 10 I=1,NROWS
WRITE(*,*)I,' ',('X',J=1,NX(I))
10 CONTINUE
RETURN
END
***** End of Display *****
*
********************************
***** HumanMove Subroutine *****
*********************************************************************
* This subroutine will take user input for his moves and update
* the board appropriately.
* Pseudocode:
* 1. Ask for row
* 1. if out of bounds - Warning - ErrorHandler
* 2. if no counter - Warning - ErrorHandler
* 2. Ask for number of counter to be removed
* 1. if 0 or less then null action, back to row input
* 2. if less than max then subtract
* 3. if max or more then set counter to zero.
*********************************************************************
SUBROUTINE HUMANMOVE
INTEGER NX,NROWS,PLAYER
COMMON /PARAM/NX(10),NROWS,PLAYER
* i is for index, and t for token input, m is for maxt
INTEGER I,T,M
*
* Ask for row
10 WRITE(*,*)'Which row, Sire?'
READ(*,*)I
* if out of bounds
IF (I.LT.1 .OR. I.GT.NROWS) THEN
CALL ERRORHANDLER(1,3)
GOTO 10
ENDIF
* if row is empty
IF (NX(I).LT.1) THEN
CALL ERRORHANDLER(2,4)
GOTO 10
ENDIF
*
* Ask for number of counter to be removed
WRITE(*,*)'How many should I remove, Sire?'
READ (*,*)T
* if 0 or less then null action, back to row input
IF (T.LE.0) THEN
CALL ERRORHANDLER(2,5)
GOTO 10
ENDIF
*
* Subtract counter - store counter in M
M=NX(I)
NX(I)=NX(I)-T
* if max or more then set counter to zero.
IF (NX(I).LE.0) THEN
WRITE(*,*)'Ho boy, you took them all, didn''t you?'
T = M
NX(I)=0
ENDIF
WRITE(*,*)'Human move row ',I,' taking',T
RETURN
END
***** End of HUMANMOVE *****
*
*******************************
***** COMPMOVE Subroutine *****
*********************************************************************
* COMPMOVE will scan the NROWS rows of counters, compute the
* binary representation of the rows, determine which
* columns of the binary representation results in an
* odd sum. If none are odd (STALL=1) a stalling move
* is executed. Otherwise (STALL=0), the maximum row
* is altered by changing all the columns that contribute
* to an odd sum.
* Pseudocode
* 1. Convert all decimals (up to nrows) to binary (BIN(10,4))
* 2. Sum all binary columns (SUM(4))
* 3. Determine EVEN-ODDS (ODD(4)) (0 for even, 1 for odd)
* 1. If no odd bits, take 1 from row which has most counters
* 2. Else continue
* 4. Find most significant odd sum - yields column number.
* 5. Find the appropriate row (with 1 in column number).
* 6. Modify the appropriate row
* 1. Change most significant bit to zero
* 2. Flip all bits in the odd position in ODD array
* 7. Convert binary to decimal
*********************************************************************
SUBROUTINE COMPMOVE
INTEGER NX,NROWS,PLAYER,TLEFT,WINNER
COMMON /PARAM/NX(10),NROWS,PLAYER
*
* Local variables used
INTEGER BIN(10,4),SUM(4),ODD(4)
INTEGER STALL,ROW,POWR,NUMB,MAXRO,I
** BIN(10,4) - The binary field, corresponding to the playfield.
** The second index refers to power.
** 1 - least significant
** 4 - most significant
** SUM(4) - The sum for the binary column.
** Used to compute Even Odd bits
** ODD(4) - The odd array for each power column in binary field
** 0 - Even
** 1 - Odd
** STALL - 1 - No odd bit in ODD()
** 0 - otherwise, not used.
** ROW - Used in BIN(ROW,POWR) or NX(ROW)
** POWR - Used in BIN(ROW,POWR)
** NUMB - Number, used in decimal-binary conversion
** MAXRO - Stalling Row index
*
* Convert all decimals (up to nrows) to binary (BIN(10,4))
* Also find maxro.
MAXRO=1
DO 20 ROW=1,NROWS
NUMB=NX(ROW)
IF (NX(MAXRO).LT.NUMB) MAXRO=ROW
DO 10 POWR=4,1,-1
I = 2**(POWR-1)
BIN(ROW,POWR)=NUMB/I
NUMB=NUMB-(BIN(ROW,POWR)*I)
10 CONTINUE
20 CONTINUE
*
* Sum all binary columns (SUM(4))
* Determine EVEN-ODDS (ODD(4)) (0 for even, 1 for odd)
DO 40 I=1,4
SUM(I)=0
DO 30 ROW=1,NROWS
SUM(I)=SUM(I)+BIN(ROW,I)
30 CONTINUE
ODD(I)=MOD(SUM(I),2)
40 CONTINUE
*
* Debugging display
* DO 50 I=1,NROWS
* WRITE(*,*)BIN(I,1),BIN(I,2),BIN(I,3),BIN(I,4)
*50 CONTINUE
* DO 60 I=1,4
* WRITE(*,*)I,SUM(I),ODD(I)
*60 CONTINUE
*
* Find most significant odd sum - yields column number.
POWR=4
70 IF (POWR.EQ.0) THEN
* Stalling
WRITE(*,*)'Computer move row ',MAXRO,'taking 1'
NX(MAXRO)=NX(MAXRO)-1
PAUSE
RETURN
ENDIF
IF (ODD(POWR).EQ.0) THEN
POWR=POWR-1
GOTO 70
ENDIF
*
* Find the appropriate row (with 1 in column number)
* for (ROW=1;BIN(ROW,POWR)<>1;ROW++) - only takes 1 line in C!
ROW=1
80 IF (BIN(ROW,POWR).EQ.1) GOTO 90
ROW=ROW+1
GOTO 80
*
* Modify the appropriate row
90 CONTINUE
* 1. Change most significant bit to zero
BIN(ROW,POWR)=0
* 2. Flip all bits in the odd position in ODD array
DO 100 I=POWR-1,1,-1
BIN(ROW,I)=ABS(BIN(ROW,I)-ODD(I))
100 CONTINUE
*
* Convert binary to decimal
NUMB=0
DO 110 I=1,4
NUMB=NUMB+(BIN(ROW,I)*(2**(I-1)))
110 CONTINUE
* Debugging Display
* DO 120 I=1,NROWS
* WRITE(*,*)BIN(I,1),BIN(I,2),BIN(I,3),BIN(I,4)
*120 CONTINUE
WRITE(*,*)'Computer move row',ROW,'taking',NX(ROW)-NUMB
NX(ROW)=NUMB
RETURN
END
***** End of COMPMOVE *****
*
***********************************
***** ErrorHandler Subroutine *****
*********************************************************************
* This subroutine will intercept errors and warnings and display
* the approprate messages and/or user reaction.
*********************************************************************
SUBROUTINE ERRORHANDLER(ERRORTYPE,ID)
INTEGER ERRORTYPE,ID
*
* Display Errortype
IF (ERRORTYPE.EQ.1) THEN
WRITE(*,*)'Input out of range'
ELSEIF (ERRORTYPE.EQ.2) THEN
WRITE(*,*)'Stupid Error#39'
ELSE
WRITE(*,*)'Indeterminant error type'
ENDIF
*
* Display Error id
GOTO (10,20,30,40,50),ID
WRITE(*,*)'ErrorHandler Subroutine Error'
WRITE(*,*)'Ho boy! Are you in fer it, now!'
STOP
10 WRITE(*,*)'Number of row determination in Init function'
GOTO 999
20 WRITE(*,*)'Number of column input error in Init function'
GOTO 999
30 WRITE(*,*)'Row input error. Stupid humans can''t read'
GOTO 999
40 WRITE(*,*)'But there''s nary a counter in that row, Sire!'
GOTO 999
50 WRITE(*,*)'Counter input error. Sheessh!'
GOTO 999
999 RETURN
END
***** End ErrorHandler *****