Artificial Intelligence

Fall 2018 -- Peter Brooks

The (ever-changing) Syllabus and readings

Decision Trees Here is the data that can be handled by a decision tree.  Try to build a minimal decision tree to encompass all of the data.  Draw it on paper and bring it to class.
Here are some decision trees as trees.
Here are some decision tree datasets.
End of course deadlines:
  • Fri night, Jan 11: Othello competitor -- must calculate best move up to ply=2 (or more, of course).
  • Fri night, Jan 18: extra credit: either Connect-4 competitor (ply=2 again), and/or review of one of the AI essays (min 1.5 pages, double-spaced)

What I mean by finding the best move up to ply=n -- the MINI-MAX Method

  • Suppose you're calculating the best move for "X" to a depth of ply=0.  That means finding all of the current legal moves and choosing one at random.
  •  Suppose the desired depth is ply=1.  Then find the legal moves, and evaluate them, and choose the best one.  Note that we don't care about what the opponent thinks yet.  Examples: if one of the legal moves is a winning move, then the evaluator will choose it.  However, if one of the moves allows the opponent to win on the next turn, the evaluator does not know that yet, and so cannot take that into consideration!
  • Suppose the desired depth is ply=2. Then find the legal moves.  If there's a winning one, take it. If not, then for each of your possible moves, find the opponent's best ply=1 counter-move (let her evaluate her own possible moves and choose the best one), and then choose the move that will provide the opponent the least advantage.  You want the minimum of her maximizing moves.  Hence: the MINI-MAX METHOD.
  • Suppose the desired depth is ply=3. Once more choose an immediate winning move if possible. Otherwise, allow the opponent to "take over" and let her choose her best move to ply=2 from her point of view.  Then choose your move that, again, affords her the least advantage.
 Information Theory Here is a quickie intro to Information Theory basics
Here is a document I'm working on that matches my information talks.
Running the demo versions of the 3 games on your PythonWebServer
  1. Download and unpack this file (games-v5.zip) into your PythonWebServer's cgi-bin directory
  2. Launch your PythonWebserver:     python3 -m http.server --cgi 9000
  3. In your browser, go to http://localhost:9000/cgi-bin/game-start.py and choose the game and the game-program.  Hopefully this will work...
Here are the current docs for constructing and running the 3 games.
  1. TicTacToe
    1. Building the competitor
    2. Running it
  2. Othello
    1. Othello info
    2. Building the othello competitor
  3. Connect-4
    1. Creating it.
TicTacToe competitor, due Wed Dec 19, 8:00a Let's get this done before the holidays.
Running your competitor in the browser
  1. Download ttt4.zip (v. 4) into the cgi-bin directory associated with your PythonWebserver directory.  Then move the webserver.bat file into your PythonWebserver directory.
  2. Massage your competitor program: BuildingACompetitor.html
  3. Debug and run your competitor: RunningACompetitor.html
AI and unemployment:

New task: for Tues (12/18) 8:00am		 Create and submit an outline for the video we saw on Wed as well as the essay below.  The outlines should be short restatements of the arguments presented in the video and in the essay.  Submit to the homework server in .doc, .docx, or google-doc form.
1. "Humans Need Not Apply" video.
The Economist (magazine) has an excellent, though long, introduction to technological unemployment issues.  I'd like you to read the section on The Impact on Jobs (pp. 5 - 8) by Tues and outline the arguments and be ready to contrast that with the video you saw on Wed.
The rest of this long introduction is also very good.  I urge, though don't require, you to read the other sections.
Sick today. Presuming that you're using CoLab, work on the homework today if you haven't finished.  Send me a message if you can't run/test the server (v. 1.2) below at home.  Presentation postponed until tomorrow.
Python web server for your home machine Download this server (v. 1.2).  Instructions.
Tic-Tac-Toe

Homework #1: Thurs night, 11/29

Homework #2, Mon night, 12/3

Homework #3, Tues, 12/11 8am

Intro to tic-tc-toe computing. 
 
Homework #1: count the number of different boards and the number of different possible games (much larger number), remembering that, by our convention, "x" always moves first.  Write in Comments-to-Teacher: number of boards and number of different games.
Here's my answer to Homework #1.

Homework #2:  ... including some additional requests beyond what I mentioned in class ( so I pushed back the deadline by a day)

Homework #3:  We're almost there...  I'd like you to complete this Jupyter notebook
For this homework, here are a few test cases that you can run:

AllBoards = {}
print('x should win this one in 3 moves')
b='x_o_o___x'
CreateAllBoards(b)
AllBoards[b].print_me()
AllBoards[b].print_layout()

AllBoards = {}
b='x__xoxo__'
print('\no should win this one in 1 move')
CreateAllBoards(b)
AllBoards[b].print_me()
AllBoards[b].print_layout()

