Recursion Applied To "AI"
===========================
Artificial Intelligence (AI) is the Mount Everest of programming. Every
programmer really wants to make a program that learns and shows intelligence,
but no one has ever done it. To start off this article, there must be a defining
line between actual AI (evaluation and learning) and robotic response (reacting
to stimuli).
Imagine a space-fighting game. Just a simple 2D will do. There is the
player's spaceship, and then there is the computer-driven spaceship, and both
are trying to destroy the other. Though the computer-drive ship may be very good
at winning the game, it is simple robotic proceedures that govern it:
Move towards/Aim at the player's ship
If in range, shoot
If low shields or power, retreat
The robotic enemy typically does not do any evaluation of the player's
movements or strategy, and this is almost always good enough to make the game
challenging enough...but it is not artificial intelligence. It is responding to
the player's ship, and what it is doing at the moment and not learning how to be
a better fighter.
Some programs that have achieved a half-step towards artifical intelligence,
or at least artificial thinking, are chess and checkers games. To take the
easier example, let us consider a checkers program.
In the game of checkers, each state in the game has a limited number of
possibilities. For example, at the beginning of the game, there are only 4
possible moves, since there are only 4 pieces that are allowed to move. However,
the artifical thinking has to come into play when there are advantages and
disadvantages to each move that is made. This is also where recursion comes into
play (no pun intended). Each move that is made in a checkers game creates a
"multi-pronged fork-in-the-road" for the possibilies for moves after. With such
form of branching, a recursive function is the best way to handle and evaluate
each possible move, and eventually come up with a victory-inspired move.
Let's start in the simplest form of the recursive function. We have to
assume that the graphical interface for the game is already set up, and that
each piece is numbered or otherwise at least has an identity. The function must
(for the computer player's side):
Determine how many possible moves there are
Call this recursive routine once for each possibility.
Of course, there must be some way of passing the function the layout of the
board, without actually changing the layout that the player actually sees. One
possible way would be to pass the function 25 variables, one for each piece,
plus one more for who's turn it is. Each variable would indicate a piece's
location with a number. If the piece has been taken, then that piece's variable
could be 0, otherwise a number from 1 to 32, since that is the number of
possible places that a piece could be. 64 squares on the board, but only one
color is ever used.
The recursive function would, upon receiving the "coordinates" of each
piece, figure out every possible move that can be done by the player who's turn
it is, whether computer of human. The function would call each one of those
possibilities by calling itself. The parameters that the function would send
itself are the parameters it received, but with one variable changed- the
variable of the piece that is to be evaluated.
So, in short, the recursive function figures out all possible moves, makes a
list of them, then calls the function (itself) for each one of those possible
moves. Of course, until the end of the game, the first move in the list that the
function has compiled will call another recursion of itself, but when there are
no more possible moves, the recursion loops will be broken, and the program flow
will eventually return to the main program where the function was first called.
Determine the possible moves for the current player
Call this function for possible move #1
Call this function for possible move #2
Call this function for possible move #3
Call this function for possible move #n
The condition that breaks the loop is when all pieces of one color are
taken. If the method mentioned previously is used (24 variables, one for each
piece), all variables indicating one players pieces are gone. Now, the way a
function works is that it must return a single value. Since there is a single
condition that breaks the loop, that is where the return value is set. When the
recursive function reaches an "end game" point (when all of either player is
gone), if the winner is the computer, then the function would return an
indication that this is good, say a 1. If the winner is the player, then it
would return a bad indication, say a 0.
Determine the possible moves for the current player
Call this function for possible moves
If there are no possible moves, then
If all computer's pieces are taken, return 0
If all player's pieces are taken, return 1
There is only one way that the function would only have one move available
in the list of moves. This is if there is a required move, such as a forced
capture, or if there is only one move that the player can make, due to physical
restraint. In these cases, the recursive routine works, but there are no
multiple pathways.
When the recursive function has completed evaluating every possible move
from its point of view (from its current board layout), then a decision can be
made simply. Since each evaluation returns a number, take those numbers and add
them together. The total should then be the return value of the function.
Determine the possible moves for the current player
Call this function for possible moves
If there are no possible moves, then
If all computer's pieces are taken, return 0
If all player's pieces are taken, return 1
If there are possible moves
Add up the numbers returns by the evaluated moves
Return that value (instead of 0 or 1)
Now you must actually implement this recursive function into the main
program, since it must be called. Basically, you must copy the code from the
recursive function into the main program in order to call it. The reason for
this is because you must start by figuring out how many possible moves there
are, then call the function for each possible move from the current layout. The
reaosn you cannot simply call the function is because of a little extra coding:
The function returns a number for each proposed move. Since one move is bound to
produce more possibilities of winning than the others, the move that returns the
highest value is the best move to take. This cannot be programmed into the
recursive function, since the function should not be allowed to affect the
actual playing board. If there is a tie between the numbers returned, just
choose the first or last of the moves proposed, it doesn't make a difference.
That is the basic way that recursion is used to create a "thinking" computer
player for a game of checkers. Obviously this does not include the possibilities
of crowning, since the recursive function would have to be sent additional
parameters indicating if a piece was crowned or not, so that it knows what
possible moves it has. But this is the basis for how what some people call
artifical intelligence works. It uses recursion to consider every possible move,
consider the best move to make, and make it.
Recursion is a wonderful tool for creating this kind of half-intelligence-
half-robotic-reaction, but it still is not true AI. What is involved with true
artificial intelligence is a combination of extreme evaluation (thinking) and
storage and useage of data (learning). So, how is that done? Wait for the next
article...!
- Written by Jack Thomson
for the QBasic Station