1

Python code for

Artificial Intelligence
Foundations of Computational Agents

David L. Poole and Alan K. Mackworth

Version 0.9.12 of February 13, 2024.

https://aipython.org https://artint.info
©David L Poole and Alan K Mackworth 2017-2024.
All code is licensed under a Creative Commons Attribution-NonCommercial-
ShareAlike 4.0 International License. See: https://creativecommons.org/licenses/
by-nc-sa/4.0/deed.en
This document and all the code can be downloaded from
https://artint.info/AIPython/ or from https://aipython.org
The authors and publisher of this book have used their best efforts in prepar-
ing this book. These efforts include the development, research and testing of
the theories and programs to determine their effectiveness. The authors and
publisher make no warranty of any kind, expressed or implied, with regard to
these programs or the documentation contained in this book. The author and
publisher shall not be liable in any event for incidental or consequential dam-
ages in connection with, or arising out of, the furnishing, performance, or use
of these programs.

https://aipython.org Version 0.9.12 February 13, 2024

Contents

Contents 3

1 Python for Artificial Intelligence 9

1.1 Why Python? . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.2 Getting Python . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.3 Running Python . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.4 Pitfalls . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.5 Features of Python . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.5.1 f-strings . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.5.2 Lists, Tuples, Sets, Dictionaries and Comprehensions . . 12
1.5.3 Functions as first-class objects . . . . . . . . . . . . . . . . 13
1.5.4 Generators . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.6 Useful Libraries . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.6.1 Timing Code . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.6.2 Plotting: Matplotlib . . . . . . . . . . . . . . . . . . . . . 16
1.7 Utilities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
1.7.1 Display . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
1.7.2 Argmax . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.7.3 Probability . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
1.8 Testing Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

2 Agent Architectures and Hierarchical Control 25

2.1 Representing Agents and Environments . . . . . . . . . . . . . 25
2.2 Paper buying agent and environment . . . . . . . . . . . . . . 27
2.2.1 The Environment . . . . . . . . . . . . . . . . . . . . . . . 27
2.2.2 The Agent . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

3
4 Contents

2.2.3 Plotting . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.3 Hierarchical Controller . . . . . . . . . . . . . . . . . . . . . . . 31
2.3.1 Environment . . . . . . . . . . . . . . . . . . . . . . . . . 31
2.3.2 Body . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
2.3.3 Middle Layer . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.3.4 Top Layer . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
2.3.5 Plotting . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

3 Searching for Solutions 41

3.1 Representing Search Problems . . . . . . . . . . . . . . . . . . 41
3.1.1 Explicit Representation of Search Graph . . . . . . . . . . 43
3.1.2 Paths . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
3.1.3 Example Search Problems . . . . . . . . . . . . . . . . . . 47
3.2 Generic Searcher and Variants . . . . . . . . . . . . . . . . . . . 53
3.2.1 Searcher . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
3.2.2 GUI for Tracing Search . . . . . . . . . . . . . . . . . . . . 55
3.2.3 Frontier as a Priority Queue . . . . . . . . . . . . . . . . . 59
3.2.4 A∗ Search . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
3.2.5 Multiple Path Pruning . . . . . . . . . . . . . . . . . . . . 62
3.3 Branch-and-bound Search . . . . . . . . . . . . . . . . . . . . . 64

4 Reasoning with Constraints 69

4.1 Constraint Satisfaction Problems . . . . . . . . . . . . . . . . . 69
4.1.1 Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
4.1.2 Constraints . . . . . . . . . . . . . . . . . . . . . . . . . . 70
4.1.3 CSPs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
4.1.4 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
4.2 A Simple Depth-first Solver . . . . . . . . . . . . . . . . . . . . 83
4.3 Converting CSPs to Search Problems . . . . . . . . . . . . . . . 84
4.4 Consistency Algorithms . . . . . . . . . . . . . . . . . . . . . . 86
4.4.1 Direct Implementation of Domain Splitting . . . . . . . . 89
4.4.2 Consistency GUI . . . . . . . . . . . . . . . . . . . . . . . 91
4.4.3 Domain Splitting as an interface to graph searching . . . 93
4.5 Solving CSPs using Stochastic Local Search . . . . . . . . . . . 95
4.5.1 Any-conflict . . . . . . . . . . . . . . . . . . . . . . . . . . 97
4.5.2 Two-Stage Choice . . . . . . . . . . . . . . . . . . . . . . . 98
4.5.3 Updatable Priority Queues . . . . . . . . . . . . . . . . . 101
4.5.4 Plotting Run-Time Distributions . . . . . . . . . . . . . . 102
4.5.5 Testing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
4.6 Discrete Optimization . . . . . . . . . . . . . . . . . . . . . . . 105
4.6.1 Branch-and-bound Search . . . . . . . . . . . . . . . . . . 106

5 Propositions and Inference 109

5.1 Representing Knowledge Bases . . . . . . . . . . . . . . . . . . 109
5.2 Bottom-up Proofs (with askables) . . . . . . . . . . . . . . . . . 112

https://aipython.org Version 0.9.12 February 13, 2024

Contents 5

5.3 Top-down Proofs (with askables) . . . . . . . . . . . . . . . . . 114

5.4 Debugging and Explanation . . . . . . . . . . . . . . . . . . . . 115
5.5 Assumables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
5.6 Negation-as-failure . . . . . . . . . . . . . . . . . . . . . . . . . 122

6 Deterministic Planning 125

