{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# An Introduction To `aima-python` \n", " \n", "The [aima-python](https://github.com/aimacode/aima-python) repository implements, in Python code, the algorithms in the textbook *[Artificial Intelligence: A Modern Approach](http://aima.cs.berkeley.edu)*. A typical module in the repository has the code for a single chapter in the book, but some modules combine several chapters. See [the index](https://github.com/aimacode/aima-python#index-of-code) if you can't find the algorithm you want. The code in this repository attempts to mirror the pseudocode in the textbook as closely as possible and to stress readability foremost; if you are looking for high-performance code with advanced features, there are other repositories for you. For each module, there are three/four files, for example:\n", "\n", "- [**`nlp.py`**](https://github.com/aimacode/aima-python/blob/master/nlp.py): Source code with data types and algorithms for natural language processing; functions have docstrings explaining their use.\n", "- [**`nlp.ipynb`**](https://github.com/aimacode/aima-python/blob/master/nlp.ipynb): A notebook like this one; gives more detailed examples and explanations of use.\n", "- [**`nlp_apps.ipynb`**](https://github.com/aimacode/aima-python/blob/master/nlp_apps.ipynb): A Jupyter notebook that gives example applications of the code.\n", "- [**`tests/test_nlp.py`**](https://github.com/aimacode/aima-python/blob/master/tests/test_nlp.py): Test cases, used to verify the code is correct, and also useful to see examples of use.\n", "\n", "There is also an [aima-java](https://github.com/aimacode/aima-java) repository, if you prefer Java.\n", " \n", "## What version of Python?\n", " \n", "The code is tested in Python [3.4](https://www.python.org/download/releases/3.4.3/) and [3.5](https://www.python.org/downloads/release/python-351/). If you try a different version of Python 3 and find a problem, please report it as an [Issue](https://github.com/aimacode/aima-python/issues).\n", " \n", "We recommend the [Anaconda](https://www.anaconda.com/download/) distribution of Python 3.5. It comes with additional tools like the powerful IPython interpreter, the Jupyter Notebook and many helpful packages for scientific computing. After installing Anaconda, you will be good to go to run all the code and all the IPython notebooks. \n", "\n", "## IPython notebooks \n", " \n", "The IPython notebooks in this repository explain how to use the modules, and give examples of usage. \n", "You can use them in three ways: \n", "\n", "1. View static HTML pages. (Just browse to the [repository](https://github.com/aimacode/aima-python) and click on a `.ipynb` file link.)\n", "2. Run, modify, and re-run code, live. (Download the repository (by [zip file](https://github.com/aimacode/aima-python/archive/master.zip) or by `git` commands), start a Jupyter notebook server with the shell command \"`jupyter notebook`\" (issued from the directory where the files are), and click on the notebook you want to interact with.)\n", "3. Binder - Click on the binder badge on the [repository](https://github.com/aimacode/aima-python) main page to open the notebooks in an executable environment, online. This method does not require any extra installation. The code can be executed and modified from the browser itself. Note that this is an unstable option; there is a chance the notebooks will never load.\n", "\n", " \n", "You can [read about notebooks](https://jupyter-notebook-beginner-guide.readthedocs.org/en/latest/) and then [get started](https://nbviewer.jupyter.org/github/jupyter/notebook/blob/master/docs/source/examples/Notebook/Running%20Code.ipynb)." ] }, { "cell_type": "markdown", "metadata": { "collapsed": true }, "source": [ "# Helpful Tips\n", "\n", "Most of these notebooks start by importing all the symbols in a module:" ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [], "source": [ "from logic import *" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "From there, the notebook alternates explanations with examples of use. You can run the examples as they are, and you can modify the code cells (or add new cells) and run your own examples. If you have some really good examples to add, you can make a github pull request.\n", "\n", "If you want to see the source code of a function, you can open a browser or editor and see it in another window, or from within the notebook you can use the IPython magic function `%psource` (for \"print source\") or the function `psource` from `notebook.py`. Also, if the algorithm has pseudocode available, you can read it by calling the `pseudocode` function with the name of the algorithm passed as a parameter." ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [], "source": [ "%psource WalkSAT" ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [ { "data": { "text/html": [ "\n", "\n", "\n", "\n", " \n", " \n", " \n", "\n", "\n", "

\n", "\n", "
def WalkSAT(clauses, p=0.5, max_flips=10000):\n",
       "    """Checks for satisfiability of all clauses by randomly flipping values of variables\n",
       "    >>> WalkSAT([A & ~A], 0.5, 100) is None\n",
       "    True\n",
       "    """\n",
       "    # Set of all symbols in all clauses\n",
       "    symbols = {sym for clause in clauses for sym in prop_symbols(clause)}\n",
       "    # model is a random assignment of true/false to the symbols in clauses\n",
       "    model = {s: random.choice([True, False]) for s in symbols}\n",
       "    for i in range(max_flips):\n",
       "        satisfied, unsatisfied = [], []\n",
       "        for clause in clauses:\n",
       "            (satisfied if pl_true(clause, model) else unsatisfied).append(clause)\n",
       "        if not unsatisfied:  # if model satisfies all the clauses\n",
       "            return model\n",
       "        clause = random.choice(unsatisfied)\n",
       "        if probability(p):\n",
       "            sym = random.choice(list(prop_symbols(clause)))\n",
       "        else:\n",
       "            # Flip the symbol in clause that maximizes number of sat. clauses\n",
       "            def sat_count(sym):\n",
       "                # Return the the number of clauses satisfied after flipping the symbol.\n",
       "                model[sym] = not model[sym]\n",
       "                count = len([clause for clause in clauses if pl_true(clause, model)])\n",
       "                model[sym] = not model[sym]\n",
       "                return count\n",
       "\n",
       "            sym = argmax(prop_symbols(clause), key=sat_count)\n",
       "        model[sym] = not model[sym]\n",
       "    # If no solution is found within the flip limit, we return failure\n",
       "    return None\n",
       "
\n", "\n", "\n" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/markdown": [ "### AIMA3e\r\n", "__function__ WALKSAT(_clauses_, _p_, _max\\_flips_) __returns__ a satisfying model or _failure_ \r\n", " __inputs__: _clauses_, a set of clauses in propositional logic \r\n", "    _p_, the probability of choosing to do a \"random walk\" move, typically around 0.5 \r\n", "    _max\\_flips_, number of flips allowed before giving up \r\n", "\r\n", " _model_ ← a random assignment of _true_/_false_ to the symbols in _clauses_ \r\n", " __for__ _i_ = 1 to _max\\_flips_ __do__ \r\n", "   __if__ _model_ satisfies _clauses_ __then return__ _model_ \r\n", "   _clause_ ← a randomly selected clause from _clauses_ that is false in _model_ \r\n", "   __with probability__ _p_ flip the value in _model_ of a randomly selected symbol from _clause_ \r\n", "   __else__ flip whichever symbol in _clause_ maximizes the number of satisfied clauses \r\n", " __return__ _failure_ \r\n", "\r\n", "---\r\n", "__Figure__ ?? The WALKSAT algorithm for checking satisfiability by randomly flipping the values of variables. Many versions of the algorithm exist." ], "text/plain": [ "" ] }, "execution_count": 3, "metadata": {}, "output_type": "execute_result" } ], "source": [ "from notebook import psource, pseudocode\n", "\n", "psource(WalkSAT)\n", "pseudocode(\"WalkSAT\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Or see an abbreviated description of an object with a trailing question mark:" ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [], "source": [ "WalkSAT?" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Authors\n", "\n", "This notebook is written by [Chirag Vertak](https://github.com/chiragvartak) and [Peter Norvig](https://github.com/norvig)." ] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.7.5" } }, "nbformat": 4, "nbformat_minor": 1 }