- Land of Lisp
- Acknowledgments
- Introduction
- I. Lisp is Power
- 1. Getting Started with Lisp
- 2. Creating Your First Lisp Program
- 3. Exploring the Syntax of Lisp Code
- II. Lisp is Symmetry
- 4. Making Decisions with Conditions
- 5. Building a Text Game Engine
- 6. Interacting with the World: Reading and Printing in Lisp
- 6.5. lambda: A Function So Important It Deserves Its Own Chapter
- 7. Going Beyond Basic Lists
- 8. This Ain't Your Daddy's Wumpus
- 9. Advanced Datatypes and Generic Programming
- III. Lisp is Hacking
- 10. Looping with the loop Command
- 11. Printing Text with the format Function
- Anatomy of the format Function
- Control Sequences for Printing Lisp Values
- Control Sequences for Formatting Numbers
- Printing Multiple Lines of Output
- Justifying Output
- Iterating Through Lists Using Control Sequences
- A Crazy Formatting Trick for Creating Pretty Tables of Data
- Attack of the Robots!
- What You've Learned
- 12. Working with Streams
- 13. Let's Create a Web Server!
- 13.5. Functional Programming Is Beautiful
- IV. Lisp is Science
- 14. Ramping Lisp Up a Notch with Functional Programming
- 15. Dice of Doom, a Game Written in the Functional Style
- The Rules of Dice of Doom
- A Sample Game of Dice of Doom
- Implementing Dice of Doom, Version 1
- Defining Some Global Variables
- Representing the Game Board
- Decoupling Dice of Doom's Rules from the Rest of the Game
- Generating a Game Tree
- Calculating Passing Moves
- Calculating Attacking Moves
- Finding the Neighbors
- Attacking
- Reinforcements
- Trying Out Our New game-tree Function
- Playing Dice of Doom Against Another Human
- Creating an Intelligent Computer Opponent
- Making Dice of Doom Faster
- What You've Learned
- 16. The Magic of Lisp Macros
- 17. Domain-Specific Languages
- 18. Lazy Programming
- 19. Creating a Graphical, Web-Based Version of Dice of Doom
- 20. Making Dice of Doom More Fun
- A. Epilogue
- Index
- About the Author
- Updates
In this chapter, we made the computer player for our Dice of Doom game much more sophisticated. We implementing the game tree using lazy lists, and applied several optimization techniques to limit the number of board positions that are searched by the AI engine. Along the way, you learned the following:
Lazy programming allows you to work with very large (and even infinite) data structures and do so efficiently.
Once you have a
lazymacro and aforcefunction, you can use them to build more sophisticated lazy operations, including building a lazy list library.Heuristics are imperfect algorithms that can be used to improve the performance of your code, with some creative thinking. In our example, we made some heuristic changes to how we score leaf nodes.
Once we converted Dice of Doom to use a lazy tree, we were able to elegantly trim the game tree in order to limit how deep the AI thinks when contemplating its moves.
Alpha-beta pruning lets us improve performance even more, by pruning branches that have no way of impacting the final scores on the moves being considered by the AI.
-
No Comment