To Know is To Use and Experience... reading about an old language
isn't nearly as satisfying as actually writing software in that
language. Reversi is one of my favorite board games and I've
already written a BASIC version
so it was a
good choice for my first non-trivial HP FORTRAN program. The end result
was another ABS program I can run on my HP2113E minicomputer or under
simulation, in the reversi.zip file (along
with derivitive versions, some adaptable to compile for a PC).
Documentation made all the difference in the world, thankfully I
found a copy of the 1973 version of HP FORTRAN, not
identical to the version I have but close enough. Learning the language
was a breeze, there just isn't much of it. That's a good thing! These
days learning a new programming language is quite difficult because of
the (in my opinion) excessive complexity of all things modern, I found
that subroutines and even recursion could be easily implemented using
only simple conditional branches and soon I found myself concentrating
on the algorithm with little concern for the apparent limitations of
the language. All that's needed to write just about any program are
arrays and variables, math, comparisons, branching and I/O, all that
other stuff is just more stuff that has to be learned before it becomes
useful. Even loop constructs aren't strictly necessary but nice to
have, especially when it's something simple like DO. Structured
goto-less programming is fine and all that but it's refreshing to write
code in a language where GO TO is king. Long Live Spaghetti Code!
(ducking...)
Before I could do much of anything I had to learn how to efficiently
compile and test my code, so I wrote a HP-IPL/OS program that takes
information about the source files and outputs a SimH HP2100 simulator
script that carries out all the steps needed to compile and link the
source into an ABS file. Once the build script was made I could edit
code, right-click and "run" the build script, then right-click and
simulate the new binary right away without having to go through all the
steps normally needed to operate the vintage compiler and linker
software. I feel a tinge of guilt for making it so easy but not
everything has to be authentic, I wanted to make a Reversi program in
FORTRAN, not practice typing at the simulator prompt (which isn't
authentic anyway).
Probably the only real limitation I encountered was I couldn't
figure out how to output text without it adding a CRLF, making it
impossible to accept input from anywhere besides column 1 [but the
solution ended up being trivial, page down]. I prefer to
enter my moves after a MOVE? prompt and an extra line wouldn't have
permitted the large board format I wanted to use, so figuring it
couldn't be that hard to print text I wrote a print routine in
assembly. Only it wasn't exactly easy... the interrupt-driven BCS
console driver induced problems like printing the text before the line
that was supposed to have already been printed, and adding a LF after
each character. To make it work I had to add a delay to permit previous
prints to complete and turn off interrupts while printing my stuff, not
an ideal solution but it functions. So long as the terminal isn't too
slow.
Here's the Reversi-playing code I came up with...
FTN,B,L,A |
Here's the code for the PRT subroutine...
ASMB,R,B,L |
And here's some of a run session...
*** REVERSI *** YOU=O ME=X MOVES=YX |
That was at lookahead level 1. Often it beats me, especially if I
slip it up and let it get an advantage. The program can look ahead up
to 3 moves but that doesn't necessarily make it play better, lookahead
is effective only if I choose the moves it thinks I'll make, which over
3 moves is not likely. The program doesn't have much of a strategy
other than a weighting table to indicate how valuable certain positions
are - side positions are specified as more worthy than middle
positions, corners are the most desireable, and positions next to the
corners are somewhat avoided until the associated corner position is
filled. I'm sure there are better or additional strategies that can be
employed, perhaps increasing the side next-to weight if the rest of
that side has already been filled.
To select a move the computer scans the entire board and for each
empty position looks in all 8 directions to see if there is one of its
pieces in that direction, if so it counts the number of opponent pieces
in between, adding to a "gain" variable. Once the piece gain has been
computed it's multiplied by the weight factor for that position to
score the possible move. If lookahead is greater than 0 it gets tricky
and saves the current variables and arrays, makes the move then calls
the move generation code again to predict the human's move and
subtracts its score from the move's score. Further lookahead levels
keep swapping sides adding and subtracting the score. When done
"playing" tests it puts the variables back and jumps back into the same
move code it was calling to perform the lookahead, a concept known as
"recursion". This is actually a mild example since while looking ahead
lookahead is disabled, otherwise an array, tricky code and a lot of
execution time would be needed to track all the nested possibilities.
Surprisingly the compiler let be jump out of and back into DO loops and
even save and restore the DO loop index variables to reuse the same
code, when I tried this trick in BASIC I had to branch to different
FOR/NEXT statements.
A tricky part was figuring out what to do with tie scores, since the
scan proceeds from 1,1 to 8,8 if it just ignored or always replaced
moves with tie scores it tends to choose moves to one side or the
other. To avoid this it uses the score, the move's raw gain and a
counter which is incremented for each new computer move, all added
together and AND'd with 1 to produce a tie-break bit. The counter also
helps randomize additional games, the first run is always deterministic
(there are no clocks or other mechanisms available to provide inherent
randomness), after that anything goes. Within each move block a static
tie-break isn't desireable since that would prevent ties in the middle
from being selected, too much randomness is just as bad as it tends to
favor ties to one side. Instead the move's piece gain is used,
sometimes it's the same, sometimes it's different (at least when
lookahead is in effect). A better way would have been to save all ties
and select each with equal probability but that's too much logic for
this hack, gotta draw the line somewhere.
For those not familiar with old-style FORTRAN, these IF statements
evaluate an expression then do a two or three way branch. If two
destination lines are specified, the first is followed if the
expression is less than 0 otherwise the second branch is followed.
Three numbers are used to specify less than 0, 0, or greater than 0.
These IFs never just drop through. One nice thing, if an expression
should never be less than 0 the first number can be a branch to some
error code to indicate the bug.
Other than PRT to print prompt text, there are no conventional
subroutines in this program. For one thing HP FORTRAN permits only 5
"modules" maximum in each source file and the resulting relocateable
"object" files give no clue as to how many modules they contain unless
hex-edited to look, when linking an additional "continue" has to be
given for each additional module as if it were a separate tape. This
can be handled by my build script maker but it's messy, if using
subroutines I'd be inclined to place each one in a separate source
file. The primary reason I decided against using subroutines relates to
how HP21xx minicomputers call subroutines, they store the return
address inside the code that's being called. This prevents any form of
recursion using conventional subroutines, recalling the code overwrites
the previous return address and it just goes into an endless loop.
However the language has a multiway branch in the form of GO TO
(line1,line2,etc),variable. If the variable contains 1 then it branches
to line1 etc. Problem solved, lets me recurse all I want without
cursing. Convulted perhaps but very easy to code for, just set the
LCTLx variable and add the "return" line to the final branch list.
Recursing While Recursing
Limiting recursion to one level makes for fast game play and simple
code, but not much strength. If the player doesn't choose the moves it
thinks will be chosen then its calculations will be misleading in some
way, possibly cancelling out an otherwise good move. Obvious losses are
detected, but its feeble attempts at setting up gains are easily
thwarted by human lookahead. To make it play better requires true
recursion - when looking ahead it looks ahead which possibly also looks
ahead, maximum depth has to be controlled to prevent runaway recursion.
At first this seemed like a very difficult problem but the solution
was fairly easy - all the variables used to save the current state are
arrays in this version, one dimension for each level allowed. This
includes the board and weight saves, since this FORTRAN supports only 2
dimensional arrays the third dimension is faked using a multiplied
offset. An array was added to hold the return "addresses" for
successive calls to the move generation code, and the actual lookahead
code itself where it swaps sides, plays the human move, swaps again to
play the computer response etc had to be recoded a bit to permit
reversing the roles so both sides could use. Also inserted a
GAIN=GAIN+1 at line 3022 for an exact gain count, not sure if it makes
any difference but seemed to make it stronger. The code includes
debugging functions, if an error occurs it indicates the line before
the IF that detected the bad value.
Huge numbers of calculations are needed to recurse in this mannor,
and it can get quite slow if running on real hardware. By default the
program looks 1 move ahead and 2 levels maximum,
and takes many seconds to come up with a move on real hardware. The
arrays are dimensioned for a maximum of 3 levels, which would take an
impractically long time to run on real hardware but not too bad under
simulation with the throttle setting disabled for maximum speed. The
play level prompt now prompts for recursion level in addition to the
existing number of moves to look ahead. I since figured out how to
suppress the newline when printing without resorting to machine code,
so the code no longer requires the PRT assembly subroutine. This
version also has variables for the logical units to make it easier to
port to other platforms.
FTN,B,L,A |
It's not too big as programs go... a 32KW HP21xx can run FORTRAN
programs much larger than this, but making it go much faster will
probably require implementing the flip and computer move generation
parts in machine code. An example of this is in the oth2src.txt file in
the hpgames.zip file.
Printing without a CRLF
Sometimes something seems impossible, but in fact is simply not
mentioned in the docs because it's a feature of another subsystem, in
this case the BCS library. I was playing around with HP Algol and
noticed one of the print examples in its docs ended with "_", and I
also knew Algol could print without a CRLF because of an old Chess
game.. hmm.. crafted up a little Algol program that prompted for a
string and printed it back, sure enough a "_" at the end of a print
string suppressed the CRLF. Algol's print formatting is practically
identical to FORTRAN formatting.. hmm.. sure enough the trick works for
HP FORTRAN too. Excellent! Doing it with machine code was educational
but not necessary, all I had to do was simply say "MOVE: _". Apparently
there isn't a standardized way to do this, but specifying strings as
"output",$ works for some versions of Fortran. The F2C utility can convert
this Reversi-playing program to PC-compatible C code with only minor
editing - comment the beginning FTN and ending END$ lines, make LUR=5,
and change all instances of _" to ",$ to supress newlines (see the
revrsi.txt file in the reversi.zip file for
compile details). Newer versions of Fortran use "string",advance="no"
to suppress newlines.
Last modified June 14, 2010
GO TO the HP Games Page.