Transcript x - HMC Computer Science

The CS 5 Herald
Goodwill Gesture Goes Awry
Claremont (AP): Seven rooms were damaged in
a Harvey Mudd College dormitory Tuesday
evening after a misguided attempt to cheer up
sleep-deprived students. “We were approached
by a group of three penguins who wanted to sing
Christmas carols,” explained a witness. “They
promised that it would help us study.” Instead, the
raucous squawking of the untrained and
untalented birds quickly led to a violent dispute
between supporters and detractors. One student
attempted to encase the singers in foam rubber,
but a second set fire to the material in hopes of
freeing the animals. The resulting explosion
unleashed a conflagration that spread to North
Dorm, where there was extensive damage.
However, losses in North were estimated at only
$35.47, due to the advanced age of the furniture
“Forced” Methods
Some methods are required by language
Must always have __init__
Good to have one of __repr__ or __str__
Others not required, but very common
copy (to do deep copies)
show (to print self)
Construction and Destruction
Constructor (__init__) builds an instance
Called when object created
Best to initialize everything to reasonable values
Destructor (__del__) rarely needed
Unlike C++
Unpredictable when (or if) it's called
Best to avoid
__repr__ and __str__
__str__ implements the str(…) built-in
Automatically called by print
__repr__ should give Python syntax
E.g., Date(11, 26, 2007)
Automatically called when interpreter is
returning a result
If __str__ undefined, __repr__ used
Quick shortcut: only do the latter
Class Globals ("statics")
How to put debug in your Date class?
Don't want to depend on user's debug
Might not exist
User might not care about Date debugging
Solution: variable that's global within class
Only one copy across all objects
Also useful for things like counting objects
A Self-Counting Class
class Counter:
instances = 0
def __init__(self):
self.id = Counter.instances
Counter.instances += 1
def unique(self): return self.id
Computational Classes
It’s often useful to define classes that provide
mathematical objects
Infinite-precision numbers
Rational numbers
Matrices
Modular fields
Writing code using these classes can be painful:
y = add(mult(a,mult(x,x)),add(mult(b,x),c))
Operator Overloading
Overloading means giving an operator (or
function) a definition that depends on
context
Example: a/b means something different
depending on whether a and b are ints or
floats
Some languages (including Python) let
users overload operators at will
y = a*x*x + b*x + c
Overloading in Python
Most Python operators can be overloaded
Just define a special function in a class
Annoying exception: plain assignment
Many finicky rules
Names aren’t always obvious
Some operators have “forward” and
“reverse” versions
Some operators derive from others by
default
Basic Overloading
class MyMath:
def __init__(self, …): …
def __add__(self, rhs):
# Only works if rhs is a MyMath
result = self.value + rhs.value
return result
def __sub__(self, rhs): …
# etc.
Important Details
Overloaded operators should return a
result
Should not modify “self” or right-hand side
Often useful to have copy method
Exception: Ops in “i” series modify “self”
Possibility of rhs not being same type
Many packages don’t handle this case well
Overloaded Operator Naming
+
*
/
/
//
%
**
add
sub
mul
div
truediv (future)
floordiv
mod
pow
+ pos
- neg
abs
int
float
complex
==
!=
<=
>=
<
>
eq
ne
le
ge
lt
gt
Remember, every name
needs two underscores
before and after it!
The r… and i… series
radd, rsub, etc. implement reversed operators
If x is special and y is built-in (e.g., integer), then x+y
invokes x.add(y), and y+x invokes y.radd(x)
However, if radd isn’t defined, Python will try y.add(x)
iadd, isub, etc. implement incremental operators
E.g., x.iadd(y) implements x += y
Modifies x
Should return None (i.e., no explicit return value)
The Alien’s Life Advice
Ask questions when
you don’t get it!
It makes you
seem human!
OK, maybe you
won’t get a date
with Xohptzl, but
you’ll learn more!
Worksheet: Designing a Class
Design class Rational, to store rational
numbers (integer divided by integer)
Choose reasonable string representation
Enumerate data, "special" functions,
things it should be able to do
E.g., a.add(b) adds b to a, modifying a
I looove rationals!
They’re so logical!
More On Rationals
Should there be any “extra” methods
beyond the obvious mathematical ones?
Rules for Connect Four
Tic-Tac-Toe with stacking
7x6 board
Checkers slide down onto top of column
Four in a row (including diagonal) wins
A C4Board Class
class C4Board:
width = 7
height = 6
def __init__(self):
board = [width*[0]
for i in range(height)]
…
Artificial Intelligence
Catch-all term for anything that “appears human”
Eliza
Chess programs
Expert systems
Many approaches
N-ply lookahead:
good for games
Looking into the Future, Part I
Basic idea
Guess a move
See whether it makes your position better
Repeat for many guesses, pick best result
What defines “better”?
Simple answer: use board evaluation
function
Evaluating a Connect-4 Board
What are some ways to numerically rate a
Connect-4 board?
If opponent has won, 0.0
If I have won, 1.0
Otherwise…
?
Looking Into the Future, Part II
Problem: evaluating a board is HARD
Solution: look at where the board leads
For each possible move:
Make the move in “trial mode”
For each possible opponent's response:
Make that move in “trial mode”
Evaluate that board instead (how?)
Return value of opponent's best option
This is the “worst case” for us
Our best move is “best of the worst cases”
Limiting Recursion
When do we stop?
That's easy:
When we find path that leads to a win
No matter what opponent does (e.g., Nim)
When all paths lead to losses (sigh)
When we have explored all possible moves
The Move Tree
X
O
X
O
X
O
X
O X
X O
X
O
X
O X
X
O X
X
O
X
O
X
O X
O X X
O X
X
O X
X
O X
X
Explosive Growth
Connect-4 move tree has < 742 nodes
Roughly 311×1033
Tree size depends on two parameters:
Branching factor per move, B
Maximum moves in game, N
Approximately BN possibilities
Chess: B≈35, N≈150
Backgammon: B≈300, N≈50
Limiting Growth
Simplest strategy: stop looking ahead
after evaluating N moves (“plies”)
Alternative: stop after t seconds elapsed
Better: prune move tree
Don't follow a path if first move is way worse
Don't explore if already found better choice
Alpha/Beta pruning
The Curse of the AI Researcher
AI is always defined as “something a lot
smarter than what my computer can do”
Corollary: if my computer can do it, it's not
artificial intelligence
⇒ Every time we achieve AI, people decide
it's not really AI!