Python code for Artificial Intelligence: Foundations of ...

1 1 Python code for ArtificialIntelligence: Foundations ofComputational AgentsDavid L. Poole and Alan K. MackworthVersion of March 6, David L Poole and Alan K Mackworth code is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike International License. See: document and all the code can be downloaded authors and publisher of this book have used their best efforts in prepar-ing this book. These efforts include the development, research and testing ofthe theories and programs to determine their effectiveness. The authors andpublisher make no warranty of any kind, expressed or implied, with regard tothese programs or the documentation contained in this book. The author andpublisher shall not be liable in any event for incidental or consequential dam-ages in connection with, or arising out of, the furnishing, performance, or useof these 6, 2022 ContentsContents31 Python for Artificial Python ? .. Python .

2 Python .. of Python .. , Tuples, Sets, Dictionaries and Comprehensions .. as first-class objects .. and Coroutines .. Libraries .. Code .. : Matplotlib .. Union .. Code ..192 Agents and Agents and Environments .. buying agent and environment .. Environment .. agent .. Controller .. Layer .. Layer ..303 Searching for Search Problems .. Representation of Search Graph .. Search Problems .. Searcher and Variants .. as a Priority Queue .. Search .. Path Pruning .. Search ..474 Reasoning with Satisfaction Problems .. Simple Depth-first Solver .. CSPs to Search Problems .. Algorithms .. Implementation of Domain Splitting .. Splitting as an interface to graph searching .. CSPs using Stochastic Local Search .. Choice .. Priority Queues .. Runtime Distributions .. Optimization .. Search ..845 Propositions and Knowledge Bases .. Proofs (with askables).

3 Proofs (with askables) .. and Explanation ..93 6, ..976 Planning with Actions and Planning Problems .. Delivery Domain .. World .. Planning .. Heuristics for a Planner .. Planning .. Heuristics for a Regression Planner .. as a CSP .. Planning ..1177 Supervised Machine of Data and Predictions .. Boolean Conditions from Features .. Predictions .. Test and Training Sets .. Data From File .. Features .. Learner Interface .. With No Input Features .. Tree Learning .. Validation and Parameter Tuning .. Regression and Classification .. Stochastic Gradient Descent .. Tree Boosting ..1608 Neural Networks and Deep .. Networks .. Optimization ..1719 Reasoning Under Probabilistic Models .. Factors .. Probability Distributions .. Regression ..181 6, Factors .. Models .. Belief Networks .. Methods .. Conditioning .. Elimination .. Simulation.

4 From a discrete distribution .. Methods for Belief Network Inference .. Sampling .. Weighting .. Filtering .. Sampling .. Behaviour of Stochastic Simulators .. Markov Models .. Filtering for HMMs .. Filtering for HMMs .. Examples .. Belief Networks .. Representing Dynamic Belief Networks .. Unrolling DBNs .. DBN Filtering .. Models ..22410 Planning with Networks .. Example Decision Networks .. Recursive Conditioning for decision networks .. Variable elimination for decision networks .. Decision Processes .. Value Iteration .. Showing Grid MDPs .. Asynchronous Value Iteration ..24711 Learning with ..25512 Multiagent .. Creating a two-player game .. Minimax and - Pruning ..265 6, 2022 Contents713 Reinforcement Agents and Environments .. Simulating an environment from an MDP .. Simple Game .. Evaluation and Plotting .. Learning.

5 Testing Q-learning .. with Experience Replay .. Reinforcement Learner .. Learning with Features .. Representing Features .. Feature-based RL learner .. Experience Replay .. Learning ..29014 Relational Filtering .. Alternative Formulation .. Plotting .. Creating Rating Sets ..30115 Version History305 Bibliography307 Index309 6, 2022 Chapter 1 Python for Artificial Python ?We use Python because Python programs can be close to pseudo-code. It isdesigned for humans to is reasonably efficient. Efficiency is usually not a problem for smallexamples. If your Python code is not efficient enough, a general procedureto improve it is to find out what is taking most the time, and implement justthat part more efficiently in some lower-level language. Most of these lower-level languages interoperate with Python nicely. This will result in much lessprogramming and more efficient code (because you will have more time tooptimize) than writing everything in a low-level language.

