book

Land of Lisp

by Conrad Barski M.D.

November 2010

Intermediate to advanced

504 pages

12h 45m

English

No Starch Press

Read now

Unlock full access

What Makes Lisp So Cool and Unusual?
Lisp DialectsA Tale of Two LispsUp-and-Coming LispsLisp Dialects Used for ScriptingANSI Common Lisp
Installing CLISPStarting Up CLISP

The Guess-My-Number Game
Defining the small and big VariablesAn Alternative Global Variable Definition Function
Defining the guess-my-number FunctionDefining the smaller and bigger FunctionsDefining the start-over Function
Syntax and Semantics
SymbolsNumbersStrings
Code ModeData Mode
Cons CellsList FunctionsThe cons FunctionThe car and cdr FunctionsThe list FunctionNested Lists
The Symmetry of nil and ()Empty Equals FalseThe Four Disguises of ()
One Thing at a Time with ifGoing Beyond if: The when and unless AlternativesThe Command That Does It All: condBranching with case
Using the Stealth Conditionals and and orUsing Functions That Return More than Just the Truth
The Wizard's Adventure GameOur Game WorldBasic Requirements
How Quasiquoting WorksDescribing Multiple Paths at OnceFinding the Relevant EdgesConverting the Edges to DescriptionsJoining the Descriptions
Listing Visible ObjectsDescribing Visible Objects
Printing and Reading TextPrinting to the ScreenSaying Hello to the UserStarting with print and readReading and Printing Stuff the Way Humans Like It
Setting Up a Custom REPLWriting a Custom read FunctionWriting a game-eval FunctionWriting a game-print Function
What lambda Does
Exotic ListsDotted ListsPairsCircular ListsAssociation Lists
Visualizing Tree-like DataVisualizing Graphs
Generating the DOT InformationConverting Node IdentifiersAdding Labels to Graph NodesGenerating the DOT Information for the NodesConverting Edges into DOT FormatGenerating All the DOT DataTurning the DOT File into a PictureUsing ThunksWriting to a FileCreating a StreamUnderstanding Keyword ParametersCapturing the Console OutputCreating a Picture of Our Graph
The Grand Theft Wumpus Game
Generating Random EdgesLooping with the loop CommandPreventing IslandsBuilding the Final Edges for Congestion CityThe make-city-edges FunctionThe edges-to-alist FunctionThe add-cops Function
Drawing a City from Partial KnowledgeKnown NodesKnown EdgesThe mapcan FunctionDrawing Only the Known Parts of the CityWalking Around Town
ArraysWorking with ArraysUsing a Generic SetterArrays vs. Lists
Working with Hash TablesReturning Multiple ValuesHash Table PerformanceA Faster Grand Theft Wumpus Using Hash Tables
Working with StructuresWhen to Use Structures
Working with SequencesSequence Functions for SearchingSequence Functions for Iterating Across a SequenceTwo More Important Sequence FunctionsCreating Your Own Generic Functions with Type Predicates
Global Variables for the Player and MonstersMain Game FunctionsPlayer Management FunctionsHelper Functions for Player AttacksMonster Management FunctionsThe MonstersThe Generic MonsterThe Wicked OrcThe Malicious HydraThe Slimy Slime MoldThe Cunning BrigandTo Battle!
The loop MacroSome loop TricksCounting from a Starting Point to an Ending PointIterating Through Values in a Listdoing Stuff in a LoopDoing Stuff Under Certain ConditionsBreaking out of a Loop EarlyCollecting a List of ValuesUsing Multiple for ClausesEverything You Ever Wanted to Know About loop
Growing Plants in Our WorldCreating AnimalsAnatomy of an AnimalHandling Animal MotionHandling Animal TurningHandling Animal EatingHandling Animal ReproductionSimulating a Day in Our WorldDrawing Our WorldCreating a User InterfaceLet's Watch Some Evolution!Explaining the Evolution
Anatomy of the format FunctionThe Destination ParameterThe Control String ParameterValue Parameters
Control Sequences for Formatting IntegersControl Sequences for Formatting Floating-Point Numbers
Types of StreamsStreams by Type of ResourceStreams by DirectionOutput StreamsInput Streams
Socket AddressesSocket ConnectionsSending a Message over a SocketTidying Up After Ourselves
Sending Streams to FunctionsWorking with Long StringsReading and Debugging
Error Handling in Common LispSignaling a ConditionCreating Custom ConditionsIntercepting ConditionsProtecting Resources Against Unexpected Conditions
How a Web Server WorksRequest ParametersRequest Parameters for GET RequestsDecoding the Values of Request ParametersDecoding Lists of Request ParametersParsing the Request HeaderTesting get-header with a String StreamParsing the Request BodyOur Grand Finale: The serve Function!
Testing the Request HandlerLaunching the Website
What Is Functional Programming?
Code Composition with Imperative CodeUsing the Functional StyleHigher-Order Programming to the Rescue
Functional Programming Reduces BugsFunctional Programs Are More CompactFunctional Code Is More Elegant
The Rules of Dice of Doom
Defining Some Global VariablesRepresenting the Game BoardDecoupling Dice of Doom's Rules from the Rest of the GameGenerating a Game TreeCalculating Passing MovesCalculating Attacking MovesFinding the NeighborsAttackingReinforcementsTrying Out Our New game-tree FunctionPlaying Dice of Doom Against Another HumanThe Main LoopGiving Information About the State of the GameHandling Input from Human PlayersDetermining the WinnerTrying Out the Human vs. Human Version of Dice of Doom
The Minimax AlgorithmTurning Minimax into Actual CodeCreating a Game Loop with an AI PlayerPlaying Our First Human vs. Computer Game
ClosuresMemoizationMemoizing the neighbors FunctionMemoizing the Game TreeMemoizing the rate-position FunctionTail Call OptimizationSupport for Tail Calls in Common LispTail Call Optimization in Dice of DoomA Sample Game on the 3-by-3 Board
A Simple Lisp MacroMacro ExpansionHow Macros Are TransformedUsing the Simple Macro
A Macro for Splitting ListsAvoiding Repeated Execution in MacrosAvoiding Variable CaptureA Recursion Macro
What Is a Domain?
Creating XML and HTML with the tag MacroWriting a Macro Helper FunctionCreating the tag MacroUsing the tag Macro to Generate HTMLCreating SVG-Specific Macros and FunctionsBuilding a More Complicated SVG Example
Creating New Game Commands by HandA Command for WeldingA Command for DunkingThe game-action MacroLet's Try the Completed Wizard's Adventure Game!
Adding Lazy Evaluation to LispCreating the lazy and force CommandsCreating a Lazy Lists LibraryConverting Between Regular Lists and Lazy ListsMapping and Searching Across Lazy Lists
Trimming the Game TreeApplying HeuristicsWinning by a Lot vs. Winning by a LittleAlpha Beta Pruning
Drawing the Game Board Using the SVG FormatDrawing a DieDrawing a TileDrawing the Board
Writing Our Web Request HandlerLimitations of Our Game Web ServerInitializing a New GameAnnouncing a WinnerHandling the Human PlayerHandling the Computer PlayerDrawing the SVG Game Board from Within the HTML
Increasing the Number of Players
Building Chance NodesDoing the Actual Dice RollingCalling the Dice Rolling Code from Our Game EngineUpdating the AI
Functional Guild CruiserSynopsisHow It Kills BugsExplanationWeakness
SynopsisHow It Kills BugsExplanationWeakness
SynopsisHow It Kills BugsExplanationWeakness
SynopsisHow It Kills BugsExplanationWeakness
SynopsisExplanationWeakness
SynopsisHow It Kills BugsExplanationExplanationWeakness
SynopsisHow It Kills BugsExplanationWeakness
SynopsisHow It Kills BugsExplanationWeakness
SynopsisHow It Fights BugsExplanationWeakness
Lisp DialectSynopsisHow It Kills BugsExplanationWeakness

Content preview from Land of Lisp

Creating an Intelligent Computer Opponent

As we discussed when we were designing the game tree code for Dice of Doom, having a separate game tree generator makes it easy to add an AI player to a game engine. In fact, we’re now going to add a computer player that can play an absolutely perfect game with only 23 additional lines of code!

So how does an AI player decide to make a move? We’ll use the following strategy:

Look at each available move.
Give a point rating to the board position resulting from each move.
Pick the move with the maximum point rating.

This sounds like a simple plan, but there is one step in this algorithm that’s pretty tricky: calculating the best point rating for a given board position.

If a move leads immediately to a win, it’s ...