AllBoards = {}
b='_________'
print('\nthis should be a draw in 9 moves')
CreateAllBoards(b)
AllBoards[b].print_me()
AllBoards[b].print_layout()
Logic puzzles extra credit Create a logic puzzle solver to solve the Zebra/Einstein puzzle.  Report the number of backtracks (incorrect guesses) that it had to make in the Comments-to-Teacher, and also any comments on the task of writing it.  There's a homework slot for this extra credit problem with the arbitrary (and ignorable) due date of  11/27/18 11:59p (you're probably late already).
Logic puzzles
  • Here are a couple of simple ones from BrainZilla: Basic 1 and Basic 2 and a look at LSAT-type logic games.
  • Here's the biggie -- called the Einstein or Zebra puzzle
  • Here's an explanation of how one can analyze such puzzles.
  • Here's an example of the code (Jupyter notebook) for solving one logic puzzle (right-click to download).  If you're using CoLab, you can drag this file (after downloading) into your CoLab drive.  Take a look at the last cell in the notebook -- that's where all the data is.
The AI half-course survey is now available.  It's due Sun, 11/18.  If you haven't received an email invitation to fill it out, here is the survey: https://docs.google.com/forms/d/e/1FAIpQLSfoHaBEDZPGJgnFJIuq4UJ4b2x7B1XmO2tWJiQaZCz_eYQEvw/viewform?usp=sf_link
Take your time while filling it out.
Sudoku extra credit assignment, due Sun 11/18, midnight Here 'tis and it's updated with my correct measure of the number of bad guesses.
Read Machines That Think, 1/2 of chap. 4 by Tues, for discussion Read "The Limits of AI" chapter at least up to the section on "Red Flags" (pp. 125 - 153).  Note the following ideas: Strong vs. Weak AI, AGI, the "hard" problem, Asimov's Laws of Robotics, the short section on Ethics.
Sudoku Ex.1, due Mon, 11/12, midnight You'll be implementing the simplest Sudoku-solving rule.  Here are the details.  Note however, that you'll be adding more sophisticated and powerful rules to this one later, so keep your code modular.  Submit to the program-tester. You'll be given 2 seconds of CPU time -- you should not need that much (my program doesn't spend more than a half-second on any of the possible sudoku boards that you may be given). 

You're allowed to
import sys
and
import copy
because the copy library provides a deepcopy method that some of you may want to use.  If you want both libraries, you must ask for them in two separate statements, not
import sys, copy
Sudoku - 1 Here is a sudoku data file (Sudoku-boards.txt), that you'll use for testing your Sudoku programs.
As I sincerely promised you, I'm absent today.  Perfect day to work on the word-connection problem with your partner. 
I am, much to my students' consternation, enamored of open-ended, creative (read: ill-defined) questions.  Idea-connections, especially analogies, are central to my thought processes.  Those of you who are willing to read an exceptional (though long) essay on thinking -- in fact, one of the very best essays I've read in the last 20 years -- should read Analogy as the Core of Cognition, by the brilliantly creative Douglas Hofstadter.
The Word-neighborhood exploration project, due Sun, 11/4 midnight - Near the bottom of the Wordladders Homework, in the Challenge Problems section, I've included some ideas/questions for further exploration.  These were just a few of the ideas that occurred to me as I was creating that homework task. 
- The interconnectness of words is a fascinating area.  The word-to-word connection we've been using -- single char replacement -- is just one of many possibilities of character addition, deletion, replacement (and other, less minute connections, like anagrams, or even rhymes, homonyms, synonyms, etc.). 
- For instance, here are the results of a Washington Post contest.
- You and your partner should explore some ideas on word-connection, and come up with interesting results if you can.  You can also mention questions that you've explored that failed to blossom after research.
- Write a document about the questions and results (Google doc, MSWord, LibreOffice, pdf, txt) and submit it to the homework server. Both partners must submit their own copies.  Also, in the Comments-to-Teacher, indicate who your partner is.
Read part of Chap. 3, by Mon,  10/29 classtime. Machines That Think, first part of Chap. 3, pp. 85 - 103.
Wordladders Homework, (due Sat, 10/27, midnight)  
3 Searches explained! The Uninformed, Greedy and A* searches  (version 1.1 is here) are explained.
Absent today (Wed. 10/17): 1) I have slightly changed the instructions for the Pre-Wordladder assignment.  The change is that the "dictall.txt" file is now in the same directory as your program, and therefore your open statement should now be:
open("dictall.txt","r"). 
If you've already submitted your homework, change it and resubmit and retest, please.  You can, of course, retrieve your program using the "View Homework" tab.  Also, some of you may have failed the program-tester test because I was, at that time, moving the file and if so, simply retest.

