Transcript ppt - UCD School of Computer Science

COMP4031/COMP4631
2006-7
Artificial Intelligence for Games and Puzzles
Dr. Arthur Cater
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
1
Course Web Page - http://csiweb.ucd.ie/Staff/acater/comp4031.html
As time progresses, Lecture Notes and Assignments will be added. Watch
for them!
Assessment will be partly by examination (60%) and partly by
programming assignment (2x 20%).
• Assignment 1 (20% of unit) : set in week 4 and due in week 8.
• Assignment 2 (20% of unit) : set in week 7 and due in week 11.
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
2
What sort of Games and Puzzles?
There are two broad categories of multi-player games:
•Parlour Games of a primarily intellectual character
• Chess, Poker, Draughts, Backgammon, Connect-Four, …
• Physical attributes of a player (dexterity, strength, steadiness, speed) have no real
bearing on the game
•Games of a sports character
• Soccer, Tennis, “finger-twitching” computer games, …
• Physical attributes are important (too)
We will deal almost exclusively with the “primarily intellectual” games, and their close
kin, combinatorial puzzles.
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
3
Is this just frivolous?
Certainly it should be some fun: interesting, entertaining, challenging. Further,
•Studies of game playing have led historically to valuable spin-offs:
• In mid-17th Century, mathematicians Pascal, Fermat, and others laid the
foundations of probability theory, and hence statistics, arising from a study of
gambling games (though beaten by Cardan by a century)
• In 20th Century, von Neumann and others formulated game theory, which now has
applications in economics and commerce - being used to design auctions for
telecoms bandwidth for example, and guiding corporate takeover strategy
•AI for games has direct commercialisation possibilities
• chess machines, in-flight entertainment consoles, computer games with AI-driven
opposition
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
4
Is this just frivolous? (2)
•Games provide a proving ground for AI (and cognitive science) theories of mentality:
• perception, representation, reasoning, learning, modelling, risk assessment, …
•There may be prizes to be won
• $1m “Ing prize” for Go sadly no longer available
• Prize for beating Taiwanese junior Go champion
• Prize for Arimaa
•There is fame and prestige in beating champions, winning tournaments
•There are still scientific open problems to be solved
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
5
Parlour Games: “The Three Games”
Three particular traditional games show up a further significant division among
competitive parlour games:
•Chess - “last man standing” type of game
• There are many games with this flavour. They are characterised by a race to
achieve some goal, often involving capture or destruction or immobilisation of the
opponent.
•Backgammon - “the gods help those who help themselves” type of game
• In games with this flavour, there is a chance element, depending usually on dice or
cards. More skilled players will nevertheless usually win.
•Go - “take the lion’s share” type of game
• In games with this flavour, players compete for shares of a resource of some kind.
To win you need not win everything, but through give-and-take, just win a greater
share than the opponent.
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
6
Last-Man-Standing game: Chess
Chess is the dominant intellectual game in the west.
In AI it is the most heavily researched game by far.
After about 50 years work, a chess machine was
developed which beat the reigning world champion,
Garry Kasparov.
Two players each have six kinds of piece, each with
its own movement rules. Players alternate play,
moving one piece at a time, sometimes capturing and
removing an opponent’s piece.
Win by “checkmate”, where the opponent has legal
moves but none of them will prevent immediate
capture of the king.
Note a mirror-image symmetry, top-to-bottom with
“colrev” - colour reversal of pieces.
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
7
Last-Man-Standing game: Draughts / Checkers
Draughts (Checkers) is played on a chessboard, or a
similar board 10x10.
A program beat the then world champion, Tinsley,
in ill health, in the 1990s.
There is initially just one kind of piece, which can
move one square along diagonals in a forward
direction. Upon reaching the far edge they are
promoted to “kings”, able to go backward too.
A piece may capture an opponent piece by hopping
over it to a vacant square beyond. Many captures in
one move are possible.
Win by capturing all the opponent’s pieces.
Note a rotational symmetry, with colrev.
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
8
Puzzle: Eternity
There are 209 playing pieces, all of different
shapes but covering the same area. They have
jagged edges with a small number of angles and
straight-line lengths.
They are assemblies of six “tridrafters” - 30o-60o90o triangles. The pieces are in reality all the same
colour and can be used either way up. Each piece
therefore has 12 possible manifestations.
The puzzle is to fit them together to fill perfectly a
particular shape of board - shown here as the lined
blue dodecahedron. The board has mirror
symmetry along 2 axes and 6-way rotational
symmetry.
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
9
Game with chance element: Backgammon
White tries to move pieces anticlockwise to end in
the bottom right, Red tries to move clockwise to
top right. (Logically, it is just a straight line,
wrapped over to be compact)
Players in turn roll two dice. Each die roll allows
one piece to be advanced the given number of
points, to land on a point that is empty, occupied
by friendly pieces, or occupied by only one enemy
piece - a ‘blot’. The blot is removed and must
begin from an imaginary off-board point before
the starting point. This can cost moves.
Win by getting all pieces, first into the final 6
points, then to (or beyond) another imaginary offboard point beyond the end.
Gambling for money is usual.
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
10
Lion’s-Share game: Go
Players take turns to place one stone on any
unoccupied intersection of a (usually) 19x19 board,
which is initially empty.
Blocks of same-colour strongly-connected stones
are captured and removed if they are surrounded so
that they have no adjacent empty intersection.
Capturing stones is part of the game, but not its
object. One wins mainly by surrounding empty
space in which opponent stones could not survive.
Rules are very simple, good play is very hard.
Note 4-rotation + mirror symmetry.
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
11
If you are not already familiar with it, spend a
few minutes on the 9-dot problem:
Draw four straight lines, joined end-to-end, to
pass through all nine dots.
(Do not ask me questions about this now! )
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
12
Points of difference between various games (& puzzles)
•Finger-twitching or not
•Kinds of symmetry
•Number of players: 1, 2, many
•Perfect Information or not
•Chance element or not
• Past moves, or current state
•Racing To Finish or Sharing Out
• Options of other players
•Zero-Sum or not
•Simultaneous move or not
•Mathematically Solved or not
•Impartial rules or not
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
13
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
14
Last-Man-Standing game: Nine Men’s Morris
Beginning with an empty board, in phase 1 players
alternately put a new peg (man) onto an empty
intersection. If they get 3 in a row - a mill - they
capture an opponent’s man.
When both players have placed all 9 men, phase 2
begins. A player may slide a man to an adjacent
connected empty intersection, capturing an enemy
man if making a new mill.
A player with exactly 3 men left may jump a man to
any empty intersection, capturing if making a new
mill. Win by reducing opponent to 2 men.
Note 4-way rotational symmetry, combined with two
forms of mirror symmetry, without requiring colrev.
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
15
Last-Man-Standing race game: Tic-Tac-Toe (Noughts&Crosses)
A very simple example of a game where there
is no capturing, merely a race to achieve an
objective.
There is often no winner: a draw occurs when
no player may make a move.
4-way rotational symmetry with mirror
symmetry.
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
16
Last-Man-Standing race game: Connect-Four
Players take turns to place one piece of their colour
on the topmost empty cell of one of seven columns.
There is no capturing. Win by being first to get four
pieces of your colour in a row, either vertically
horizontally or diagonally.
There is only one mirror symmetry, left-to-right.
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
17
Last-Man-Standing race game: Go-Moku / Five In A Row
Players take turns to put a piece of their colour onto
(almost) any empty point in a large grid: sometimes
infinite, sometimes a 19x19 Go board, …
The winner is the first to get five pieces in a row.
Note 4-rotational + mirror symmetry.
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
18
Last-Man-Standing race game: Fox and Hounds / Fox and Geese
Played on an 8x8 chessboard.
One player controls the four hounds, which can
move one square along diagonals in a forwards-only
direction. The other player controls the fox, which
moves one square along diagonals either forwards or
backwards. No two pieces can occupy the same
square.
Hounds win by trapping the fox. Fox wins by
slipping through the line of hounds.
Note there is no symmetry.
Also the players are bound by different rules of
movement. The rules are partisan not impartial.
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
19
Last-Man-Standing game: Roshambo / Rock-Paper-Scissors
Two players simultaneously pick one of three options,
•Rock wins over scisssors
•Scissors wins over paper
•Paper wins over Rock
There is arguably a 3-rotational cyclic symmetry here.
This is the first multi-player game we have seen to not
feature turn-taking.
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
20
Last-Man-Standing race game: Nim
Players take turns to remove 1, 2, or 3 items all from the
same row. The one to take the last item is the winner.
(Alternative rule: the one to take the last item is the
loser.)
There is some symmetry, since all rows are
interchangeable, even though not all positions generated
by symmetry are reachable.
The game is solved: there is an algorithm that can be
followed for winning.
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
21
Puzzles: Last-Man-Standing games versus “the rules”: Solitaire
Start with pieces occupying all pits except the
central one. You may jump a piece over another
into an empty pit, removing the piece you jumped.
You succeed (win) if you end with just one piece
remaining, in the central pit.
You lose if you cannot move.
Note 4-way rotational + mirror symmetry, and also
a symmetry between the two ends of the game: the
finish is like the start, with empty and filled pits
interchanged.
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
22
Puzzle: Logic puzzles
You are given pieces of information from
which you should be easily able to deduce
pairs of attributes that could not go together, as
well as pairs that do go together.
Ultimately, you will be left with a few
alternatives that must be enumerated in order
to find the one consistent solution.
Five men went to five separate cities on five
different days by five modes of transport.
Mr. Brown went on the train..
Mr. Green went to Galway.
The bus went on Saturday.
….
Who went where, how, and when?
There is typically a concealed symmetry,
which can be made explicit with a tabular
representation.
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
23
Puzzle: Kakuro
There is a grid like a crossword.
Each “word” across or down must be filled
with digits 1 - 9, summing to a specified total,
without duplicates.
Some “words” can be filled only by certain
combinations of digits: eg
7 in 3 cells: 1+2+4
34 in 5 cells: 4+6+7+8+9
In “easy” kakuro puzzles there are several
cells where highly-constrained words meet: so
you can get started by fixing a few cell values.
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
24
Game of Chance: Yahtzee
Any number can play.
Roll 5 dice per turn, up to three times in a turn,
keeping as many as you like from previous roll
that turn.
Add the pips on qualifying dice to make a
score in one of the non-bonus categories. You
may ultimately be forced score zero for some
categories.
At the end, add your scores and bonuses,
player with highest score wins.
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
25
Game of chance and bluff: Liar Dice
For two or more players.
The first rolls the five dice, keeping them hidden,
and passes them to the next player with a
description of their goodness. Each player may then
secretly re-roll all some or none, and pass them on
with an ever more impressive description.
A player may choose not to accept the description
given them. If the dice are at least as good as
described, they lose; otherwise the player caught
lying loses.
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
26
Game of chance: Russian Roulette
Not recommended.
There is no winner, only a loser.
It is not, in game-theoretic terms, a “zero-sum game”.
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
27
Lion’s-Share game: Mancala / Awari / Kalah
Each player controls the pits on one side of the
board. On your turn, pick up the stones from
one of your pits and add one of them to each
succeeding pit in an anticlockwise direction. If
the last pit you reach now has 2 or 3 stones,
remove them, and then do likewise for the
preceding pit and so on.
The winner is the one who captures the
majority of the stones.
Note rotational 2-symmetry; all pieces alike.
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
28
Lion’s-Share game: Othello / Reversi
Players begin with two pieces each as shown. They take
turns, adding one new piece of their colour. All enemy
pieces in a vertical/diagonal/horizontal line between the
new piece and another friendly piece are replaced with
friendly pieces.
In practice, 2-sided pieces are used.
A player who cannot move misses a turn.
Win by having more pieces than the opponent.
4-way rotational + mirror symmetry.
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
29
Lion’s-share games of chance: Poker, Bridge, Whist, Piquet, …
The use of playing cards, shuffled and dealt in secret, introduces an element of chance.
Some are strictly many-player games (poker, bridge), some are 2-player (Piquet, Nomination
Whist).
I’d call Poker a lion’s-share game because although there is an outright winner of a single deal,
there are usually many deals in a session. The winner is the one who wins most money overall.
In Bridge, Whist, etc, there are several tricks to be shared out among the players or teams; and
winning is determined in terms of the share won - perhaps set against a “contract”.
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
30
Lion’s-share game: Diplomacy
2 to 7 players control Army and Navy pieces
for seven countries. Every other turn, players
may lose pieces or acquire pieces depending
on their being the last to occupy certain
“provinces”.
Attacks may be made on pieces occupying
provinces, with both offence and defence
fortified by neighbouring pieces. Moves are
written secretly and revealed simultaneously.
Conspiracy and treachery are both encouraged.
The winner is the first to control more than
half of the salient provinces.
No symmetry; alliances are important.
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
31
Games in the real world
Many real-world situations and problems can be viewed
as games of a sort:
•Players have a choice of actions,
•Players have conflicting goals,
•Players may move sequentially or simultaneously,
•Alliances may prosper,
•Treachery may occur,
•Understanding of the goals of others may be useful in
predicting their actions and planning actions of one’s
own.
•Stock Market
•War
•Passing legislation
•Hustling
•Cartels
•Fight for market share
•Biological evolution
•Industrial relations
Parlour games offer environments in which various kinds
of simplification can be made in order to focus attention
on particular AI issues: perception, representation,
reasoning, learning, opponent modelling, and risk
assessment.
http://csiweb.ucd.ie/Staff/acater/comp4031.html
•Democratic elections
•Takeover negotiations
Artificial Intelligence for Games and Puzzles
32
Points of difference between various games (& puzzles)
•Finger-twitching or not
•Kinds of symmetry
•Number of players: 1, 2, many
•Perfect Information or not
•Chance element or not
• Past moves, or current state
•Racing To Finish or Sharing Out
• Options of other players
•Zero-Sum or not
•Simultaneous move or not
•Mathematically Solved or not
•Impartial rules or not
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
33
The End
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
34