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!

TABLE OF CONTENTS:
  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
SEARCH DEV SHED

TOOLS YOU CAN USE

advertisement

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
   

PRACTICES ARTICLES

- 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: