I'm going to start this post by covering the 'exercises' I mentioned regarding Animal. Here's a simple fix for the issue of jumping out of the X and Y loops:
Code: Select all
455 FOR ZX=3 TO LEN(Q$)-1
460 IF MID$(Q$,X,2)=T$ THEN X=ZX:ZX=LEN(Q$)
470 NEXT ZX
480 FOR ZY=X+1 TO LEN(Q$)
490 IF MID$(Q$,Y,1)="\" THEN Y=ZY:ZY=LEN(Q$)
500 NEXT ZY
This takes out the 'just-in-case'
STOP commands; if you wanted to add a paranoia check, you'd have to do it a bit differently. (I'd set
X and
Y to 0 before starting the loops and change the relevant lines to
IF X=0 THEN STOP or what have you.)
(I may have said earlier, but back in my C64 days, I got used to using variables starting with Z as temporary values.
ZZ, of course, was the most ephemeral of those, sometimes destined to be thrown away immediately in a timing loop.)
Another way to get all but the first two characters of
A$(K) (as seen in line 200) would be
MID$(A$(K),3,LEN(A$(K))-2). However, since
MID$() gracefully handles running out of characters, you could easily make that
MID$(A$(K),3,LEN(A$(K)) - or, indeed,
MID$(A$(K),3,999), presuming your version of BASIC can't have strings that long. This is why, incidentally, you would bother with using
MID$() in this situation - so you don't have to also use
LEN(). You could also amend my modified lines 460 and 490 with that in mind.
On an unrelated note: it'd probably be a good idea to set the various variables used for input to
"" before using
INPUT. I've confirmed that, at least in Commodore BASIC V2, if you don't enter anything, it doesn't change the original value of the variable, and one carriage return too many could confuse the program. Also, there's no sanity check for animal names, so you could stick a backslash in the name or not type anything and really confuse matters.
As for the assumptions made in lines 600 on, I said there were two. One is that the screen/paper is at least 60 columns wide. The other is that no animal will have a name longer than 11 characters. Both assumptions appear in line 624, which tries to format the animal names into pretty columns but only works if those constraints are met.
Finally, to keep from overflowing the
A$() array, I'd suggest checking the value of
A$(0) before adding new information - ideally, after confirming that the player has a new animal in mind but before bothering to ask for information about it - and throwing some sort of complaint before returning to line 120. And if I were somehow in the Teletype age, I might consider adding a 'dump database' subroutine that would format and print BASIC
DATA commands that I could then type back in to update the code and give it more brainpower! (If the teleprinter had a paper tape attachment, I could even write the lines to tape, then read them back in to make the changes automatically. That'd be one way to save and load data!)
Let's move on to a game that's actually halfway worth playing!
Okay, let me make this clear right from the start: this is not Awari (or Oware, as it's more properly known). Nor is it Mancala, any more than you're Primate. Mancala is a name for a
large body of games with similar mechanics, some of which are simple enough to have been solved by computers, some of which are rather complex. This game is most similar to a variant called Kalah, but has several differences in play. Familiarize yourself with the rules above before we proceed.
The listing for this game is surprisingly short, considering it actually implements a learning AI. It's well-organized, too, which is a treat. That said, it commits not one but two major sins, and it has a bug or two besides. Let's get started breaking it down.
(By the way, I'm making some assumptions about how much you know about programming that may not be correct. I don't mean to talk down to you. If I'm talking
up to you, let me know what needs clarification.)
Code: Select all
5 PRINT TAB(34);"AWARI"
7 PRINT TAB(15);"CREATIVE COMPUTING MORRISTOWN, NEW JERSEY"
10 DATA 0
15 DIM B(13),G(13),F(50):READ N
The
B() array stores the state of the board.
B(0) is the number of beans in the player's left-most pit. The numbers ascend counter-clockwise, so
B(6) is the number of beans in the player's home pit, and
B(13) is the number of beans in the computer's home pit. The
G() array is used to back up that state as part of the computer's move-making code.
The
F() array and
N are used in the computer's learning AI. I'll go into more detail as we explore that code. I don't know why
N is set with a
DATA - READ combo, though; neither command is used elsewhere in the program, so you could just say
N=0. This will be the mildest of the program's technically legal, but kind of strange, decisions.
Code: Select all
20 PRINT:PRINT:E=0
25 FORI=0 TO 12:B(I)=3:NEXT I
30 C=0:F(N)=0:B(13)=0:B(6)=0
35 GOSUB 500
40 PRINT "YOUR MOVE";:GOSUB 110
45 IF E=0 THEN 80
50 IF M=H THEN GOSUB 100
55 IF E=0 THEN 80
60 PRINT "MY MOVE IS ";:GOSUB 800
65 IF E=0 THEN 80
70 IF M=H THEN PRINT ",";:GOSUB 800
75 IF E>0 THEN 35
80 PRINT:PRINT"GAME OVER"
85 D=B(6)-B(13):IF D<0 THEN PRINT "I WIN BY";-D;"POINTS":GOTO 20
90 N=N+1:IF D=0 THEN PRINT "DRAWN GAME":GOTO 20
95 PRINT "YOU WIN BY";D;"POINTS":GOTO 20
This is the main loop of the program. As you can see, it makes extensive use of subroutines, making the program as modular as BASIC allows. Let's go through it.
Line 20 sets
E to 0.
E is a flag used to determine if the game is not over (that is, if both players still have beans; I'll explain why I phrased it that way when we get there.) Lines 25 and 30 initialize the board and the learning AI's information storage for this game. (Again, more detail when we get there.)
Where line 20 starts the loop of the entire play session, line 35 starts the loop of a single game. The subroutine at line 500 prints the current state of the board.
Line 40 starts the section of the code that processes the player's turn. The subroutine at line 110 takes the player's move, updates the board and the learning AI's information storage, prints the updated board, and checks whether the game is over. If it is, it sets
E to 1, and line 45 jumps to the 'game over' code. Line 50 determines whether the player gets a second move (I'll explain both
M and
H when we get there) and, if so, calls the subroutine at line 100 - which is just the subroutine at line 110, only instead of printing
"YOUR MOVE", it prints
"AGAIN".
After another check if the game is over (if needed), it's the computer's turn. The subroutine at line 800 makes a move for the computer; more detail when we get there. It's worth noting, though, that this subroutine does
not print the updated board, which is why lines 60 and 70 print its moves (if it gets two) on the same line. If neither move ends the game, we then head back to 35, which prints the result of the computer's move(s) and starts things off again.
Starting at line 80, we handle a game over. As I said earlier,
B(6) is the number of beans in the player's home pot, while
B(13) is the number of beans in the computer's home pot. The difference,
D, is positive if the player won, 0 if the player tied, and negative if the player lost. The appropriate message is displayed, and then the game loops back to line 20, starting a new game. Note that
N is increased if the player wins or draws, but not if the player loses. That's part of the learning AI.
And that's it for the main loop! Time to look at some subroutines, starting with the one at line 500.
Code: Select all
500 PRINT:PRINT" ";:REM 3 SPACES
505 FOR I=12 TO 7 STEP -1:GOSUB 580
510 NEXT I
515 PRINT:I=13:GOSUB 580
520 PRINT" ";:PRINT B(6):PRINT " ";:REM 23 SPACES, THEN 3 SPACES
525 FOR I=0 TO 5:GOSUB 580
530 NEXT I
535 PRINT:PRINT:RETURN
580 IF B(I)<10 THEN PRINT " ";
585 PRINT B(I);:RETURN
I added the REM statements here because the scan doesn't have any real way to tell how much space is there other than comparing the text to the adjacent lines and counting the characters. You can leave them out.
This subroutine, as previously mentioned, is what we use to print the board.
STEP is a new part of the
FOR - NEXT combo. By default, each time we go through a
FOR - NEXT loop, the loop variable goes up by 1.
STEP lets us change that. Lines 500-510, therefore, print the first line of the board, showing the computer's pits; since the pits are numbered counter-clockwise, the leftmost is pit 12, the next 11, and so on.
The subroutine at line 580 - look, ma, we're calling a subroutine from a subroutine! - prints the number of beans in pit
I, padding it with a space if it's less than 10. Since there are only 36 beans all told, this means each time we call this function, we use the same number of characters. This keeps the numbers on the board neatly aligned.
Line 515 prints the number of beans in the computer's home pit; line 520 moves over to where the player's home pit is on the screen, then prints that number as well. (Note that we do not use
GOSUB 580 here; whether or not that's a good thing is a matter of taste, and it's easily changed in any event.) Then it sets up for line 525 to print the player's pits and adds a few blank lines before coming back.
You may need to adjust the number of spaces in line 520, based on how your version of BASIC prints numbers.
This subroutine is called elsewhere, but under unusual circumstances. You'll see how when we get there.
Code: Select all
100 PRINT "AGAIN";
110 INPUT M:IF M<7 THEN IF M>0 THEN M=M-1:GOTO 130
120 PRINT "ILLEGAL MOVE": GOTO 100
130 IF B(M)=0 THEN 120
140 H=6:GOSUB 200
As previously mentioned, line 100 is jumped to if this is the player's second move; line 110 is jumped to if it's the first. This handles what prompt is used for the player's move.
Line 110 does something legal, yet somewhat odd: it nests
IF - THEN commands in order to make sure
M is both less than 7 and greater than 0 (in other words, in the range 1-6). BASIC does provide logic operators, so you could write
IF M>0 AND M<7 THEN M=M-1:GOTO 130; I'm not sure why the programmer chose this approach.
Note that, from the
player's perspective, their pits are numbered 1-6, but internally they're 0-5. That's what the end of line 110 takes care of.
Line 130 makes sure there are actually beans in the pit the player wants to sow from; with that done, we call the subroutine at 200, which actually makes the move and checks to see if the game is over.
Then we do...
...this. Okay. Remember how I said BASIC has subroutines? I was a
filthy liar. The
only difference between
GOTO and
GOSUB is that
GOSUB leaves a note on the top of what's called a stack saying where to go the next time the program
RETURNs. (
FOR - NEXT uses a similar stack to keep track of loops that haven't finished yet. Running out of memory for either causes a crash, which is why, much like not wanting to jump out of
FOR - NEXT loops, you don't want to nest
GOSUB calls too deep.)
It is perfectly legal, therefore, for us to
GOTO 500, and when program execution hits the
RETURN, it'll take the top note off the stack - and since we returned properly from
GOSUB 200, the note on top is from
GOSUB 110, back on line 40 or 50, depending. In other words, instead of explicitly calling the 'print the board' subroutine before returning from this one, the flow of the program basically tacks that subroutine onto the end of this one.
Let's move on to line 200.
Code: Select all
200 K=M:GOSUB 600
205 E=0:IF K>6 THEN K=K-7
210 C=C+1:IF C<9 THEN F(N)=N(F)*6+K
215 FOR I=0 TO 5:IF B(I)<>0 THEN 230
220 NEXT I
225 RETURN
230 FOR I=7 TO 12:IF B(I)<>0 THEN E=1:RETURN
235 GOTO 220
(Almost) the first thing this subroutine does is call
another subroutine which actually updates the board for the move the player (or, eventually, the computer) chose.
M, you will recall, is that move; it's passed to that subroutine (well, 'passed' to that 'subroutine'), which will change it, so we back it up to
K first. (That's not the only reason we put it in
K, but we'll get to that.)
Line 205 starts the code to check if the game is over. The first thing it does is set
E to 0, i.e. 'the game is over'. Remember that I said
E is whether the game is
not over? In BASIC terms, 0 is 'false', and anything else is 'true' - I'll go more into that when we start seriously dealing with bitwise operations and logic statements. So if we reach the end of the subroutine and haven't set
E to something else, then the game is over.
Lines 215-235 do the bulk of the work of deciding if the game is over. This is where the first major sin of the game is committed, as we jump out of not one but two loops. (Note also that those loops
share a
NEXT statement, which is, again, technically correct but kind of odd.) Line 215 determines if the player has a legal move, while line 230 determines if the computer has a legal move; if both are true (i.e., if both
IF - THEN statements go off),
E is set to 1 - the game is
not over - and the function is returned from. If either loop finishes, either the player or the computer has no beans left, and the function is returned from without changing
E - the game is over.
Incidentally, this subroutine is somewhat flawed. If either the player or the computer get more than half of the beans in the game into their home pot, then the other participant can't win. This code could check for that by seeing if either
B(6) or
B(13) is greater than 18 and returning immediately if so.
Code: Select all
600 P=B(M):B(M)=0
605 FOR P=P TO 1 STEP -1:M=M+1:IF M>13 THEN M=M-14
610 B(M)=B(M)+1:NEXT P
615 IF B(M)=1 THEN IF M<>6 THEN IF M<>13 THEN IF B(12-M)<>0 THEN 625
620 RETURN
625 B(H)=B(H)+B(12-M)+1:B(M)=0:B(12-M)=0:RETURN
Here's where the board is actually updated.
M starts as the move the player or computer made.
B(M) is therefore the number of beans in that pit; we assign this to
P before removing those beans.
P is therefore the number of beans we just picked up.
Lines 605-610 handle sowing the beans. Line 605 does another technically legal, but kind of weird, thing, using
P as a loop variable starting at
itself to count out the beans. We re-purpose
M to mark the pit the next bean will go into, subtracting 14 each time we get back to the player's first pit, and proceed until we're out of beans, at which point
M holds the location of the last bean we sowed.
Having sown the beans, we then need to know if a capture has occurred. The check in line 615 does this:
IF there's exactly one bean in the current pit (i.e., if the pit was empty before we sowed the last bean into it),
THEN IF that pit isn't the player's home pit,
THEN IF that pit isn't the
computer's home pit,
THEN IF there are beans in the pit directly across from the current pit,
THEN jump to line 625. If any of those aren't true, we just return from the function.
Line 625 scoops the beans from both pots into the home pot. Which home pot? Well, back on line 140, we set
H to 6 before calling line 200, which called line 600. As pit 6 is the player's home pit, the first time we come here is when the player makes their first move. The subroutine that makes the computer's move must, therefore, set
H to 13 before coming anywhere near this code.
Code: Select all
800 D=-99:H=13
805 FOR I=0 TO 13:G(I)=B(I):NEXT I
810 FOR J=7 TO 12:IF B(J)=0 THEN 885
815 Q=0:M=J:GOSUB 600
820 FOR I=0 TO 5:IF B(I)=0 THEN 845
825 L=B(I)+I:R=0
830 IF L>13 THEN L=L-14:R=1:GOTO 830
835 IF B(L)=0 THEN IF L<>6 THEN IF L<>13 THEN R=B(12-L)+R
840 IF R>Q THEN Q=R
845 NEXT I
850 Q=B(13)-B(6)-Q:IF C>8 THEN 875
855 K=J:IF K>6 THEN K=K-7
860 FOR I=0 TO N-1:IF F(N)*6+K=INT(F(I)/6^(7-C)+.1) THEN Q=Q-2
870 NEXT I
875 FOR I=0 TO 13:B(I)=G(I):NEXT I
880 IF Q>=D THEN A=J:D=Q
885 NEXT J
890 M=A:PRINT CHR$(42+M);:GOTO 200
Which it does. (I know that's a lot of code to go through, but don't worry; I'll repeat sections as needed.)
D is used by the AI to determine which move it wants to make; I'll cover exactly how when we get there.
Line 805 backs up the current state of the board into
G(); as you'll see, when the computer is trying to decide what move to make, it's going to be calling line 600, so we want it to be able to take back a move.
Line 810 starts a loop that goes through all of the computer's legal moves.
J is the current move the computer is considering; if there are no beans in that pit, it jumps to 885, the end of the loop. (Don't worry about line 890 for now, except to note that it has another
GOTO to a subroutine, in this case the one that applies the move the computer has chosen and checks for a game over; since we got there with a
GOTO, its
RETURN will take us back to line 60 or 70, depending.)
I don't know if it's my scan or a typo in the book or what, but the first part of line 815 looks like
G=0; it should be
Q=0, as shown above. Yet again, I'll cover what that means when we get there. We then set
M to the move the computer is considering before calling line 600, which updates the board. (This is why we backed up the board earlier. In a language with proper scope and proper subroutines, we'd pass the subroutine a copy of the board for processing.)
Line 820 starts the real meat and potatoes of the AI. Having made this move, the computer asks, what could the player do in response?
I is a possible move by the player; if that wouldn't be a legal move, it jumps to 845, the end of the loop. Line 825 sets
L to the last pot the player would sow into and initializes
R. The program then does some calculations with
R and sets
Q to the greater of
Q and
R before finishing the loop.
So why was I vague in that last sentence? Well, there's a bug in the code here.
Q, as we'll discover, is how much the score (or, rather, the difference between how many beans the player has and how many the computer has) will change in the player's favor if they make the most optimal move (for a value of 'most' that takes into account the AI's limits).
R is therefore how much the score will change in the player's favor if they make
this move. But it's calculated incorrectly. Line 830 is supposed to account for the player putting a bean in their home pot if they go past it, while line 835 is supposed to account for them making a capture on their move, but both are incorrect. Here's a patch.
Code: Select all
830 IF L>13 THEN L=L-14:GOTO 830
832 IF L>5 THEN IF L<13 THEN R=R+1
835 IF B(L)=0 THEN IF L<>6 THEN IF L<>13 THEN R=R+B(12-L)+1
If the player has made a move that goes around the board and back into their home territory, they've put a bean into both their own home pit and the computer's, so the relative score hasn't changed. If, on the other hand, they've made a move that ends either in their home pit or in enemy territory, they've put a bean into their home pit but
not the computer's, so the relative score has gone up by one in the player's favor. Finally, line 835 previously didn't account for a capture also scoring the bean doing the capturing, so we add 1 there.
Let's take a look at the rest of the
J loop again.
Code: Select all
850 Q=B(13)-B(6)-Q:IF C>8 THEN 875
855 K=J:IF K>6 THEN K=K-7
860 FOR I=0 TO N-1:IF F(N)*6+K=INT(F(I)/6^(7-C)+.1) THEN Q=Q-2
870 NEXT I
875 FOR I=0 TO 13:B(I)=G(I):NEXT I
880 IF Q>=D THEN A=J:D=Q
885 NEXT J
890 M=A:PRINT CHR$(42+M);:GOTO 200
We previously set
Q to the greatest change of the score in the player's favor from all of the player's possible moves - in other words, the change of the score in the player's favor if they make the best possible move in response to the move the computer is considering. At the start of 850, we change
Q to be the computer's relative score in that case. (This isn't strictly necessary - we could change lines 860 and 880 to avoid it - but it does no harm.) We then potentially skip over a chunk of code. (Remember
C? We're almost to the bit where we explain it.) Whether or not we run that code, we then go to line 875, which restores the backup of the board.
D was set to -99 when we started looking for a move. Whatever the computer's relative score is the first time we go through this loop, it
has to be better than that, so we store the current move under consideration in
A and update
D. The next time through, we only do this if
Q is greater than or equal to
D. What this means is that, by the time we end the loop,
A will contain the move that
maximizes the computer's score even if the player tries to
minimize it - the best-case scenario of the worst-case scenarios. This is called the
maximin, which may sound familiar; min-maxing takes its name, somewhat improperly, from the term
minimax, which is used when we're talking about costs instead of benefits - the
minimum loss out of potential
maximum losses.
Having decided on what move the computer wants to make, we need to actually make it. We set
M to
A, then - wait, what?
The CHR$() Function
The function
CHR$() takes a number and returns its character representation. What's that? Well, you remember me talking about how strings are sorted, and how each character has an internal numeric representation that is used for that sorting (and what a mess that can be varying on implementation)? This function takes one of those numbers and returns the associated character. Fortunately, in every BASIC variety I know of, the digit characters have the same numeric representations: 48 is "0", 49 is "1", and so on up to 57 being "9". Therefore, if the computer decides to make move 7, we add 7 to 42, getting 49, which is "1". In other words, that command prints the digit 1-6, depending on what move the computer makes.
So why not just
PRINT M-6;? Well, remember how different varieties of BASIC pad numbers differently when you print them? This is one way to get around that. Doing this guarantees that there isn't a space either before or after the digit of the computer's move. This approach only works for a single digit, mind, but it works, and it works across all versions of BASIC. (If you're curious about how to make a subroutine that does that for multi-digit numbers, just ask.)
Oh, and in case you're curious: the
ASC() function reverses the process.
ASC("0") = 48.
We've covered, at this point, everything about the program but one thing. Well, there are a few minor things, so let's get them out of the way real quick...
Code: Select all
50 IF M=H THEN GOSUB 100
...
70 IF M=H THEN PRINT ",";:GOSUB 800
Remember these two lines? Now that we know that
M is the pit where the player or computer put their last bean and
H is their home pit, we see how they get a second turn: by putting that bean into their home pit.
Code: Select all
900 FOR I=0 TO N-1:PRINTB(I):NEXT I
999 END
This code isn't called anywhere in the program. Even if it was, it doesn't do anything useful - I assume it was intended as debug code, but if it was, it should be printing the contents of
F(), not
B().
The learning AI
Okay, with that out of the way, let's talk learning AI. We already know how the computer chooses its moves in the
first game of a session, when it hasn't learned anything. But how does it improve? Well, we'll need to look at a couple different parts of the code for that. Here's the first:
Code: Select all
200 K=M:GOSUB 600
205 E=0:IF K>6 THEN K=K-7
210 C=C+1:IF C<9 THEN F(N)=N(F)*6+K
Line 210 is where the magic starts. At the beginning of the program run, in line 15, we set
N to 0, and line 30 sets
F(N) to 0. Line 210 is called every time we check if the game is over, i.e. after someone has finished making a move. That means that, the first time we get there, we multiply 0 by 6 and add
K, then store the result in
F(0). Each time thereafter, we multiply the current value by 6 and add
K again, until
C reaches 9, at which point we stop doing this.
So what is
K? Well, if it's the player's move, we set
K to
M, the move they chose, before actually making the move. (This happens in line 200.) That means that it's a number from 0 to 5. If the computer made the move, though,
K is still set to
M, but then we subtract 7 from it (since the computer's moves are in the 7-12 range) - which, funnily enough, makes
K a number from 0 to 5.
This means that, after the first move made, either player or computer,
F(N) contains the first value of
K, or
K1 for short. After the second move made, it contains
6 * K1 + K2. After the third move made, it contains
36 * K1 + 6 * K2 + K3. And so on until
C hits 9.
At which point, F(0) contains a record of the first eight moves of the game. (With a honking big asterisk, but we'll get to that.) Since any given
K is in the range 0-5, we can retrieve each move by dividing by six and taking the remainder, and we don't need the information about who made the move because we can reconstruct that by replaying the moves.
This is the first part of the learning AI. At the end of a game, if the player lost, we don't increase
N, and the first thing we do in the new game is set
F(N) to 0, which means the computer tosses out the information it just got. If the player won or drew, though, we increase
N by one before looping back, which means that information is preserved. The computer is keeping the first several moves of that game in mind for later, hoping to avoid its mistakes.
Code: Select all
850 Q=B(13)-B(6)-Q:IF C>8 THEN 875
855 K=J:IF K>6 THEN K=K-7
860 FOR I=0 TO N-1:IF F(N)*6+K=INT(F(I)/6^(7-C)+.1) THEN Q=Q-2
870 NEXT I
Here's the second part of the equation. Starting at line 855, we figure out the
K that would result from the computer's
next move (for the record, the line could just be
K=J-7, since
J will always be greater than 6), then enter a loop with
I.
The code, unfortunately, makes a misstep here, though not a lethal one. Unlike some languages, in BASIC a
FOR - NEXT loop is guaranteed to run at least once. The intent of the code in line 860 is to compare the current game to previous games, but if we haven't had any previous games, we wind up comparing it to itself. I'd change line 850 to end
IF C>8 OR N=0 THEN 875.
If the comparison in line 860 is true, then we subtract 2 from
Q. Since
Q is the score the computer expects to have after making the move it's considering, this says 'if we've been in this situation before, and didn't win, this position isn't as good as we think it is'. So why isn't the comparison just
IF F(N)=F(I)? That is the final mystery.
Let's suppose that the first move the player makes is from their fourth pit (internally, pit three), which puts a seed in their home pit, giving them a second move. They then move from their first pit (internally, pit zero), putting their last seed in the now-empty pit and making a capture. Let us suppose further that the player has already won or drew a game. It is now the computer's move.
N=1;
F(N)=6*3+0=18;
C=2; and
K is the move the computer is currently contemplating, from 0 to 5.
F(N)*6+K is therefore what will be stored in
F(N) if the computer actually makes this move.
F(0) is the first eight moves of the first game the player won or drew.
^ is BASIC's exponentiation operator, so
6^(7-C) is 6[super]5[/super]. Since dividing by six
once removes the information from the previous move, dividing by six five times in a row removes the information from the five previous moves - and eight minus five is three.
So now we have the first three moves of that previous game... and a ratty bit of fraction, since
F() is a floating-point array. (This variety of BASIC doesn't have integer variables.) We get rid of them with the
INT() function - but we add .1 first. Why? Well, .1 is less than 1/6, so this won't ever push the fractional bit over 1, but it
will handle any fractional weirdness where dividing 6 by 6 somehow produces 0.9999. (It has to do with how floating-point numbers in general, not just in BASIC, are handled. BASIC just handles it more poorly than other languages.)
In other words, if this third move would replicate the first three moves of a previous game - and if the player used this strategy in that game, at least one of the moves the computer's considering will - we mark that move as not being as good as we think. This is likely to make the computer choose a different move, which will hopefully increase its chances of winning, and if it doesn't, well, that's more data for next time. And if the player keeps winning by using those first two moves, the computer is going to be more and more unlikely to choose any option that led to a loss, since it can subtract two more than once.
Once we've made eight moves, we're in unknown territory, since that's as far as the computer can keep track of. At that point, it stops calling the 855-870 code and does the best it can.
There's a bug in this code, incidentally. If
C=8,
C^(7-C)=1/6, so we wind up multiplying
F(I) by 6.
C is updated after this part of the code, so
C=8 here means the computer's making its
ninth move. Line 850 should end
IF C>7 OR N=0 THEN 875.
That Honking Big Asterisk
So that thing I said about
F() storing the first eight moves of a given game? Weeeell... that depends on
F() being capable of holding a number as large as 6[super]8[/super]-1, or 1679615, without issue. Fortunately, most varieties of BASIC can handle that. Unfortunately, they may not be able to handle it perfectly. I mentioned floating point weirdness; because of the way these numbers are stored internally, a number that displays as 6 may actually be something like 5.9999997 or something, which is why we added .1 in line 860.
So, you might say, your variety of BASIC supports integer arrays. Why not just use those? Well, you can, but there are a few things to be careful of. One is that the behavior you get when you divide an integer variable by something else also depends on your variety of BASIC. 11/6 may be 1.8333... and get rounded down by
INT() to 1, but
F%(N)/6, with
F%(N) containing the integer 11, may give 1.8333... or it may give 1. Or 2, the division rounding to the nearest integer instead of rounding down.
The other thing you need to be aware of is that integers have limits, just like floating point numbers do. With floating point numbers, it's generally significant digits (i.e, you might have trouble storing exactly 1.795668586868469) but with integers, it's a hard limit on the minimum and maximum values - and in, say, QuickBASIC, that maximum limit is 32767! Fortunately QuickBASIC also provides the long integer type (the
& suffix), which goes up to around two billion (precisely, 2147483647), but, say, Commodore BASIC V2 does
not.
If your flavor of BASIC provides neither sufficiently accurate floating point numbers nor sufficiently large integers, you could change
F() to have two dimensions, so
F(N, C) would hold the
Cth move of game
N. You'd replace line 860 with a loop through the second dimension's elements, looking for all of them to match your current game's up until the point you're at.
Still. This program, once you deal with the major sins of 'jumping out of loops' and 'assuming a certain precision from variables', is a compact, well-organized program that plays an acceptable game of 'Awari' and learns from its mistakes. It'd be relatively easy to change it to follow the actual rules of Kalah, and the AI could be adapted to any reasonably simple game. I didn't expect much from this program going in, and I'm pleased by just how wrong I was!
In case you want to try it for yourself, here's the full, bug-patched listing. (It also fixes a bug I didn't mention: if
N>50,
F(N) is invalid. The fixed program will just stop learning at that point. I also added something to keep pressing enter at the input prompt from doing something unexpected.) It'll work on even a 40-column monitor, provided you adjust lines 5-7. Omit the comment on line 520, or else the line will be too long for (at least) Commodore BASIC V2.
Code: Select all
5 PRINT TAB(34);"AWARI"
7 PRINT TAB(15);"CREATIVE COMPUTING MORRISTOWN, NEW JERSEY"
10 DATA 0
15 DIM B(13),G(13),F(50):READ N
20 PRINT:PRINT:E=0:IF N>50 THEN N=50
25 FORI=0 TO 12:B(I)=3:NEXT I
30 C=0:F(N)=0:B(13)=0:B(6)=0
35 GOSUB 500
40 PRINT "YOUR MOVE";:GOSUB 110
45 IF E=0 THEN 80
50 IF M=H THEN GOSUB 100
55 IF E=0 THEN 80
60 PRINT "MY MOVE IS ";:GOSUB 800
65 IF E=0 THEN 80
70 IF M=H THEN PRINT ",";:GOSUB 800
75 IF E>0 THEN 35
80 PRINT:PRINT"GAME OVER"
85 D=B(6)-B(13):IF D<0 THEN PRINT "I WIN BY";-D;"POINTS":GOTO 20
90 N=N+1:IF D=0 THEN PRINT "DRAWN GAME":GOTO 20
95 PRINT "YOU WIN BY";D;"POINTS":GOTO 20
100 PRINT "AGAIN";
110 M=-1:INPUT M:IF M<7 THEN IF M>0 THEN M=M-1:GOTO 130
120 PRINT "ILLEGAL MOVE": GOTO 100
130 IF B(M)=0 THEN 120
140 H=6:GOSUB 200
150 GOTO 500
200 K=M:GOSUB 600
210 E=0:IF B(6)>18 THEN RETURN
220 IF B(13)>18 THEN RETURN
230 IF K>6 THEN K=K-7
240 C=C+1:IF C<9 THEN F(N)=F(N)*6+K
250 FOR I=0 TO 5:IF B(I)<>0 THEN E=1
260 IF B(I+7)<>0 THEN E=1
270 NEXT:RETURN
500 PRINT:PRINT" ";:REM 3 SPACES
505 FOR I=12 TO 7 STEP -1:GOSUB 580
510 NEXT I
515 PRINT:I=13:GOSUB 580
520 PRINT" ";:PRINT B(6):PRINT " ";:REM 23 SPACES, THEN 3 SPACES
525 FOR I=0 TO 5:GOSUB 580
530 NEXT I
535 PRINT:PRINT:RETURN
580 IF B(I)<10 THEN PRINT " ";
585 PRINT B(I);:RETURN
600 P=B(M):B(M)=0
605 FOR P=P TO 1 STEP -1:M=M+1:IF M>13 THEN M=M-14
610 B(M)=B(M)+1:NEXT P
615 IF B(M)=1 THEN IF M<>6 THEN IF M<>13 THEN IF B(12-M)<>0 THEN 625
620 RETURN
625 B(H)=B(H)+B(12-M)+1:B(M)=0:B(12-M)=0:RETURN
800 D=-99:H=13
805 FOR I=0 TO 13:G(I)=B(I):NEXT I
810 FOR J=7 TO 12:IF B(J)=0 THEN 885
815 Q=0:M=J:GOSUB 600
820 FOR I=0 TO 5:IF B(I)=0 THEN 845
825 L=B(I)+I:R=0
830 IF L>13 THEN L=L-14:GOTO 830
832 IF L>5 THEN IF L<13 THEN R=R+1
835 IF B(L)=0 THEN IF L<>6 THEN IF L<>13 THEN R=R+B(12-L)+1
840 IF R>Q THEN Q=R
845 NEXT I
850 Q=B(13)-B(6)-Q:IF C>7 OR N=0 THEN 875
855 K=J:IF K>6 THEN K=K-7
860 FOR I=0 TO N-1:IF F(N)*6+K=INT(F(I)/6^(7-C)+.1) THEN Q=Q-2
870 NEXT I
875 FOR I=0 TO 13:B(I)=G(I):NEXT I
880 IF Q>=D THEN A=J:D=Q
885 NEXT J
890 M=A:PRINT CHR$(42+M);:GOTO 200
Oh, there's one bug (that I know of) still left in this code; I only thought of it while I was proofreading this post. Do you know what it is? Hint behind spoilers:
the computer's AI is making an incorrect assumption about the player's next move.