Assignment 2 more preview
- basic step: solver similar to TicTacToe example
- deal with three outcomes, win, loss, draw
- many improvements possible
- move ordering: look at (probably) good moves first
- find moves that help in more than one direction
.
.oo.. intersection of two promising
o patterns
o
.
.
.ooo. playing here gives two good
o threats
o
.
- evaluation function: how good or bad are states?
Example:
- how many possible 5-in-a-row
are there on the board?
- For us? For opponent?
- How close are they to complete?
- move pruning: recognize threats
- In these situations we can greatly restrict the set of moves to look at
1. immediate win:
xxxx.
xxx.x
xx.xx
xxx.xxx
etc.
2. block opponent's immediate win:
xoooo.
ooo.o
oo.oo
2b. Give up when opponent has double threats
.
xoooo.
....o
....o
....o
....x
3. win in 2 moves
.xxx..
.x.xx.
- optimization:
- where does your program spend time?
- can you find smarter ways,
save computation?
- important goals: keep soundness and
completeness
- you program should never give
a wrong result
- your program should never cut
all the winning moves
- some rules are only heuristics, not
exact. Can still use them for move ordering, but not as absolute truth