2) I have posted the DAILY-Presentation Partner page where you register your partnership.  So do so (by Sun night, at the latest.  But why not now, that you have a whole period that you can dedicate to this task?)
  https://docs.google.com/spreadsheets/d/1LmvsRsZt0ULPMEF6aNhlzgLf0qvzQRgpJX2ueM_Jg0w/edit?usp=sharing
The pre-Wordladder assignment; revised: due Sat. 10/20 midnight The assignment is here.  This will be tested by the program-tester, so submit your file, then go to "View Homework" and test it.
The dAIly starteth soon  
What to know for Friday's test  
Priority queue as-a-heap optional extra credit assignment, due Thurs, 10/4 midnight Here's the assignment.
Create a Prioity Queue tester, code and results due Mon, 10/1 midnight Here are the specs for the priority queue tester.
Read the following by Tuesday, 10/2.
  1. Chap.2 of the book
  2. The Turing Test in the original: Computing Machinery and Intelligence by Alan Turing -- this is (possibly) the most famous paper about AI.  Read sections 1, 2 and 6; the other sections are optional.
Testing the Program Tester, due Thurs, 10/4, midnight Create the program sumline.py (docs here)
Here are the ProgramTester docs
Create a priority queue in a Jupyter notebook.  Due Fri 9/28/18, midnight
  
AlphaZero Read the first two pages of the research paper announcing AlphaZero -- this is the type of publishable paper you'll find in AI research.
BTW, for those of you who have Netflix accounts, there is a documentary there called ... "AlphaGo" about .... AlphaGo.
Create classes in a Jupyter notebook to implement a binary tree for sorting.  Due, Thurs, 9/20 midnight.

 Here is my version of the BinTree class in Notebook and HTML versions.

As a sample, here is the Notebook version of a singly-linked ordered list, as well as the HTML version.

Your nodes must have a value instance variable that is comparable with the "<", "<=" and "==", ">=" and ">" operators.

Your BinTree class is intended to hold nodes in positive order so that they can be used to produce an ordered list of node.values.
The BinTree must support the following methods:
__init__(A), where A is a list that might be empty (A is a unordered list of values that are comparable -- there may be duplicates)
insert(v) (inserts a value v into the tree)
has(v) (returns as Boolean indicating whether v is in the tree)
get_ordered_list()  (produces an ordered list of the values in the nodes)
clear()  (removes all nodes in the list)

The clear() method is tricky.  What you want to accomplish is to set every node's pointers to other nodes to None.  If you have just 2 pointers to the left and right (larger and smaller) children of that node, then walk the tree carefully, and set those pointers in every node to None.  Once all of the pointers to a block of memory (in this case, a node) are removed, that block of memory becomes inaccessible, and should be collected by the garbage-collector later.
Python Classes Here is some quick documentation on classes in Notebook form (so you can play with and modify them) and webpage form.
PythonReview2.ipynb Download and try the additional Python review topics.  Alternatively, here it is as an HTML page.
For Mon. 9/17: Read the Preface and Chapter 1 of Machines That Think, and take note of these terms:
Homework 1, due Sun, 9/16 midnight Download the Jupyter notebook from here.  Submit the modified notebook(.pynb file) to the homework server, and as a Comment-to-Teacher, print the 4 numbers that you got when working on the last notebook cell, and also write a comment as to what those numbers mean.  You might try playing with different values of the m parameter, to see what happens.
Python 2 vs. 3  
Python review Here's a Jupyter notebook (right-click to download).  Load it into a working Jupyter server (at school, or at home, or Google's Colab) and:
- read all of my Python review docs (#2 and #3) in the first cell
- in your browser, bookmark the PQR reference
- I have left a cell below each review topic in the notebook for you to play in.  Play in them.
Richard Gruet's Python page This is my standard quick-reference for Python.  It's the first place I go to for a quick look at the operators and methods of built-in datatypes.  I often have this up in a different browser tab with programming.   Although it's only really accurate for v. 2.7.x, there is very little difference between this and 3.6.x (and anyway, the 3.6.x+ compiler will warn you if you have sinned).
First task: fill out your Profile on the Homework server.
  1. Go to the main class link page (http://bert.stuy.edu/pbrooks)
  2. Click on the Homework/Grade server link
  3. Choose the Profile menu item
  4. Choose your period and name
  5. Log in with your OSIS number as your password
  6. Fill out your email address and preferred first name only, DO NOT CHANGE YOUR PASSWORD YET.
  7. Save: (Change Profile button)...
  8. (optional, but recommended): now you can change your password for this Homework server, if you want.
  9. REMEMBER this password!
Help from Mr. Brooks Feel free to come and see me during periods 6, 7, or 8 in room 301 (just walk in) or by appointment beforehand just after school also in room 301.
Sending email to Mr. Brooks:
 Send mail to: pbrooks@stuy.edu

You MUST include your name in the subject line or body of the message, otherwise I won't know who it's from.
Stuyvesant bell schedule  
Homework/grade server  
Support Wikipedia