6.1 Representing Actions and Planning Problems . . . . . . . . . . 125
6.1.1 Robot Delivery Domain . . . . . . . . . . . . . . . . . . . 126
6.1.2 Blocks World . . . . . . . . . . . . . . . . . . . . . . . . . 128
6.2 Forward Planning . . . . . . . . . . . . . . . . . . . . . . . . . . 130
6.2.1 Defining Heuristics for a Planner . . . . . . . . . . . . . . 132
6.3 Regression Planning . . . . . . . . . . . . . . . . . . . . . . . . 135
6.3.1 Defining Heuristics for a Regression Planner . . . . . . . 137
6.4 Planning as a CSP . . . . . . . . . . . . . . . . . . . . . . . . . . 138
6.5 Partial-Order Planning . . . . . . . . . . . . . . . . . . . . . . . 142

7 Supervised Machine Learning 149

7.1 Representations of Data and Predictions . . . . . . . . . . . . . 150
7.1.1 Creating Boolean Conditions from Features . . . . . . . . 153
7.1.2 Evaluating Predictions . . . . . . . . . . . . . . . . . . . . 155
7.1.3 Creating Test and Training Sets . . . . . . . . . . . . . . . 157
7.1.4 Importing Data From File . . . . . . . . . . . . . . . . . . 157
7.1.5 Augmented Features . . . . . . . . . . . . . . . . . . . . . 160
7.2 Generic Learner Interface . . . . . . . . . . . . . . . . . . . . . 162
7.3 Learning With No Input Features . . . . . . . . . . . . . . . . . 163
7.3.1 Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . 165
7.4 Decision Tree Learning . . . . . . . . . . . . . . . . . . . . . . . 167
7.5 Cross Validation and Parameter Tuning . . . . . . . . . . . . . 171
7.6 Linear Regression and Classification . . . . . . . . . . . . . . . 175
7.7 Boosting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181
7.7.1 Gradient Tree Boosting . . . . . . . . . . . . . . . . . . . . 184

8 Neural Networks and Deep Learning 187

8.1 Layers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187
8.1.1 Linear Layer . . . . . . . . . . . . . . . . . . . . . . . . . . 188
8.1.2 ReLU Layer . . . . . . . . . . . . . . . . . . . . . . . . . . 190
8.1.3 Sigmoid Layer . . . . . . . . . . . . . . . . . . . . . . . . . 190
8.2 Feedforward Networks . . . . . . . . . . . . . . . . . . . . . . . 191
8.3 Improved Optimization . . . . . . . . . . . . . . . . . . . . . . 193
8.3.1 Momentum . . . . . . . . . . . . . . . . . . . . . . . . . . 193
8.3.2 RMS-Prop . . . . . . . . . . . . . . . . . . . . . . . . . . . 193
8.4 Dropout . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194
8.4.1 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . 195

9 Reasoning with Uncertainty 201

https://aipython.org Version 0.9.12 February 13, 2024

6 Contents

9.1 Representing Probabilistic Models . . . . . . . . . . . . . . . . 201

9.2 Representing Factors . . . . . . . . . . . . . . . . . . . . . . . . 201
9.3 Conditional Probability Distributions . . . . . . . . . . . . . . 203
9.3.1 Logistic Regression . . . . . . . . . . . . . . . . . . . . . . 203
9.3.2 Noisy-or . . . . . . . . . . . . . . . . . . . . . . . . . . . . 204
9.3.3 Tabular Factors and Prob . . . . . . . . . . . . . . . . . . 205
9.3.4 Decision Tree Representations of Factors . . . . . . . . . 206
9.4 Graphical Models . . . . . . . . . . . . . . . . . . . . . . . . . . 208
9.4.1 Showing Belief Networks . . . . . . . . . . . . . . . . . . 209
9.4.2 Example Belief Networks . . . . . . . . . . . . . . . . . . 210
9.5 Inference Methods . . . . . . . . . . . . . . . . . . . . . . . . . 216
9.5.1 Showing Posterior Distributions . . . . . . . . . . . . . . 217
9.6 Naive Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 218
9.7 Recursive Conditioning . . . . . . . . . . . . . . . . . . . . . . 220
9.8 Variable Elimination . . . . . . . . . . . . . . . . . . . . . . . . 224
9.9 Stochastic Simulation . . . . . . . . . . . . . . . . . . . . . . . . 227
9.9.1 Sampling from a discrete distribution . . . . . . . . . . . 227
9.9.2 Sampling Methods for Belief Network Inference . . . . . 229
9.9.3 Rejection Sampling . . . . . . . . . . . . . . . . . . . . . . 229
9.9.4 Likelihood Weighting . . . . . . . . . . . . . . . . . . . . 230
9.9.5 Particle Filtering . . . . . . . . . . . . . . . . . . . . . . . 231
9.9.6 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . 233
9.9.7 Gibbs Sampling . . . . . . . . . . . . . . . . . . . . . . . . 234
9.9.8 Plotting Behavior of Stochastic Simulators . . . . . . . . 236
9.10 Hidden Markov Models . . . . . . . . . . . . . . . . . . . . . . 238
9.10.1 Exact Filtering for HMMs . . . . . . . . . . . . . . . . . . 240
9.10.2 Localization . . . . . . . . . . . . . . . . . . . . . . . . . . 241
9.10.3 Particle Filtering for HMMs . . . . . . . . . . . . . . . . . 244
9.10.4 Generating Examples . . . . . . . . . . . . . . . . . . . . 246
9.11 Dynamic Belief Networks . . . . . . . . . . . . . . . . . . . . . 247
9.11.1 Representing Dynamic Belief Networks . . . . . . . . . . 248
9.11.2 Unrolling DBNs . . . . . . . . . . . . . . . . . . . . . . . . 251
9.11.3 DBN Filtering . . . . . . . . . . . . . . . . . . . . . . . . . 252

