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