Artificial Intelligence

Spring 2020 -- Peter Brooks

The (ever-changing) Syllabus and readings


Coding exercises using information theory. Due, Thurs, 5/28, midnight. Here are some coding exercises using variable-length coding. 

There is an algorithm called Huffman Coding that will, in fact, produce the most efficient coding for a situation like we covered in class.  Namely, given a coin with a certain number N of faces, with each face F(i) having a certain probability P(i) of coming up, and given that you wnt to group together the results of G flips, what is the most effiicent coding?
Here's a tutorial on how the Huffman Coding works.
deeplearning.ai This is a newsletter/blog by Andrew Ng's group on AI news.  Check out the A.I. Eurovision Song Contest, among other news
And now, for something completely different... Of course, you don't have any time for this....but here's a remarkable feat of puzzle-solving: solving a Sudoku board (with some additional rules) knowing only 2 of the 81 values.  Solving the “The Miracle Sudoku”
Information Theory I've created a set of notes on the Shannon Theory of Information.  We'll be going through these ideas.
Real-Machine Learning! MENACE: A TicTacToe-playing machine, that learns to play TTT well, built out of matchboxes containing beads, invented by Donald Michie in 1961.  Video.
Teachable Machine Machine learning inside a browser.
The Traveling Salesman Problem (TSP) homework due Mon, May 11, midnight We'll be talking about Genetic Algorithms as applied to the TSP.  You're going to have a crack at the TSP -- here are the instructions.
Here's the Genetic Algorithm quick tutorial video.

For those of you who were wondering if a solution to TSP was really important: read this.
Monday, Apr. 27
MiniMax algorithm (and Alpha-Beta pruning)
The MiniMax Algorithm is really, down deep what you've been using for your TicTacToe competitors.  So here are two videos that explain both the MiniMax Algorithm and also the Alpha-Beta Pruning Technique (which you're not using using).

1. Sebastian Lague explaining MiniMax and Alpha-Beta (11 min).  Good and clear in the general description, although the alpha-beta code is not easy to follow.

2. Patrick Winston -- MIT OpenCourseware (48 min)
Patrick Winston of MIT talks about chess, MiniMax, Alpha-Beta, progressive deepening, and some history.  Winston is one of the old men of AI -- his AI book used to be the standard textbook in AI. His lecture here at MIT is from 2014, before AlphaGo.  At about minute 12:00 he appears to copy my technique of estimating total number of computations for a combinatorially explosive problem (his lawyer will hear from me).
Thurs. Apr. 23

Final TTT competitor that can be played with the Netlogo-UI, due Monday, Apr. 27, midnight
Here are new (corrected - version 2) instructions for completing the TicTacToe competitor and testing it.  Download, unzip and read the ReadMe and get started.  (The code template had a bug).