10 Learning with Uncertainty 255

10.1 Bayesian Learning . . . . . . . . . . . . . . . . . . . . . . . . . 255
10.2 K-means . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 259
10.3 EM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 263

11 Causality 269
11.1 Do Questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 269
11.2 Counterfactual Example . . . . . . . . . . . . . . . . . . . . . . 271
11.2.1 Firing Squad Example . . . . . . . . . . . . . . . . . . . . 274

12 Planning with Uncertainty 277

https://aipython.org Version 0.9.12 February 13, 2024

Contents 7

12.1 Decision Networks . . . . . . . . . . . . . . . . . . . . . . . . . 277

12.1.1 Example Decision Networks . . . . . . . . . . . . . . . . 279
12.1.2 Decision Functions . . . . . . . . . . . . . . . . . . . . . . 285
12.1.3 Recursive Conditioning for decision networks . . . . . . 286
12.1.4 Variable elimination for decision networks . . . . . . . . 289
12.2 Markov Decision Processes . . . . . . . . . . . . . . . . . . . . 292
12.2.1 Problem Domains . . . . . . . . . . . . . . . . . . . . . . . 293
12.2.2 Value Iteration . . . . . . . . . . . . . . . . . . . . . . . . 301
12.2.3 Value Iteration GUI for Grid Domains . . . . . . . . . . . 302
12.2.4 Asynchronous Value Iteration . . . . . . . . . . . . . . . . 307

13 Reinforcement Learning 309

13.1 Representing Agents and Environments . . . . . . . . . . . . . 309
13.1.1 Environments . . . . . . . . . . . . . . . . . . . . . . . . . 309
13.1.2 Agents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 310
13.1.3 Simulating an Environment-Agent Interaction . . . . . . 311
13.1.4 Party Environment . . . . . . . . . . . . . . . . . . . . . . 312
13.1.5 Environment from a Problem Domain . . . . . . . . . . . 313
13.1.6 Monster Game Environment . . . . . . . . . . . . . . . . 314
13.2 Q Learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 317
13.2.1 Exploration Strategies . . . . . . . . . . . . . . . . . . . . 319
13.2.2 Testing Q-learning . . . . . . . . . . . . . . . . . . . . . . 320
13.3 Q-leaning with Experience Replay . . . . . . . . . . . . . . . . 322
13.4 Stochastic Policy Learning Agent . . . . . . . . . . . . . . . . . 324
13.5 Model-based Reinforcement Learner . . . . . . . . . . . . . . . 326
13.6 Reinforcement Learning with Features . . . . . . . . . . . . . . 329
13.6.1 Representing Features . . . . . . . . . . . . . . . . . . . . 330
13.6.2 Feature-based RL learner . . . . . . . . . . . . . . . . . . 333
13.7 GUI for RL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 336

14 Multiagent Systems 341

14.1 Minimax . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 341
14.1.1 Creating a two-player game . . . . . . . . . . . . . . . . . 341
14.1.2 Minimax and α-β Pruning . . . . . . . . . . . . . . . . . . 344
14.2 Multiagent Learning . . . . . . . . . . . . . . . . . . . . . . . . 346
14.2.1 Simulating Multiagent Interaction with an Environment 346
14.2.2 Example Games . . . . . . . . . . . . . . . . . . . . . . . . 348
14.2.3 Testing Games and Environments . . . . . . . . . . . . . 349

15 Individuals and Relations 351

15.1 Representing Datalog and Logic Programs . . . . . . . . . . . 351
15.2 Unification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 353
15.3 Knowledge Bases . . . . . . . . . . . . . . . . . . . . . . . . . . 354
15.4 Top-down Proof Procedure . . . . . . . . . . . . . . . . . . . . 356
15.5 Logic Program Example . . . . . . . . . . . . . . . . . . . . . . 358

https://aipython.org Version 0.9.12 February 13, 2024

8 Contents

16 Knowledge Graphs and Ontologies 361

16.1 Triple Store . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 361
16.2 Integrating Datalog and Triple Store . . . . . . . . . . . . . . . 364

17 Relational Learning 367

17.1 Collaborative Filtering . . . . . . . . . . . . . . . . . . . . . . . 367
17.1.1 Plotting . . . . . . . . . . . . . . . . . . . . . . . . . . . . 371
17.1.2 Loading Rating Sets from Files and Websites . . . . . . . 374
17.1.3 Ratings of top items and users . . . . . . . . . . . . . . . 375
17.2 Relational Probabilistic Models . . . . . . . . . . . . . . . . . . 377

18 Version History 383

Bibliography 385

Index 387

https://aipython.org Version 0.9.12 February 13, 2024

 Chapter 1

Python for Artificial Intelligence

AIPython contains runnable code for the book Artificial Intelligence, foundations
of computational agents, 3rd Edition [Poole and Mackworth, 2023]. It has the
following design goals:

• Readability is more important than efficiency, although the asymptotic

complexity is not compromised. AIPython is not a replacement for well-
designed libraries, or optimized tools. Think of it like a model of an en-
gine made of glass, so you can see the inner workings; don’t expect it to
power a big truck, but it lets you see how a metal engine can power a
truck.

