The Recursive Algorithm

Define a function (program), 'PICK BEST NEXT STEP.' The function returns a value of 'SUCCESS" (we've solved the problem) or 'FAILURE" (we didn't solve it). If it returns with a value of SUCCESS, then the function also returns the sequence of selected steps that solved the problem. PICK BEST NEXT STEP does the following:

PICK BEST NEXT STEP Routine Begins Here:

• Determine if the program can escape from continued recursion at this point. This bullet and the next two bullets deal with this escape decision. First, determine if the problem has now been solved. Since this al to PICK BEST NEXT STEP probably came from the program calling itself, we may now have a satisfactory solution. Examples are:
• In the context of a game (e.g., chess), the last move allows us to win(e.g., checkmate).
• In the context of solving a mathematical theorem, the last step provesthe theorem.
• In the context of an artistic program (e.g., cybernetic poet or com- poser), the last stop matches the goals for the next word or note.

If the problem has been satisfactorily solved, the program returns with a value of SUCCESS. In this case, PICK BEST NEXT STEP also returns the sequence of steps that caused the success.

- If the problem has not been solved, determine if a solution is now hopeless. Examples are:

(i) In the context of a game (e.g., chess), this move causes us to lose (e.g., checkmate for the other side).

(ii) In the context of solving a mathematical theorem, this step violates the theorem.

(iii) In the context of an artistic program (e.g., cybernetic poet or com- poser), this step violates the goals for the next word or note.

If the solution at this point has been deemed hopeless, the program returns with a value of FAILURE.

• If the problem has been neither solved nor deemed hopeless at this point of recursive expansion, determine whether or not the expansion should be abandoned anyway. This is a key aspect of the design and takes into consideration the limited amount of computer time we have to spend. Examples are: -

(i) In the context of a game (e.g., chess), this move puts our side sufficiently "ahead" or "behind." Making this determination may not be straightforward ans is the primary design decision. However, simple approaches, e.g., adding up piece values) can still provide good results. If the program determines that our side is sufficiently ahead, then PICK BEST NEXT STEP returns in a similar manner to a determination that our side has won (i.e. with a value of success). If the program determines that our side is sufficiently behind, then PICK NEXT BEST STEP returns in a similar manner to a determination that our side has lost (i.e., with a value of FAILURE).

(ii) In the context of solving a mathematical theorem, this step involves determining if the sequence of steps in the proof are unlikely to yeild a kproof. If so, then this path should be abandoned, and PICK BEST NEXT STEP returns in a similar manner to a determination that this step violates the theorem (i.e. with a value of FAILURE). There is no "soft" equivalent of success. We can't return with a value of SUCCESS until we have actually solved the problem. That's the nature of math.

(iii) In the context of an artistic program (e.g., cybernetic poet or composer), this step involves determining if the sequence of steps (e.g., words in a poem, notes in a song) is unliekly to satisfy the goals for the next step. If so, then this path should be abandoned, and PICK BEST NEXT STEP returns in a similar manner to a determination that this step violates the goals for the next step[ (i.e., with a value of FAILURE).

• If PICK BEST NEXT STEP has not returned (because the program has neither determined success nor failure nor made a determination that this path should be abandoned at this point), then we have not escaped from continued recursive expansion. In this case, we now generate a list of all possible next steps at this poitn. This is where the precise statement of the problem comes in.

(i) In the context of a game, this involves generating all possible moves for our side for the current state of the board.

(ii) In the contedt of finding a proof for a mathematical theorem, this involves listing th epossible axioms or previously proved theorems that can be applied at this point.

(iii) In the context of a cybernetic art program, this involves listing the possible words/notes/line segments that could be used at this point.

For each possible next step:

(i) Create the hypothetical situation that would exist if this step were implemented. In a game, this means the hypothetical state of the board. In mathematics, this means adding this step to the proof. In art, this means adding a word/note/line segment.

(ii) Now call PICK BEST NEXT STEP to examine this hypothetical situation. This is, of course, where the recursion comes in because the program is now calling itself.

(iii) If the above callto PICK BEST NEXT STEP returns with a value of

SUCCESS, then return from the call to PICK BEST NEXT STEP (that we are now in), also with a value of SUCCESS. Otherwise consider the next possible step.

If all the possible next steps have been considered without finding a stop that resulted in a return from the call to PICK BEST NEXT STEP with a value of SUCCESS, then return from this call to PICK BEST NEXT STEP (that we are now in) with a value of FAILURE.

END OF PICK BEST NEXT STEP

If the original call to PICK BEST NEXT STEP returns with a value of SUCCESS, it will also return the correct sequence of steps:

(i) In the context of a game, the first step in this sequence is the next move you should make.

(ii) In the context of a mathematical proof, the full sequence of steps is the proof.

(iii) In the context of a cybernetic art program, the sequence of steps is your work of art.

If the original call to PICK BEST NEXT STEP is FAILURE, then you need to go back to the drawing board.

Key Design Decisions

In the simple schema above, the designer of the recursive algorithm needs to determine the following at the outset:

• The key to a recursive algorithm is the determination in PICK BEST NEXT STEP when to abandon the recursive expansion. This is easy when the program has achieved clear success (e.g., checkmate in chess, or the requisite solution in a math or combinatorial problem) or clear failure. It is more difficult when a clear win or loss has not yet been achieved. Abandoning a line of inquiry before a well-defined outcome is necessary because otherwise the program might run for billions of years (or at least until the warranty on your computer runs out).

• The other primary requirement for the recursive algorithm is a straight- forward codification of the problem. In a game like chess, that's easy. But in other situations, a clear definition of the problem is not always so easy to come by.