ARTIFICIAL
INTELLIGENCELiberty Basic is develeopped by Carl Gundel Original Newsletter compiled by Alyce Watson Translation to HTML: Raymond Roumeas
- Hubert Humphrey
ARTIFICIAL
INTELLIGENCEComputers can do only those things that we program them to do. They cannot think or reason on their own. We can create different types of programs that simulate the ability to think as a human brain thinks. This subject is very complex and involved, and we'll just touch on a few of the simpler aspects here.
In an arcade game, the bad guys can move in a preset pattern, or in a random fashion. If they do, they have no intelligence at all. We can program them to evaluate conditions and appear to be intelligent. The "smarter" the bad guy in the game, the more closely and often he evaluates the conditions before making his moves. If the goodguy X is less than the badguy X, the badguy can decrease his X location with his next move. If he is shooting, rather than moving, he can shoot towards a lesser X location. If the goodguy X is larger than the badguy X, then the badguy increases his X. If he does this often, or in large increments, he is very smart and difficult to defeat! Of course, he will evaluate both X and Y positions, and possibly speed and direction of motion with each move.
If you have ever played the arcade game, Pacman, you have noticed that the ghosts start out moving in a pattern and as the game progresses, their movements become less random and they start chasing Pacman more and more energetically. This is a good example of this type of game intelligence.
Text adventure games and computer chat-type programs require parsing of user text input. If a certain key word or words are found, the program responds with a set answer or action. Notice that the program evaluates key words, or perhaps short phrases. It would be impossible to guess the exact syntax of every possible user input, so as to have a ready response.
Imagine that you are constructing a chat program, in which the user types comments to the computer, and the computer answers. A user might make a comment about the weather. If we tried to trap every possible way for the user to comment about the weather, we'd fail miserably, and we'd also create a huge program file! It might look something like this:
if comment$="How is the weather?" then [weatherResponse} if comment$="How's the weather?" then [weatherResponse} if comment$="Do you like the weather?" then [weatherResponse} if comment$="Do you like this weather?" then [weatherResponse} if comment$="I hate the weather!" then [weatherResponse} if comment$="What is the weather forecast?" then [weatherResponse} if comment$="What will the weather be tomorrow?" then [weatherResponse} if comment$="Is it raining?" then [weatherResponse} if comment$="Will it rain?" then [weatherResponse} if comment$="I HATE RAIN!" then [weatherResponse} if comment$="When will it snow?" then [weatherResponse} if comment$="Do you like snow?" then [weatherResponse} if comment$="What is the weather today?" then [weatherResponse} if comment$="Is it cloudy?" then [weatherResponse} if comment$="My garden needs rain." then [weatherResponse} if comment$="Can you forecast the weather?" then [weatherResponse} if comment$="What date will see the first snow here?" then [weatherResponse} if comment$="This weather stinks!" then [weatherResponse} if comment$="I want to play in the snow." then [weatherResponse} if comment$="Will the weather be nice for the race?" then [weatherResponse} if comment$="What is tomorrow's weather report?" then [weatherResponse} if comment$="Will you predict the weather?" then [weatherResponse} if comment$="will you predict the weather" then [weatherResponse} if comment$="predict the weather" then [weatherResponse} if comment$="weather?" then [weatherResponse} if comment$="the weather?" then [weatherResponse} if comment$="weather is??" then [weatherResponse} ... ... ... if comment$="Do you like baseball"" then [baseballResponse] ... ... goto [loop] [weatherResponse] notice "I can't tell you the weather!" goto [loop]
That was but a tiny sampling, but you get the idea! Okay, we clearly need to identify some keywords, like weather, rain and snow. We could parse the words in the user comment, using the word$() function. We could also use the instr() function. Let's try out the instr() version:
if instr(comment$,"rain")>0 then [weatherResponse] if instr(comment$,"snow")>0 then [weatherResponse] if instr(comment$,"weather")>0 then [weatherResponse]
Hey, that looks better! Wait a minute. What would happen if the user comment was like the one above: I HATE RAIN! Unfortunately, "RAIN" and "rain" are not the same! That problem is easy to fix, though, with the lower$ (or upper$) function. We simply need to convert the user's comment to all lower case, then do the evaluation:
comment$=lower$(comment) if instr(comment$,"rain")>0 then [weatherResponse] if instr(comment$,"snow")>0 then [weatherResponse] if instr(comment$,"weather")>0 then [weatherResponse]
We've simplified the coding quite a bit, but we can do even better. We can put the keywords into arrays, and put the replies into matching arrays. This can get quite complicated, depending upon the complexity and scope of the program. We'll use a simple example. We'll set up an array of keywords, called keys$() It will be double dimensioned. We'll have an array of replies, whose members match the keywords in the keys$() array.
We'll make this really small, for the sake of the demonstration:
dim keys$(2,2) dim replies$(2)
We can fill keys$(0,1) and keys$(0,2) with keywords that might be typed by a user. We can fill replies$(0) with the response that matches those keywords. Let's start with the obvious -- a possible reference to Liberty BASIC by the user, and the matching response:
keys$(0,1)="liberty basic" keys$(0,2)="lb" replies$(0)="Liberty BASIC is my favorite language!" For this demo, let's also use the "hi" and "bye" greetings: keys$(1,1)="hello" keys$(1,2)="hi" replies$(1)="Hello to you also!" keys$(2,1)="goodbye" keys$(2,2)="bye" replies$(2)="Goodbye. It's been nice chatting with you."
A real program would require many more keys and replies, of course.
When the user hits an "Ask" button, we'll retrieve the contents of the textbox, and convert them to lower case for evaluation purposes:
print #ask.text1, "!contents?"
input #ask.text1, msg$
msg$=lower$(msg$)
Since we've placed our keywords and replies in matching arrays, we can evaluate them easily in a FOR/NEXT loop. If we find a match to a keyword by using instr(), then we give the user the corresponding reply. We also set a flag, so that when we are done evaluating all possibilities, we can give the user a stock response if no keyword was found.
for j = 0 to 2
if instr(msg$,keys$(j,1)) > 0 _
or instr(msg$, keys$(j,2)) > 0 then
notice replies$(j)
j = 2
foundflag = 1
end if
next j
Here, if no keyword matches what the user has typed, the computer responds with, "I don't understand!"
if foundflag = 0 then
notice "I don't understand!"
end if
After the computer gives its answer, we clear the textbox, resetting focus so that the next keyboard input is directed to the textbox:
print #ask.text1, "" 'erase text box
print #ask.text1, "!setfocus"
If our array of keywords held more than 2 possibilities for each type, we would want to evaluate in a nested loop. In the following example, there are 200 keys, and each one has 20 possibilites. In our weather example, this would give us 20 words to evaluate, and could include weather, cloud, rain, snow, storm, flood, blizzard, etc. Also, this example would provide 200 categories for replies, so in addition to WEATHER, we could have LOVE, JOB, SCHOOL, MILITARY, GOVERNMENT, TELEVISION, MOVIES, MUSIC, etc. etc.
etc., each with 20 possible keywords.
DIM keys$(200, 20)
for j = 0 to 200
for k = 0 to 20
if instr(msg$,keys$(j,k)) > 0 then
notice replies$(j)
j = 200 : k = 20 'set counter to max
foundflag = 1
end if
next k
next jNotice also that we have made the chat window a dialog window. This allows us to set a default button. When the user pushes ENTER, it is the same as if he has pressed the default button. This allows the user to chat with the computer without removing his hands from the keyboard to use the mouse.
button #ask.default, "Ask Me Now!", [button1.click], UL, 185, 55, 113, 25
Here is the little demo. Feel free to expand it, or create a better one of your own and share it with the group! One possible improvement: write the keys and replies into a text file and load the arrays from that file at runtime.
'artificial intelligence chat program
dim keys$(2,2)
dim replies$(2)
keys$(0,1)="liberty basic"
keys$(0,2)="lb"
replies$(0)="Liberty BASIC is my favorite language!"
keys$(1,1)="hello"
keys$(1,2)="hi"
replies$(1)="Hello to you also!"
keys$(2,1)="goodbye"
keys$(2,2)="bye"
replies$(2)="Goodbye. It's been nice chatting with you."
NOMAINWIN
WindowWidth = 315 : WindowHeight = 170
menu #ask, "&File" , "E&xit", [quit]
menu #ask, "&Help" , "&About", [about]
button #ask.default, "Ask Me Now!", [button1.click], UL, 185, 55, 113, 25
button #ask.button2, "Quit", [quit], UL, 185, 85, 113, 25
textbox #ask.text1, 5, 25, 296, 24
Open "Ask Me" for Dialog_nf as #ask
print #ask.default, "!font ms_sans_serif 0 18"
print #ask.button2, "!font ms_sans_serif 0 18"
print #ask.text1, "!font ms_sans_serif 0 18"
[loop]
input aVar$
[quit]
close #ask : END
[about]
NOTICE "Copyright 2000"
goto [loop]
[button1.click]
'place code here
foundflag = 0
print #ask.text1, "!contents?"
input #ask.text1, msg$
msg$=lower$(msg$)
for j = 0 to 2
if instr(msg$,keys$(j,1)) > 0 _
or instr(msg$, keys$(j,2)) > 0 then
notice replies$(j)
j = 2
foundflag = 1
end if
next j
if foundflag = 0 then
notice "I don't understand!"
end if
print #ask.text1, "" 'erase text box
print #ask.text1, "!setfocus"
goto [loop]In a more complicated type of intelligence, the program can be aware of certain rules of the game. One example is the moves in Tic Tac Toe, and another is the moves in a game of chess. When it is the computer's turn, it can refer to the rules of movement and check each possible move that it is allowed to make. It can go from each of THOSE moves and evaluate the NEXT possible moves, both for itself and for its opponent. It can look into the future and determine the most likely outcome, whether good or bad, for each of its possible moves on this turn. The further it looks into the future, the smarter it is! This type of program is well beyond the abilities of the author to write, or even comment on. Sorry!
Liberty BASIC ships with a Tic Tac Toe game, so check it out!
The closest thing to true artificial intelligence that we'll discuss in this article is the method that allows the computer to learn as the program progresses. Again, the author is not equipped to discuss this type of programming algorithm, but Ryan Jeffords can help us out. He has created a game in which the user can choose the intelligence of the computer opponent, by allowing it to learn by playing games -- 1 test game producing a dumb opponent, and 500 test games producing a smart opponent.
The code here is very well documented and clearly explained. There is an attachment to this newsletter that contains a set of html documents written by Ryan to further explain the Nim code, and the Monticello algorithm that it uses. If you find this demo to be interesting or useful, please tell Ryan! Contact him:
mailto:jeffords@b...
Thanks, Ryan!
NIM BY RYAN JEFFORDS
' Artificial Intelligence demo -- the game of Nim
' by Ryan Jeffords jeffords@b... copyright 1999
'
' FYI:
' Without pointers, AI is tough to do in LB. However, with some creative
' programming it is possible.
'
'
'
'** Initialize variables
' you can adjust the number of sticks and the
' max number of moves by adjusting the numSticks, maxSticks variables
' and the two arrays.
'---------------------------------------------------------------------
numSticks=17 'Number of sticks we are playing with
maxSticks=3 'Max number of sticks to be removed
DIM a(17,3) 'Holds the move table a(NUMBER OF STICKS, MAX NUMBER OF MOVES)
DIM player(17) 'Holds the moves made during the game player(NUMBER OF STICKS)
'** MAIN LOOP OF NIM
'-------------------------------
[mainLoop]
Gosub [BuildBrains]
'UNCOMMENT THE NEXT LINE IF YOU JUST WANT TO SEE THE PROBABILITY TABLES
'Gosub [ShowBrains]
Gosub [GetSmart]
'UNCOMMENT THE NEXT LINE IF YOU JUST WANT TO SEE THE PROBABILITY TABLES
'Gosub [ShowBrains]
GOSUB [PlayRealGame]
END ' Exit the program
[BuildBrains]
'** BUILD THE INITIAL MOVE TABLE
'** COMPUTER IS BASICALLY AS SMART
'** AS A RANDOM NUMBER GENERATOR
'-------------------------------
' This table shows all valid moves
' and is used for considering what
' move to make.
'
' The higher the percentage, the more
' likely that move should be made
'-------------------------------
FOR tempRow=numSticks TO 1 Step -1
a(temprow,0)=0 'Zero sticks is not an option
FOR tempCol = 1 TO maxSticks
If tempRow>=maxSticks then
a(tempRow,tempCol) = 1 / maxSticks
Else
a(tempRow,tempCol)= 1 / tempRow
End If
If tempCol > tempRow then a(tempRow,tempCol)=0
NEXT tempCol
NEXT tempRow
RETURN
[ShowBrains]
'** PRINT THE MOVE TABLE
'------------------------------------------
' Displays the move table, showing what
' the probability of making a move is
' given a number of sticks.
'------------------------------------------
CLS
Print "Here's my ideas of good game moves"
Print "based on the number of sticks left"
'TEXT FORMATTING STUFF
'---------------------
Print
Print "Sticks ";
for tempCounter=1 to maxSticks
print "Probability ";
next tempCounter
print
print " ";
for tempCounter=1 to maxSticks
print "of move " + str$(tempCounter) + " ";
next tempCounter
print
print "==========";
for tempCounter=1 to maxSticks
print "===============";
next tempCounter
print
'ACTUAL DATA
'-----------
FOR tempRow=numSticks TO 1 Step -1
tmpValue=0
Print " " + using("##",tempRow) + " ";
FOR tempCol = 1 TO maxSticks
tmpValue=tmpValue + a(tempRow,tempCol)
Print using("###", a(tempRow,tempCol)*100); "% ";
NEXT tempCol
print
NEXT tempRow
Print:Print"Press <ENTER> TO continue ";
INPUT TEMP$
RETURN
[GetSmart]
' ALLOW NIM TO GET SMARTER
'--------------------------------------------
' This is the part where NIM teaches himself/herself
' how to win.
'--------------------------------------------
CLS
Print "How smart of a competitor do you want?"
Print "CHOICE (1-500)";
INPUT learningGames
FOR tempCounter = 1 TO learningGames
gameSticks=numSticks
CLS: print "Learning game " + STR$(tempCounter) + " of " +
str$(learningGames)
' RESET GAME VECTOR
' -----------------
' Game vector is used to keep track
' of both players moves durring the game.
' ------------------------------------
For tempLoop=1 to numSticks
player(tempLoop)=0
next tempLoop
' GET MOVE WHILE STICKS ARE LEFT
' ------------------------------
while gameSticks>0
'GET MOVE AND UPDATE VALUES ACCORDINGLY
gosub [GetCompMove] 'Get the computers move
player(gameSticks)=CompMove 'Store the move in the move vector
gameSticks=gameSticks - CompMove 'Subtract the computers move
from the number of sticks available
wend
' UPDATE THE MOVE TABLE
' ---------------------
' Because we kept track of the moves durring the
' game, we know what moves the WINNER made based upon the
' number of sticks left, and what moves the LOSER made based
' upon the number of sticks left. (The LOSER made the last
' move... So we will start out with a NEGATIVE weight)
'
' NOTE: The weight determines what percentage, the move table
' is adjusted. Too high a weight will cause the table to fluctuate
' too wildly and increase learn time. Too low will take the
computer
' a very, very long time to learn.
'
' We are going to increase the probability of selecting the
' WINNING number of sticks, based upon the number of sticks left
' by a pre-defined weight. We are also going to decrease the
' probability of selecting the LOSING number of sticks, based upon
' the number of sticks left.
'
' i.e., The Winner selected 3 Sticks when there were 4 sticks left.
' So we would increase the probability of selecting 3, when
' there are 4 sticks left.
'
' i.e., The Loser selected 2 Sticks when there were only 2
sticks left.
' So we would decrease the probability of selecting 2 when there
' are only 2 sticks left.
'
Weight= -.05 'Because the first player lost... use a negative weight
for tempUpdate=1 to numSticks
move=player(tempUpdate)
' If MOVE=0 then no one made a move when
' there were that many sticks left.
'
' i.e, if player(5)=0, then no one took any sticks when there
' were only 5 sticks left.
if move>0 then
tempValue=a(tempUpdate,player(tempUpdate)) 'Get current move
value from the move table
tempValue=tempValue + (tempValue * Weight) 'Calculate the new
move value
a(tempUpdate,player(tempUpdate))=tempValue 'Update the move
table
Weight=Weight*-1 'Toggle Weight Value (+/-)
end if
next tempUpdate
' NORMALIZE MOVE TABLE
' --------------------
' We now have a move table that
' adds up to over 100% so we need
' to adjust it so that it adds back up
' to 100%.
'
' We are going to add the values for that move
' Then divide each value by the max value for that
' move.
for tempUpdate = 1 to numSticks
tmpMax=0
'Sum of all values for that move
for tempResult=1 to maxSticks
tempValue=a(tempUpdate,tempResult)
a(tempUpdate,tempResult)=int(tempValue*100)/100
tempValue=a(tempUpdate,tempResult)
tmpMax=tmpMax+tempValue
next tempResult
'Normalize each value based upon 100%
for tempResult=1 to maxSticks
tempValue=a(tempUpdate,tempResult)
tempValue=tempValue/tmpMax
a(tempUpdate,tempResult)=tempValue
next tempResult
next tempUpdate
NEXT tempCounter
RETURN
[GetCompMove]
' DETERMINES THE BEST MOVE BASED UPON THE
' MOVE TABLE
'--------------------------------------------
' Generates a random number between 0 and 1
' Determines where within the probability
' table the percentage falls.
'
' As the game becomes smarter,
' Certain moves will have a higher probability
' of being selected. These are considered the
' smarter moves.
'--------------------------------------------
CompRandom=rnd(1)'The random number
CompMove=0 'Preset to null
ProbMove=0 'Probability of that move
for moveCounter=1 to maxSticks 'Cycle through stick options
if ((CompRandom>ProbMove) AND (CompRandom<=ProbMove +
a(gameSticks,moveCounter))) then
CompMove=moveCounter 'This is the computers move
end if
ProbMove=ProbMove+ a(gameSticks,moveCounter)
next moveCounter
return
[PlayRealGame]
WINS=0
GAMES=0
whoseMove=-1
CLS
PRINT "NIM"
PRINT "=================================================================="
PRINT "There are "+STR$(numSticks)+" sticks in a pile and we each take
turns"
PRINT "pulling sticks out of this pile until there are no "
PRINT "more sticks left to take."
PRINT
PRINT "The person who takes the last stick loses."
PRINT
PRINT "To keep things interesting, we can only take up to "+str$(maxSticks)
PRINT "sticks on any one move."
PRINT
[RealGameStart]
PRINT "Would you like to go first (Y/N)";
INPUT ANSWER$
IF ANSWER$="Y" or ANSWER$="y" then whoseMove=1 else whoseMove=-1
CLS
gameSticks=numSticks
while gameSticks>0
PRINT
PRINT "There are "+str$(gameSticks)+" sticks left"
If whoseMove=1 then
GOSUB [GetMove]
Else
GOSUB [GetCompMove]
PRINT "My Move! I will take "+str$(CompMove)+" sticks."
ProbMove=CompMove
End If
gameSticks=gameSticks-ProbMove 'Subtract current move from number left
whoseMove=whoseMove*-1 'Toggle whose turn it is.
wend
'Update Wins and Games played values
PRINT
GAMES=GAMES+1
if whoseMove<0 then
Print "I Win! Better luck next time!"
else
PRINT "Congratulations! You WON!"
WINS=WINS+1
end if
PRINT
PRINT "Total number of games played: "+STR$(GAMES)
PRINT "Number of games won: "+STR$(WINS)
PRINT
PRINT "Would you like to play again (Y/N)";
INPUT ANSWER$
IF ANSWER$="Y" or ANSWER$="y" then goto [RealGameStart]
RETURN
[GetMove]
'GETS THE USERS MOVE
'-------------------
'Determine the largest legal move
if gameSticks<maxSticks then
humanMove=gameSticks
else
humanMove=maxSticks
end if
ProbMove=0
while ProbMove=0
PRINT "How many sticks (1 - " + STR$(humanMove) +") ";
INPUT legalMove$
legalMove=val(legalMove$)
if legalMove>0 and legalMove<=humanMove then ProbMove=legalMove
wend
returnThanks Brandon Watts for the following article on program design. Contact Brandon: Brandon Watts http://www.wattsware.com brandonwatts@g...
Believe it or not, design is one of the most important factors in programming. The first thing most users will look at in a program is the design. Design can have a major affect on your product. For example, the U.S.S. Vincennes shot down an Iranian airplane mostly because the crew was confused by the way the data was presented on the screen! Most likely a flaw in your design will not have this strong of an effect. So how do you go about making better designs? Here are some general suggestions.
Ask the consumer what they want in a GUI. After all the consumer is the one who is going to have to put up with your product. Make it a pleasant experience for them. As I mentioned earlier, success or failure will depend on the design, as well as other factors.
Another thing you can do is check out the programs in your category that have been successful. I am not telling you to copy them by any means, just look at the way that they designed their program.
Keep it simple. Do not burden the user with so many features that they feel like they have been overloaded. Since you designed the program, you will probably find your way around the program easily. However the user will be lost. Remember the user is your number one priority.
Last of all, I would suggest that you take a look at the book: GUI Bloopers. It has so many wonderful principles to go by. It shows programs that have been successful, and some that have not. They go through the program step by step showing you what was good and bad about the product.
Brandon Watts http://www.wattsware.com brandonwatts@g...
Comments, requests or corrections: Hit 'REPLY' now! Dean Hodgson -- mailto:Hodgson.Dean@saugov.sa.gov.au Alyce Watson -- mailto:awatson@wctc.net