There's a talk, this Sat. afternoon at 4:00 by the head of AI at Uber, and the head of Applied AI at Google.  You need to register to see this talk, by midnight tonight (4/23). 
Wed. -- I'm not "in class" today (minor family matter).. We'll continue TicTacToe on Fri, with the Daily Digital tomorrow (Thurs).
TTT #2, due after Tues, Apr 21, midnight Preparing for the TTT competitor...  CreateAllBoards() is a function that will hold all of the relevant information about every TTT board in preparation for using that information in computing the best move given any valid middle-of-the-game board.
Essay on thinking and simulation.   Officially due Wed night, with leniency to Sat. night. Write an essay on the two questions posed here
Tic-Tac-Toe, Due Mon 4/6/20 Here's the first TTT assignment -- calculating how large the combinational space to explore is.  Upload code and also type results into Comments-to--Teacher
Here is some code to help your processing...
Monday, 3/30 Zoom meetings all this week during period 3.
See below for the reading assignment, due by Monday.  We'll talk about this.
The reality of simulations, and about intelligence and  consciousness and the Turing Test. Computing Machines and Intelligence by Alan Turing (read parts 1, 2, 6 and 7)
A Coffeehouse Conversation on the Turing Test, by Douglas Hofstadter  (you needn't read the Post Scriptum section at the end)
The Seventh Sally by Stanislaw Lem  (much shorter sci-fi short story)
Fri, 3/27 Zoom Meetings will be at 9:30, except lab days which will be announced here ahead of time.
Meeting ID/Pwd will be sent to you by email (keep that data for the future).
Thurs, 3/26

Smart Sudoku solver due Sun, 3/29, midnight
Zooming today at 9:30 as usual: Meeting ID: 940-161-203

Here are 8 Sudoku boards (the first 3 you already know).  Test your smarter solutions on these boards.  Once more to test your smart program (called, say: sudoku-smart.py) against board A4-1, you should be able to run the program with the following command-line arguments:

python3 sudoku-smart.py  Sudoku-boards-Master-unsolved.txt  answer.csv  A4-1

...and get just the 9 lines of the solution in in CSV form written into answer.csv.  You should also print out (to the console) the number of backtracks and the elapsed time.

Show your solver data: You should also fill the Google spreadsheet with your naive and smart data for boards A6-1, A7-1 and A8-1, which are in increasing difficulty order.  BTW, you may have trouble waiting for your naive solver on A8-1 (long time). 
Note: each cell of that spreadsheet should contain 3 numbers, and here's how to format them.  Let's suppose your data for A6-1 was the following: naive backtracks = 450, smart backtracks = 105.  Then, the cell entitled "A6 backtracks" should contain the following string:  "450 / 105 / 4.29", with the 3rd number being the improvement ratio between the first two (just 2 or 3 significant digits, please). Do the same things for the naive and smart times and their ratio.  If the number of backtracks for A6-1 is 0 (congrats), then the cell should read "450 / 0 / inf".

The Program Tester is up for this smart solver.  The tester's command-line will look like the one above, except the last argument could be for any one of the 8 boards (A1-1  ...  A8-1) from the Sudoku-boards-Master-unsolved.txt file.  I have allowed up to 10 seconds of Program Tester CPU time for your solver (it should take much less than that).
Wed, 3/25 Working on the smarter Sudoku version.
Tues, 3/24 Zoom at 9:30, as usual.  Meeting ID: 805-292-466 (no password).  We'll go over naive Sudoku backtracks and times.  And then onward, into the smartlands!
Mon, 3/23 A day to finish your naive Sudoku solvers and post on the homework slot.
Also: look at the office hours and checkin links above.  I'm starting the office hours on Mon...
Thurs, 3/19 Zoom session starting our regular class time: 9:30am  (sorry, latebirds) -- I'll be going over the Naive Sudoku solver homework due this Sunday.
This is your first non-trivial programming assignment, so start early, post questions on the Q&A forum.
Updated information

Create the:
Sudoku: the Naive solver

Due, Sunday, 3/22, midnight
Here are a number of Sudoku boards that we'll be working with. 
Here's  -- some info on the coding for this problem.
Here's the main loop for my  naive (simplest) version

Here are my backtrack numbers for various boards (note that they're not strictly correlated with NYTimes's estimation of difficulty):
A1-1,Easy-NYTimes,unsolved: 260
A2-1,Medium-NYTimes,unsolved: 27,917
A3-1,Hard-NYTimes,unsolved: 10,616

Here are the instructions for program-tester.
Allowed imports:
import time

import sys
import copy

Your program will be given 3 command-line arguments:
1) name of input file (which will contain a subset of Sudoku boards)
2) name of the output file
3) name of the board to solve: that will be one of the following:
A2-1 or A3-1

The output file should be just the 9 lines of the solved board -- just like in the file Sudoku boards.  Nothing else.

For the homework server submission:
The homework slot should contain more information, though.  I'd like you to run your program on all 3 of the boards in the Sudoku-boards file (A1-1, A2-1, and A3-1), and put into the Comments-to-Teacher the number of backtracks you've had for each.
Tues, March 17

...we're moving online!
We're going to try out ZOOM!