• It uses as few libraries as possible. A reader only needs to understand

Python. Libraries hide details that we make explicit. The only library
used is matplotlib for plotting and drawing.

1.1 Why Python?

We use Python because Python programs can be close to pseudo-code. It is
designed for humans to read.
Python is reasonably efficient. Efficiency is usually not a problem for small
examples. If your Python code is not efficient enough, a general procedure to
improve it is to find out what is taking most of the time, and implement just
that part more efficiently in some lower-level language. Most of these lower-
level languages interoperate with Python nicely. This will result in much less
programming and more efficient code (because you will have more time to
optimize) than writing everything in a low-level language. You will not have
to do that for the code here if you are using it for larger projects.

9
10 1. Python for Artificial Intelligence

1.2 Getting Python

You need Python 3.9 or later (https://python.org/) and a compatible version
of matplotlib (https://matplotlib.org/). This code is not compatible with
Python 2 (e.g., with Python 2.7).
Download and install the latest Python 3 release from https://python.org/
or https://www.anaconda.com/download. This should also install pip3. You can
install matplotlib using
pip3 install matplotlib
in a terminal shell (not in Python). That should “just work”. If not, try using
pip instead of pip3.
The command python or python3 should then start the interactive Python
shell. You can quit Python with a control-D or with quit().
To upgrade matplotlib to the latest version (which you should do if you
install a new version of Python) do:
pip3 install --upgrade matplotlib
We recommend using the enhanced interactive python ipython (https://
ipython.org/) [Pérez and Granger, 2007]. To install ipython after you have
installed python do:
pip3 install ipython

1.3 Running Python

We assume that everything is done with an interactive Python shell. You can
either do this with an IDE, such as IDLE that comes with standard Python
distributions, or just running ipython3 or python3 (or perhaps just ipython or
python) from a shell.
Here we describe the most simple version that uses no IDE. If you down-
load the zip file, and cd to the “aipython” folder where the .py files are, you
should be able to do the following, with user input in bold. The first python
command is in the operating system shell; the -i is important to enter interac-
tive mode.
python -i searchGeneric.py
Testing problem 1:
7 paths have been expanded and 4 paths remain in the frontier
Path found: A --> C --> B --> D --> G
Passed unit test
>>> searcher2 = AStarSearcher(searchProblem.acyclic_delivery_problem) #A*
>>> searcher2.search() # find first path
16 paths have been expanded and 5 paths remain in the frontier
o103 --> o109 --> o119 --> o123 --> r123
>>> searcher2.search() # find next path

https://aipython.org Version 0.9.12 February 13, 2024

1.4. Pitfalls 11

21 paths have been expanded and 6 paths remain in the frontier

o103 --> b3 --> b4 --> o109 --> o119 --> o123 --> r123
>>> searcher2.search() # find next path
28 paths have been expanded and 5 paths remain in the frontier
o103 --> b3 --> b1 --> b2 --> b4 --> o109 --> o119 --> o123 --> r123
>>> searcher2.search() # find next path
No (more) solutions. Total of 33 paths expanded.
>>>
You can then interact at the last prompt.
There are many textbooks for Python. The best source of information about
python is https://www.python.org/. The documentation is at https://docs.
python.org/3/.
The rest of this chapter is about what is special about the code for AI tools.
We will only use the standard Python library and matplotlib. All of the exer-
cises can be done (and should be done) without using other libraries; the aim
is for you to spend your time thinking about how to solve the problem rather
than searching for pre-existing solutions.

1.4 Pitfalls
It is important to know when side effects occur. Often AI programs consider
what would/might happen given certain conditions. In many such cases, we
don’t want side effects. When an agent acts in the world, side effects are ap-
propriate.
In Python, you need to be careful to understand side effects. For example,
the inexpensive function to add an element to a list, namely append, changes
the list. In a functional language like Haskell or Lisp, adding a new element to a
list, without changing the original list, is a cheap operation. For example if x is
a list containing n elements, adding an extra element to the list in Python (using
append) is fast, but it has the side effect of changing the list x. To construct a
new list that contains the elements of x plus a new element, without changing
the value of x, entails copying the list, or using a different representation for
lists. In the searching code, we will use a different representation for lists for
this reason.

1.5 Features of Python

1.5.1 f-strings
Python can use matching ', ", ''' or """, the latter two respecting line breaks
in the string. We use the convention that when the string denotes a unique
symbol, we use single quotes, and when it is designed to be for printing, we
use double quotes.

https://aipython.org Version 0.9.12 February 13, 2024

12 1. Python for Artificial Intelligence

We make extensive use of f-strings https://docs.python.org/3/tutorial/

inputoutput.html. In its simplest form
f"str1{e1}str2{e2}str3"
where e1 and e2 are expressions, is an abbreviation for
"str1"+str(e2)+"str2"+str(e2)+"str3"
where + is string concatenation, and str is the function that returns a string
representation of its expression argument.

1.5.2 Lists, Tuples, Sets, Dictionaries and Comprehensions

We make extensive uses of lists, tuples, sets and dictionaries (dicts). See
https://docs.python.org/3/library/stdtypes.html
One of the nice features of Python is the use of comprehensions1 (and also
list, tuple, set and dictionary comprehensions). A generator expression is of
the form

(fe for e in iter if cond)

enumerates the values fe for each e in iter for which cond is true. The “if cond”
part is optional, but the “for” and “in” are not optional. Here e is a variable
(or a pattern that can be on the left side of =), iter is an iterator, which can
generate a stream of data, such as a list, a set, a range object (to enumerate
integers between ranges) or a file. cond is an expression that evaluates to either
True or False for each e, and fe is an expression that will be evaluated for each
value of e for which cond returns True.
The result can go in a list or used in another iteration, or can be called
directly using next. The procedure next takes an iterator and returns the next
element (advancing the iterator); it raises a StopIteration exception if there is
no next element. The following shows a simple example, where user input is
prepended with >>>
>>> [e*e for e in range(20) if e%2==0]
[0, 4, 16, 36, 64, 100, 144, 196, 256, 324]
>>> a = (e*e for e in range(20) if e%2==0)
>>> next(a)
0
>>> next(a)
4
>>> next(a)
16
>>> list(a)
[36, 64, 100, 144, 196, 256, 324]
1 https://docs.python.org/3/reference/expressions.html#displays-for-lists-sets-and-dictionaries

https://aipython.org Version 0.9.12 February 13, 2024

 1.5. Features of Python 13

>>> next(a)
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
StopIteration
Notice how list(a) continued on the enumeration, and got to the end of it.
Comprehensions can also be used for dictionaries. The following code cre-
ates an index for list a:
>>> a = ["a","f","bar","b","a","aaaaa"]
>>> ind = {a[i]:i for i in range(len(a))}
>>> ind
{'a': 4, 'f': 1, 'bar': 2, 'b': 3, 'aaaaa': 5}
>>> ind['b']
3
which means that 'b' is the 3rd element of the list.
The assignment of ind could have also be written as:
>>> ind = {val:i for (i,val) in enumerate(a)}
where enumerate is a built-in function that, given a dictionary, returns an itera-
tor of (index, value) pairs.

1.5.3 Functions as first-class objects

Python can create lists and other data structures that contain functions. There
is an issue that tricks many newcomers to Python. For a local variable in a
function, the function uses the last value of the variable when the function is
called, not the value of the variable when the function was defined (this is called
“late binding”). This means if you want to use the value a variable has when
the function is created, you need to save the current value of that variable.
Whereas Python uses “late binding” by default, the alternative that newcom-
ers often expect is “early binding”, where a function uses the value a variable
had when the function was defined. The following examples show how early
binding can be implemented.
Consider the following programs designed to create a list of 5 functions,
where the ith function in the list is meant to add i to its argument:2
pythonDemo.py — Some tricky examples
11 fun_list1 = []
12 for i in range(5):
13 def fun1(e):
14 return e+i
15 fun_list1.append(fun1)
2 Numbered lines are Python code available in the code-directory, aipython. The name of

the file is given in the gray text above the listing. The numbers correspond to the line numbers
in that file.

https://aipython.org Version 0.9.12 February 13, 2024

 14 1. Python for Artificial Intelligence

16
17 fun_list2 = []
18 for i in range(5):
19 def fun2(e,iv=i):
20 return e+iv
21 fun_list2.append(fun2)
22
23 fun_list3 = [lambda e: e+i for i in range(5)]
24
25 fun_list4 = [lambda e,iv=i: e+iv for i in range(5)]
26
27 i=56

Try to predict, and then test to see the output, of the output of the following
calls, remembering that the function uses the latest value of any variable that
is not bound in the function call:

pythonDemo.py — (continued)

29 # in Shell do
30 ## ipython -i pythonDemo.py
31 # Try these (copy text after the comment symbol and paste in the Python
prompt):
32 # print([f(10) for f in fun_list1])
33 # print([f(10) for f in fun_list2])
34 # print([f(10) for f in fun_list3])
35 # print([f(10) for f in fun_list4])

In the first for-loop, the function fun1 uses i, whose value is the last value it was
assigned. In the second loop, the function fun2 uses iv. There is a separate iv
variable for each function, and its value is the value of i when the function was
defined. Thus fun1 uses late binding, and fun2 uses early binding. fun_list3
and fun_list4 are equivalent to the first two (except fun_list4 uses a different
i variable).
One of the advantages of using the embedded definitions (as in fun1 and
fun2 above) over the lambda is that is it possible to add a __doc__ string, which
is the standard for documenting functions in Python, to the embedded defini-
tions.

1.5.4 Generators
Python has generators which can be used for a form of lazy evaluation – only
computing values when needed.
The yield command returns a value that is obtained with next. It is typi-
cally used to enumerate the values for a for loop or in generators. (The yield
command can also be used for coroutines, but AIPython only uses it for gener-
ators.)
A version of the built-in range, with 2 or 3 arguments (and positive steps)
can be implemented as:

https://aipython.org Version 0.9.12 February 13, 2024

 1.5. Features of Python 15

pythonDemo.py — (continued)

37 def myrange(start, stop, step=1):

38 """enumerates the values from start in steps of size step that are
39 less than stop.
40 """
41 assert step>0, f"only positive steps implemented in myrange: {step}"
42 i = start
43 while i<stop:
44 yield i
45 i += step
46
47 print("list(myrange(2,30,3)):",list(myrange(2,30,3)))

Note that the built-in range is unconventional in how it handles a single argu-
ment, as the single argument acts as the second argument of the function. Note
also that the built-in range also allows for indexing (e.g., range(2,30,3)[2] re-
turns 8), but the above implementation does not. However myrange also works
for floats, whereas the built-in range does not.

Exercise 1.1 Implement a version of myrange that acts like the built-in version
when there is a single argument. (Hint: make the second argument have a default
value that can be recognized in the function.) There is no need to make it with
indexing.

Yield can be used to generate the same sequence of values as in the example
of Section 1.5.2:

pythonDemo.py — (continued)

49 def ga(n):
50 """generates square of even nonnegative integers less than n"""
51 for e in range(n):
52 if e%2==0:
53 yield e*e
54 a = ga(20)

The sequence of next(a), and list(a) gives exactly the same results as the com-
prehension in Section 1.5.2.
It is straightforward to write a version of the built-in enumerate called myenumerate:

pythonDemo.py — (continued)

56 def myenumerate(enum):
57 for i in range(len(enum)):
58 yield i,enum[i]

Exercise 1.2 Write a version of enumerate where the only iteration is “for val in
enum”. Hint: keep track of the index.

https://aipython.org Version 0.9.12 February 13, 2024

 16 1. Python for Artificial Intelligence

1.6 Useful Libraries

1.6.1 Timing Code
In order to compare algorithms, we often want to compute how long a program
takes; this is called the run time of the program. The most straightforward way
to compute run time is to use time.perf_counter(), as in:
import time
start_time = time.perf_counter()
compute_for_a_while()
end_time = time.perf_counter()
print("Time:", end_time - start_time, "seconds")
Note that time.perf_counter() measures clock time; so this should be done
without user interaction between the calls. On the interactive python shell, you
should do:
start_time = time.perf_counter(); compute_for_a_while(); end_time = time.perf_counter()
If this time is very small (say less than 0.2 second), it is probably very inac-
curate, and it may be better to run your code many times to get a more accu-
rate count. For this you can use timeit (https://docs.python.org/3/library/
timeit.html). To use timeit to time the call to foo.bar(aaa) use:
import timeit
time = timeit.timeit("foo.bar(aaa)",
setup="from __main__ import foo,aaa", number=100)
The setup is needed so that Python can find the meaning of the names in the
string that is called. This returns the number of seconds to execute foo.bar(aaa)
100 times. The variable number should be set so that the run time is at least 0.2
seconds.
You should not trust a single measurement as that can be confounded by in-
terference from other processes. timeit.repeat can be used for running timit
a few (say 3) times. When reporting the time of any computation, you should
be explicit and explain what you are reporting. Usually the minimum time is
the one to report.

1.6.2 Plotting: Matplotlib

The standard plotting for Python is matplotlib (https://matplotlib.org/). We
will use the most basic plotting using the pyplot interface.
Here is a simple example that uses everything we will use. The output is
shown in Figure 1.1.
pythonDemo.py — (continued)

60 import matplotlib.pyplot as plt

61

https://aipython.org Version 0.9.12 February 13, 2024

 1.6. Useful Libraries 17

The first fun

300 y=(x-40)^2/10-20

250

200
The y axis

150

100 ellipse?

50

0 20 40 60 80 100
The x axis

Figure 1.1: Result of pythonDemo code

62 def myplot(minv,maxv,step,fun1,fun2):
63 plt.ion() # make it interactive
64 plt.xlabel("The x axis")
65 plt.ylabel("The y axis")
66 plt.xscale('linear') # Makes a 'log' or 'linear' scale
67 xvalues = range(minv,maxv,step)
68 plt.plot(xvalues,[fun1(x) for x in xvalues],
69 label="The first fun")
70 plt.plot(xvalues,[fun2(x) for x in xvalues], linestyle='--',color='k',
71 label=fun2.__doc__) # use the doc string of the function
72 plt.legend(loc="upper right") # display the legend
73
74 def slin(x):
75 """y=2x+7"""
76 return 2*x+7
77 def sqfun(x):
78 """y=(x-40)ˆ2/10-20"""
79 return (x-40)**2/10-20
80
81 # Try the following:
82 # from pythonDemo import myplot, slin, sqfun
83 # import matplotlib.pyplot as plt
84 # myplot(0,100,1,slin,sqfun)
85 # plt.legend(loc="best")
86 # import math
87 # plt.plot([41+40*math.cos(th/10) for th in range(50)],
88 # [100+100*math.sin(th/10) for th in range(50)])

https://aipython.org Version 0.9.12 February 13, 2024

 18 1. Python for Artificial Intelligence

89 # plt.text(40,100,"ellipse?")
90 # plt.xscale('log')

At the end of the code are some commented-out commands you should try in
interactive mode. Cut from the file and paste into Python (and remember to
remove the comments symbol and leading space).

1.7 Utilities
1.7.1 Display
In this distribution, to keep things simple, using only standard Python, we
use a text-oriented tracing of the code. A graphical depiction of the code can
override the definition of display (e.g., see SearcherGUI in Section 3.2.2 and
ConsistencyGUI in Section 4.4.2).
The method self.display is used to trace the program. Any call

self.display(level, to print . . . )

where the level is less than or equal to the value for max_display_level will be
printed. The to print . . . can be anything that is accepted by the built-in print
(including any keyword arguments).
The definition of display is:
display.py — A simple way to trace the intermediate steps of algorithms.
11 class Displayable(object):
12 """Class that uses 'display'.
13 The amount of detail is controlled by max_display_level
14 """
15 max_display_level = 1 # can be overridden in subclasses or instances
16
17 def display(self,level,*args,**nargs):
18 """print the arguments if level is less than or equal to the
19 current max_display_level.
20 level is an integer.
21 the other arguments are whatever arguments print can take.
22 """
23 if level <= self.max_display_level:
24 print(*args, **nargs) ##if error you are using Python2 not
Python3

(Note that args gets a tuple of the positional arguments, and nargs gets a dic-
tionary of the keyword arguments). This will not work in Python 2, and will
give an error.
Any class that wants to use display can be made a subclass of Displayable.
To change the maximum display level to 3 for a class do:

Classname.max display level = 3

https://aipython.org Version 0.9.12 February 13, 2024

 1.7. Utilities 19

which will make calls to display in that class print when the value of level is
less-than-or-equal to 3. The default display level is 1. It can also be changed for
individual objects (the object value overrides the class value).
The value of max_display_level by convention is:

0 display nothing

1 display solutions (nothing that happens repeatedly)

2 also display the values as they change (little detail through a loop)

3 also display more details

4 and above even more detail

1.7.2 Argmax
Python has a built-in max function that takes a generator (or a list or set) and re-
turns the maximum value. The argmax method returns the index of an element
that has the maximum value. If there are multiple elements with the maximum
value, one of the indexes to that value is returned at random. argmaxe assumes
an enumeration; a generator of (element, value) pairs, as for example is gener-
ated by the built-in enumerate(list) for lists or dict.items() for dictionaries.
utilities.py — AIPython useful utilities
11 import random
12 import math
13
14 def argmaxall(gen):
15 """gen is a generator of (element,value) pairs, where value is a real.
16 argmaxall returns a list of all of the elements with maximal value.
17 """
18 maxv = -math.inf # negative infinity
19 maxvals = [] # list of maximal elements
20 for (e,v) in gen:
21 if v>maxv:
22 maxvals,maxv = [e], v
23 elif v==maxv:
24 maxvals.append(e)
25 return maxvals
26
27 def argmaxe(gen):
28 """gen is a generator of (element,value) pairs, where value is a real.
29 argmaxe returns an element with maximal value.
30 If there are multiple elements with the max value, one is returned at
random.
31 """
32 return random.choice(argmaxall(gen))
33
34 def argmax(lst):

https://aipython.org Version 0.9.12 February 13, 2024

 20 1. Python for Artificial Intelligence

35 """returns maximum index in a list"""

36 return argmaxe(enumerate(lst))
37 # Try:
38 # argmax([1,6,3,77,3,55,23])
39
40 def argmaxd(dct):
41 """returns the arg max of a dictionary dct"""
42 return argmaxe(dct.items())
43 # Try:
44 # arxmaxd({2:5,5:9,7:7})

Exercise 1.3 Change argmaxall to have an optional argument that specifies whether
you want the “first”, “last” or a “random” index of the maximum value returned.
If you want the first or the last, you don’t need to keep a list of the maximum
elements. Enable the other methods to have this optional argument.

1.7.3 Probability
For many of the simulations, we want to make a variable True with some prob-
ability. flip(p) returns True with probability p, and otherwise returns False.

utilities.py — (continued)

45 def flip(prob):
46 """return true with probability prob"""
47 return random.random() < prob

The select_from_dist method takes in a item : probability dictionary, and

returns one of the items in proportion to its probability. The probabilities
should sum to 1 or more. If they sum to more than one, the excess is ignored.

utilities.py — (continued)

49 def select_from_dist(item_prob_dist):
50 """ returns a value from a distribution.
51 item_prob_dist is an item:probability dictionary, where the
52 probabilities sum to 1.
53 returns an item chosen in proportion to its probability
54 """
55 ranreal = random.random()
56 for (it,prob) in item_prob_dist.items():
57 if ranreal < prob:
58 return it
59 else:
60 ranreal -= prob
61 raise RuntimeError(f"{item_prob_dist} is not a probability
distribution")

https://aipython.org Version 0.9.12 February 13, 2024

 1.8. Testing Code 21

1.8 Testing Code

It is important to test code early and test it often. We include a simple form of
unit test. The value of the current module is in __name__ and if the module is
run at the top-level, its value is "__main__". See https://docs.python.org/3/
library/ main .html.
The following code tests argmax and dict_union, but only when if utilities
is loaded in the top-level. If it is loaded in a module the test code is not run.
In your code, you should do more substantial testing than done here. In
particular, you should also test boundary cases.
utilities.py — (continued)

63 def test():
64 """Test part of utilities"""
65 assert argmax([1,6,55,3,55,23]) in [2,4]
66 print("Passed unit test in utilities")
67 print("run test_aipython() to test (almost) everything")
68
69 if __name__ == "__main__":
70 test()

The following does a simple check of all of AIPython that has automatic checks.
If you develop new algorithms or tests, add them here!
utilities.py — (continued)

72 def test_aipython():
73 # Agents: currently no tests
74 # Search:
75 print("***** testing Search *****")
76 import searchGeneric, searchBranchAndBound, searchExample, searchTest
77 searchGeneric.test(searchGeneric.AStarSearcher)
78 searchBranchAndBound.test(searchBranchAndBound.DF_branch_and_bound)
79 searchTest.run(searchExample.problem1,"Problem 1")
80 # CSP
81 print("\n***** testing CSP *****")
82 import cspExamples, cspDFS, cspSearch, cspConsistency, cspSLS
83 cspExamples.test_csp(cspDFS.dfs_solve1)
84 cspExamples.test_csp(cspSearch.solver_from_searcher)
85 cspExamples.test_csp(cspConsistency.ac_solver)
86 cspExamples.test_csp(cspConsistency.ac_search_solver)
87 cspExamples.test_csp(cspSLS.sls_solver)
88 cspExamples.test_csp(cspSLS.any_conflict_solver)
89 # Propositions
90 print("\n***** testing Propositional Logic *****")
91 import logicBottomUp, logicTopDown, logicExplain, logicNegation
92 logicBottomUp.test()
93 logicTopDown.test()
94 logicExplain.test()
95 logicNegation.test()
96 # Planning

https://aipython.org Version 0.9.12 February 13, 2024

 22 1. Python for Artificial Intelligence

97 print("\n***** testing Planning *****")

98 import stripsHeuristic
99 stripsHeuristic.test_forward_heuristic()
100 stripsHeuristic.test_regression_heuristic()
101 # Learning
102 print("\n***** testing Learning *****")
103 import learnProblem, learnNoInputs, learnDT, learnLinear
104 learnNoInputs.test_no_inputs(training_sizes=[4])
105 data = learnProblem.Data_from_file('data/carbool.csv', target_index=-1,
seed=123)
106 learnDT.testDT(data, print_tree=False)
107 learnLinear.test()
108 # Deep Learning: currently no tests
109 # Uncertainty
110 print("\n***** testing Uncertainty *****")
111 import probGraphicalModels, probRC, probVE, probStochSim
112 probGraphicalModels.InferenceMethod.testIM(probRC.ProbSearch)
113 probGraphicalModels.InferenceMethod.testIM(probRC.ProbRC)
114 probGraphicalModels.InferenceMethod.testIM(probVE.VE)
115 probGraphicalModels.InferenceMethod.testIM(probStochSim.RejectionSampling,
threshold=0.1)
116 probGraphicalModels.InferenceMethod.testIM(probStochSim.LikelihoodWeighting,
threshold=0.1)
117 probGraphicalModels.InferenceMethod.testIM(probStochSim.ParticleFiltering,
threshold=0.1)
118 probGraphicalModels.InferenceMethod.testIM(probStochSim.GibbsSampling,
threshold=0.1)
119 # Learning under uncertainty: currently no tests
120 # Causality: currently no tests
121 # Planning under uncertainty
122 print("\n***** testing Planning under Uncertainty *****")
123 import decnNetworks
124 decnNetworks.test(decnNetworks.fire_dn)
125 import mdpExamples
126 mdpExamples.test_MDP(mdpExamples.partyMDP)
127 # Reinforement Learning:
128 print("\n***** testing Reinforcement Learning *****")
129 import rlQLearner
130 rlQLearner.test_RL(rlQLearner.Q_learner, alpha_fun=lambda k:10/(9+k))
131 import rlQExperienceReplay
132 rlQLearner.test_RL(rlQExperienceReplay.Q_ER_learner, alpha_fun=lambda
k:10/(9+k))
133 import rlStochasticPolicy
134 rlQLearner.test_RL(rlStochasticPolicy.StochasticPIAgent,
alpha_fun=lambda k:10/(9+k))
135 import rlModelLearner
136 rlQLearner.test_RL(rlModelLearner.Model_based_reinforcement_learner)
137 import rlFeatures
138 rlQLearner.test_RL(rlFeatures.SARSA_LFA_learner,
es_kwargs={'epsilon':1}, eps=4)

https://aipython.org Version 0.9.12 February 13, 2024

 1.8. Testing Code 23

139 # Multiagent systems: currently no tests

140 # Individuals and Relations
141 print("\n***** testing Datalog and Logic Programming *****")
142 import relnExamples
143 relnExamples.test_ask_all()
144 # Knowledge Graphs and Onologies
145 print("\n***** testing Knowledge Graphs and Onologies *****")
146 import knowledgeGraph
147 knowledgeGraph.test_kg()
148 # Relational Learning: currently no tests

https://aipython.org Version 0.9.12 February 13, 2024

 Chapter 2

Agent Architectures and

Hierarchical Control

This implements the controllers described in Chapter 2 of Poole and Mack-

worth [2023].
These provide sequential implementations of the control. More sophisti-
cated version may have them run concurrently (either as coroutines or in par-
allel).
In this version the higher-levels call the lower-levels. The higher-levels call-
ing the lower-level works in simulated environments when there is a single
agent, and where the lower-level are written to make sure they return (and
don’t go on forever), and the higher level doesn’t take too long (as the lower-
levels will wait until called again).

2.1 Representing Agents and Environments

In the initial implementation, both agents and the environment are treated as
objects in the send of object-oriented programs: they can have an internal state
they maintain, and can evaluate methods that can provide answers. This is the
same representation used for the reinforcement learning algorithms (Chapter
13).
An environment takes in actions of the agents, updates its internal state
and returns the next percept, using the method do.
An agent takes the precept, updates its internal state, and output it next
action. An agent implements the method select_action that takes percept
and returns its next action.

25
 26 2. Agent Architectures and Hierarchical Control

The methods do and select_action are chained together to build a simula-

tor. In order to start this, we need either an action or a percept. There are two
variants used:

• An agent implements the initial_action() method which is used ini-

tially. This is the method used in the reinforcement learning chapter
(page 309).

• The environment implements the initial_percept() method which gives

the initial percept. This is the method used in this chapter.

In this implementation, the state of the agent and the state of the environ-
ment are represented using standard Python variables, which are updated as
the state changes. The percept and the actions are represented as variable-value
dictionaries. When agent has only a limited number of actions, the action can
be a single value.
In the following code raise NotImplementedError() is a way to specify
an abstract method that needs to be overridden in any implemented agent or
environment.
agents.py — Agent and Controllers
11 from display import Displayable
12
13 class