Heuristic AI

Problem and Instance

  • Basic idea from algorithms

  • An instance is

    • Some specific description of a situation

    • Some description of what is wanted in that situation

  • A problem is a collection of related instances

  • A class is a collection of related problems

AI Problems

  • In AI, a problem is likely to be

    • Fuzzily specified: want a "smart answer" that is "good enough"

    • Hard: No efficient algorithm is known to exist for large / hard instances

    • Human-tractable: Humans demonstrably do a reasonable job on real-world instances

  • "AI Complete" problems are those for which a good solution will require general intelligence

  • (Conversely, a general intelligence would handle standard algorithms problems)

Problem: Pathfinding

  • Instance: A map

  • Solution: A good route through that map

  • Issues:

    • How much detail is in the map? Like a Google map? A treasure map? A photo?

    • Similar: How is the map represented? A graph? An image? Something else?

    • What is a "good" route? Short? Low-effort? Safe?

  • Dijkstra's Algorithm or similar search is good for small instances of simple problems

  • Super-fancy AI techniques are used on some kinds of real-world problem


  • Abstract away "irrelevant" details

  • For example, take image to Google Map (fancy graph), Google Map to simple graph

  • Hard to tell what is irrelevant


  • We study games because they are

    • Hard: seem to require some intelligence

    • Pre-abstracted: "simple" models, clear rules, "win condition"

  • "Game" is a bit ill-defined: certainly includes single-agent and multiple-agent things

  • Games range from competitive to cooperative

Shut The Box

  • Shut The Box is a simple multi-player probabilistic dice game vaguely related to Yahtzee

  • We will use the single-player 9-digit game with "digital" ("say what you see") scoring

  • I have built a single-player solver for this game. We will learn how it works. Today is not that day

  • (rules, demo)

  • Let's build some Python AIs for this game

Shut The Box: Setup

  • "Obvious": Represent a state as a set of remaining digits and a dice roll

  • Apparently a state is an instance to be solved

  • Solution? A "better" state

    • Can be greedy: pick the next state with lowest score

    • Greed is not necessarily good: actual scoring is at the end

    • Now we're balancing two things: lower score / "better" numbers

Shut The Box: Code

  • AI code is a lot of setup per unit intelligence

  • I've done some of this setup for you here

  • Let's look at the code

Shut The Box: Player

  • Just choosing randomly from the legal moves is not AI (or is it)?

  • But it's a good place to start

  • We'll then build stronger heuristic rules and evaluate via play

Shut The Box: Evaluating the Player

  • Could try to do a full analytic evaluation

  • Much easier to play a bunch of games and see how it does

  • What is the success measure? Mean? Number of perfect scores? Something else?

  • Will the AI vary depending on what success measure is chosen? (yes)

Last modified: Wednesday, 2 October 2019, 2:26 AM