You should all have received email from me about 2 sessions on Tues (12:00-noon, and if you can't make that one: 6:00pm), with instructions and meeting IDs and passwords to try out this free online video conferencing software. If you're going to be using your smartphone instead of a computer/tablet, download the Zoom app ahead of time.

Afterwards, fill out the survey form (even if you couldn't make a session):
https://docs.google.com/forms/d/e/1FAIpQLSen_IB6LqX1gY5pLzw3QGW2fh1AXbzeXG7kQMyR1WFM4CAvCw/viewform?usp=sf_link
Monday, March 16
Schools closed until April 20
All right, we're going to move forward.  I am working on the Sudoku program tester, which will be available shortly along with (perhaps different) test code.  Stay tuned to this channel...
Parent-Teacher conference design, due tonight (Wed 3/11) or before class. Give me your design thoughts, in whatever form to the homework server --  Google doc, MSWord, webpage, complete running system (auto 100 grade)
Moore's Law Exponential growth: There's a wonderful series of charts by Ray Kurzweil on exponential growth of a lot of things including Moore's Law.  This is a blow-your-mind site.  Take a look at some of the other charts on this site, for instance charts 67, 20, 50, 70, 71 -- each displays exponential growth (key indication: an approximate straight line on a logarithmic chart).
AI history and present, due Wed 3/11 in class
  • read Chap. 3 of Machines That Think.  Note that, by now, this is not the present but just recent history (in AI-years)
  • Read through these histories Timeline of AI. (esp. Pascal, Leibniz, Babbage, Boole, Russell & Whitehead, McCulloch & Pitts, von Neumann, and then the modern era).
    and Timeline of Machine Learning (Bayes, Markov, Rosenblatt, Minsky & Papert [remember Netlogo?], Deep Blue, and then the modern era [2010+])
Python test Here are my answers (Jupyter Colab notebook)
Surveillance vs. Privacy: Thurs Read the article "NYTimes report on surveillance in China" from the link on the Syllabus above.  Also choose and read another article from the same "Security / Surveillance / Privacy" section or another article from elsewhere on the same topic.  Be prepare to discuss and support your side of the argument
Sudoku warmup, due Sun, 3/1 midnight Sudoku swapped elements.  Intstructions are here

Here's my answer code.  Here's the program-tester input data.  Here are the program-tester answers.
AI topics/news Here's a link to The Batch -- a very good newsletter on current AI topics. A lot of information digested by that organization headed by famed AI researcher Andrew Ng.
Presentations will start in 2 weeks (March 9) Post your topic at least one week in advance of your presentation. Also, first poster on a topic gets it (but there are so many, don't worry).
Sudoku! Here is the format we'll be using.
AI Summer camp The following has come wizzing into my mailbox: announcement of an AI summer camp here in NYC.
Exercise in creating classes, due Sun, 2/16, midnight  Create a program, called MakeFriends, that can be called from the command-line as:
$ python MakeFriends.py  input-filename  output-filename
which will take commands in the inputfile and write its answers to the output file. 
Here are the details, some of which have changed (2/14, 12:20AM)
Sample of a class Here a Stack (last-in-first-out) class in a notebook.  Download and try it out and understand it.
Here is a much more complicated list -- a singly-linked ordered list -- to show a more involved use of classes with Nodes.
Presentations You (solo) or y'all (duo) will be giving a full-period presentation later in this semester.  Here is a signup sheet.  Next to your name, indicate with "y" or  "n" whether you'll be presenting with a partner, and if so, who.
Homework: reading and writing CSV files by Tues night (2/11)

In a Jupyter notebook, create a function called DoIt(alist=None), that either takes a list as a parameter, or if no list is available, uses sys.argv as the list for incoming arguments (sys.argv will be used when you extract this code from the notebook and run it on the command-line).  The incoming arguments are: 

  1. the name of the program (any name will do, this is ignored)
  2. the name of an input CSV file
  3. the name of an output CSV file

So, when you supply a list to DoIt(), it must contain 3 elements, above.

Create an input text file for testing.  The file should have any number of lines. Each line will have a sequence of string elements separated by commas.  Each line will have one or more positive integers and possibly other elements.  For each input line, write a line out to the output file the number of positive integers and their sum, separated by a comma.  If the input line contains nothing, no output line should be written.

So, if the input file contained:
1,2,3
good,12,luck,-4

the output file should contain:
3,6
1,12

Assuming that your program is called fred.py, you should be able to call it with the 2 arguments of input and output filenames from the command line.

Testing your program on the homework server...

1) Upload your program (.py file) to the homework server slot "CSV-test".
2) Go to View Homework and press the Test Program button.
3a) If your program fails with an error message, fix it and resubmit
3b) If your program fails with a message about incorrect output, then read the requirements of the program above VERY CAREFLLY, and see if you can figure out why and fix and resubmit.

Reading files Reading files is simple in Python -- open with f=open(filename,'r') -- provided you can access the directory (requires authentication in Colab), and you can navigate to it.

Here's a notebook describing the file-reading procedures in Colab: File_Reading_2.ipynb. Here's a file called afile.csv.  Download the notebook and the file, and upload them into Colab.  Create a notebook that reads the file and print it out.
Monkeys and Typewriters The real experiment.  With the published result.  And, of course, there's a Wikipedia article.
Monday, Feb. 3: Learn about... Python Classes Yes, you can program classes and instances in Python, except it's a lot less bossy than Java.  Here's my quick intro to Classes.ipynb (download).
First homework, due Mon, 2/3  midnight Here's a notebook talking about an old math problem, and asking you how to solve it in a variety of ways, numerically.  Fill in the notebook with your answers and submit it to the homework server.
Python review notebooks Download these 2 notebooks, and load them either into your own laptop version of Jupyter or upload them to your Google drive, and open them there with Colab.  These are reviews and review exercises. Do them.  You'll need the ideas therein. 

PythonReview-1.ipynb
PythonReview-2.ipynb

You might was to sneak a look at how these notebooks are written internally (JSON format).  Of course, I don't think they're ever written directly by humans.
Python!  Jupyter Notebooks! We'll be using Python in this class.  Feel free to forget the arcane details of Java, but retain at least some knowledge of classes.

Learn about Jupyter Notebooks using Google's free Colab environment here.  And/or you can use Jupyter notebooks by downloading and installing the huge Anaconda distribution from here.

If you've never been introduced to Python or are pretty rusty, take a look at Python.org's suggestions for learning.  If you're willing to read, I recommend Head First Python.  Also CodingBat for quickie exercises.

Learning Python resources:
My Python cribsheet
Python topic explanations from Intro-2
Excellent Python function/method guide (for v. 2.7 but almost everything is still true in 3.x)
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 5, 6, or 7 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