6 You will not haveto do that for the code here if you are using it for course PythonYou need Python 3 ( ) and matplotlib ( ) that runs with Python 3. This code isnotcompatible with Python 2 ( ,with Python ).Download and istall the latest Python 3 release should also installpip3. You can install matplotlib usingpip3 install matplotlibin a terminal shell (not in Python ). That should just work . If not, try usingpipinstead commandpythonorpython3should then start the interactive pythonshell. You can quit Python with a control-D or withquit().9101. Python for Artificial IntelligenceTo upgrade matplotlib to the latest version (which you should do if youinstall a new version of Python ) do:pip3 install --upgrade matplotlibWe recommend using the enhanced interactive pythonipython( ). To install ipython after you have installed Python do:pip3 install PythonWe assume that everything is done with an interactive Python shell. You caneither do this with an IDE, such as IDLE that comes with standard Pythondistributions, or just running ipython3 (or perhaps just ipython) from a we describe the most simple version that uses no IDE.

7 If you down-load the zip file, and cd to the aipython folder where the .py files are, youshould be able to do the following, with user input following:. The firstipython3 command is in the operating system shell (note that the-iis impor-tant to enter interactive mode), with user input in bold:ipython -i ( :f59c0932b4, Mar 28 2018, 05:52:31)Type'copyright','credits'or'lic ense'for more informationIPython -- An enhanced Interactive Python . Type'?'for problem 1:7 paths have been expanded and 4 paths remain in the frontierPath found: a --> b --> c --> d --> gPassed unit testIn [1]:searcher2 = AStarSearcher( ) #A*In [2] () # find first path16 paths have been expanded and 5 paths remain in the frontierOut[2]: o103 --> o109 --> o119 --> o123 --> r123In [3] () # find next path21 paths have been expanded and 6 paths remain in the frontierOut[3]: o103 --> b3 --> b4 --> o109 --> o119 --> o123 --> r123In [4] () # find next path28 paths have been expanded and 5 paths remain in the frontierOut[4]: o103 --> b3 --> b1 --> b2 --> b4 --> o109 --> o119 --> o123 --> r123In [5] () # find next pathNo (more) solutions.

8 Total of 33 paths 6, Pitfalls11In [6]:You can then interact at the last are many textbooks for Python . The best source of information aboutpython We will be using Python 3; please down-load the latest release. The documentation is rest of this chapter is about what is special about the code for AI 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 aimis for you to spend your time thinking about how to solve the problem ratherthan searching for pre-existing is important to know when side effects occur. Often AI programs considerwhat would happen or what may have happened. In many such cases, wedon t want side effects. When an agent acts in the world, side effects are Python , you need to be careful to understand side effects. For example,the inexpensive function to add an element to a list, namelyappend, changes thelist. In a functional language like Haskell or Lisp, adding a new element to alist, without changing the original list, is a cheap operation.

9 For example ifxisa list containingnelements, adding an extra element to the list in Python (usingappend) is fast, but it has the side effect of changing the listx. To construct a newlist that contains the elements ofxplus a new element, without changing thevalue ofx, entails copying the list, or using a different representation for the searching code, we will use a different representation for lists for of , Tuples, Sets, Dictionaries and ComprehensionsWe make extensive uses of lists, tuples, sets and dictionaries (dicts). of the nice features of Python is the use of list comprehensions (andalso tuple, set and dictionary comprehensions).(feforeiniterifcond)enum erates the valuesfefor eacheiniterfor whichcondis true. The if cond part is optional, but the for and in are not optional. Hereehas to be avariable,iteris 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 6, 2022121.

10 Python for Artificial Intelligenceis an expression that evaluates to either True or False for eache, andfeis anexpression that will be evaluated for each value ofefor result can go in a list or used in another iteration, or can be calleddirectly usingnext. The procedurenexttakes an iterator returns the next el-ement (advancing the iterator) and raises a StopIteration exception if there isno next element. The following shows a simple example, where user input isprepended 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]>>> next(a)Traceback (most recent call last):File "<stdin>", line 1, in <module>StopIterationNotice howlist(a)continued on the enumeration, and got to the end of can also be used for dictionaries. The following code cre-ates an index for lista:>>> 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']3which means that'b'is the 3rd element of the assignment ofindcould have also be written as:>>> ind = {val:i for (i,val) in enumerate(a)}whereenumeratereturns an iterator of(index,value) as first-class objectsPython can create lists and other data structures that contain functions.