Home arrow Practices arrow Page 9 - Solving Problems with Recursion

Trying it Out - Practices

Recursion is a way to solve a problem by...reducing it to the same problem. What? It may be counterintuitive, but many turn-based games (including chess) use exactly this technique to make a computer player "think." Mohamed Saad explains the concept, along with when (and when not) to use recursion in your programming. Check out the Connect4 example!

  1. Solving Problems with Recursion
  2. The Plot Thickens
  3. First Programming Example
  4. The Flood Fill Algorithm
  5. How it Works
  6. Connect 4 AI program
  7. The Minimax Method
  8. Placing Pieces
  9. Trying it Out
  10. Two More Tips
By: Mohamed Saad
Rating: starstarstarstarstar / 54
November 17, 2004

print this article



Whew, and that's it. Now we have a nice Connect 4 AI engine that can actually look several moves ahead, thanks to recursion. For example, if we try the engine on this position:

Solving Problems with Recursion

Fig 4. The AI (red player), will know how to win in this situation

If the program is called to play for the red player with a depth of only 3, it will correctly find that the best move is to put a piece in column 2 to force the human to block at column 5 and then the computer wins by putting a piece at column 5.

In another situation: 

Solving Problems with Recursion

Fig 5. If the computer (yellow player) could only see one step ahead, he would be unable to see the threat of playing at column 3 or 6 and winning. Now, it can detect and prevent it.

The computer correctly decides to play at column 3 to block the human from winning by putting at column 3 or 6.

Pretty impressive, huh? And it is all less than 30 lines of code.

>>> More Practices Articles          >>> More By Mohamed Saad

blog comments powered by Disqus
escort Bursa Bursa escort Antalya eskort


- Calculating Development Project Costs
- More Techniques for Finding Things
- Finding Things
- Finishing the System`s Outlines
- The System in So Many Words
- Basic Data Types and Calculations
- What`s the Address? Pointers
- Design with ArgoUML
- Pragmatic Guidelines: Diagrams That Work
- Five-Step UML: OOAD for Short Attention Span...
- Five-Step UML: OOAD for Short Attention Span...
- Introducing UML: Object-Oriented Analysis an...
- Class and Object Diagrams
- Class Relationships
- Classes

Developer Shed Affiliates


Dev Shed Tutorial Topics: