Transcript Search methods

CO2301 - Games Development 1
Week 11
Search Methods
Gareth Bellaby
1
Topics
• Search
Methods in Traditional
Games - Tower of Hanoi example
• Combinatorial Explosion
• Chess
2
Search Methods in Traditional
Games - Tower of Hanoi
example
3
Traditional Games
The approach described in this lecture is not one
that is used much within computer games.
Useful for games such as Chess. I've called
these "traditional" games for want of a better
phrase.
The approach may be applicable to certain
problems in modern computer games.
4
Towers of Hanoi (1)
A simple game played with three pegs and a pile
of disks of different sizes. The pegs are stacked
on a peg in order of size.
• The object is to stack the disks onto a new peg.
• Only one disk may be moved at a time.
• A disk can never be placed on top of a smaller
disk.
5
Towers of Hanoi (2)
6
Lists
The disks can be represented as numbers:
the small disk is 1
the medium sized disk is 2
the large disk is 3.
This will allow us to easily describe the rule about "A disk
can never be placed on top of a smaller disk".
A useful (and common) representation of a problem is the
list structure.
A empty list is given by: []
7
Lists
The disks on a single peg can be represented as a list.
One common convention is to use square brackets for a
list. The elements of the list are separated by commands.
A peg with the small disk on top, the medium sized disk in
the middle and the large disk on the bottom would
therefore be: [1, 2, 3]
The state of all three pegs would be represented by a list
of lists: [ [2,3], [1], [ ] ]
8
Towers of Hanoi (4)
[1,2,3][ ][ ]
/
\
[2,3][1][ ]
|
[3][1][2]
[2,3][ ][1]
|
[3][2][1]
9
Towers of Hanoi (5)
[1,2,3][ ][ ]
/
[2,3][1][ ]
\
[2,3][ ][1]
|
|
[3][1][2]
[3][2][1]
|
|
[3][ ][1,2]
|
[ ][3][1,2]
[3][1,2][ ]
|
[ ][1,2][3]
|
|
[1][3][2]
[1][2][3]
|
|
[1][2,3][ ]
|
[ ][1,2,3][ ]
[1][ ][2,3]
|
[ ][ ][1,2,3]
10
Search trees
11
Searches
Search is a basic problem-solving
technique.
Grow a tree from the start position to
the goal.
12
Trees Again...
The Tower of Hanoi problem can be represented as a set
of states.
A new state is generated by applying a rule.
The states form a tree structure.
A route through the tree to a goal state represents a
solution.
Search is a basic problem-solving technique.
13
Search Trees
A tree is:
• A representation of a problem
• A way to solve the problem using a search
technique, e.g. breadth-first search, best-first search,
etc.
14
Conceptional Search &
Pathfinding
Pathfinding searches a map. The map is just a
representation.
A Conceptional Search searches a problem space.
The space is just a representation of states within the
problem.
Dijkstra's algorithm uses a graph. In other algorithms
the nodes, linked together, can form a tree-like
structure.
15
Rules
Rules are used to generate new nodes. For
example, in the pathfinding exercise you used a
grid and rules to move north, south, east and
west.
For the Towers of Hanoi a good representation of
the problem state is:
[1,2,3][ ][ ]
A rule would be "Can only remove the topmost
disk" and, in this representation, this would be
the leftmost number in the list.
16
Search
A state space (or problem space) represents a
problem.
Indeed the full tree represents the whole of the
problem in every possible permutation.
A state space is a graph whose nodes
correspond to problem situations. A given
problem is a path in this graph.
17
Search Tree (Graph)
The nodes, linked together, form a tree-like
structure.
The whole tree is described as the search
state (or problem state)
Lots of generate and search techniques
have been developed.
18
Search Tree (Graph)
• Nodes
correspond to situations, e.g. a
node represents a move, or position, in a
game.
• A link (or arc) between nodes represents
a legitimate move, or action, according to
the rules.
19
Search Tree (Graph)
A specific problem is defined by:
• state space
• start node (root node)
• goal condition (may be
more than
one node)
20
Evaluation Function
The Tower of Hanoi problem was represented using lists.
Lists are a commonly used technique in AI for
representing a problem state.
Another common technique is to describe a problem
using a number.
A number is an evaluation of a state, e.g. a node (a move
or position) in a game.
Numbers are useful because they mean that states can
be compared with one another.
21
Combinatorial Explosion
22
Combinatorial Explosion
• Combinatorial Explosion:
• A rapid increase in the amount of possible outcomes
due to the large number of combinations.
• Towers
of Hanoi is a simple problem, but most
problems are far more complex.
• A directed search is used to overcome the problem of
combinatorial explosion. A heuristic is used to guide the
search and hopefully remove the need to evaluate every
possible permutation of the problem.
23
Travelling Salesman (1)
• An
example
explosion.
of
combinatorial
• Plan
the quickest route for
salesman visiting different cities.
a
• Initially appears a simple problem.
24
Travelling Salesman (2)
nottingham
20
leicester
15
derby
37
25
Travelling Salesman (3)
nottingham
20
leicester
30
15
37
derby
18
40
sheffield
26
Chess
27
Chess
• Consider chess. How would you:
• Build a chess game?
• Represent a move?
• What are the rules?
• Create an evaluation function?
• Wwhat are the characteristics of the game of chess?
• The same approach as solving the Tower of Hanoi
problem
• Each
node of the tree represents one move (or
position) in the game
• Each
layer of the tree is all of the moves either
Black or White could take that turn
28
Chess and Combinatorial
Explosion
Average number of moves in a single turn of
chess is 35.
The number of moves in an average game is
around 50 for each player.
Therefore, full evaluation of a game requires
35100 moves
29
Heuristics
Heuristics can be used to guide search.
• non-heuristic: blind search
• heuristic: directed search
Chess heuristic: put pawns into the center
squares.
Employ a search algorithm.
30
Chess
• 2-player game
• Perfect information
• Certain
outcomes, e.g. success and failure
clearly defined for the game and for a move.
• What about computer games?
31
Computer Games
•
•
•
n-player games. This does not mean that there
are necessarily lots of people playing the game
but that lots of units or NPCs are moving at the
same time (contrast to one piece moving in
Chess or Draughts).
Imperfect information
unpredicatable.
-
outcomes
are
Success and failure may not be clearly defined
for the game or an instance within the game
(The player has cleared an area of enemies but
how much life and ammo has been lost?).
32