Games, Theory and Application Jaap van den Herik and Jeroen Donkers

Games, Theory and Application

• Jaap van den Herik and Jeroen Donkers

• Institute for Knowledge and Agent Technology, IKAT

• Department of Computer Science

• Universiteit Maastricht

• The Netherlands

• SOFSEM 2004 Prague, Hotel VZ Merin

• Sunday, January 25 8.30-10.00h

Contents

• Games in Artificial-Intelligence Research

• Game-tree search principles

• Using opponent models

• Opponent-Model search

• Gains and risks

• Implementing OM search: complexities

• Past future of computer chess

• Games, such as Chess, Checkers, and Go

• are an attractive pastime and

• scientifically interesting

Chess

• Much research has been performed in Computer Chess

• Deep Blue (IBM) defeated the world champion Kasparov in 1997

• A Micro Computer better than the world champion?

World Champion Programs

• KAISSA 1974 Stockholm
• CHESS 1977 Toronto
• BELLE 1980 Linz
• CRAY BLITZ 1983 New York
• CRAY BLITZ 1986 Keulen
• DEEP THOUGHT 1989 Edmonton
• REBEL 1992 Madrid
• FRITZ 1995 Hong Kong
• SHREDDER 1999 Paderborn
• JUNIOR 2002 Maastricht
• SHREDDER 2003 Graz
• ? 2004 Ramat-Gan

International Draughts

• Buggy best draughts program

• Human better than computer, but the margin is small

• Challenge: More knowledge in program

Go

• Computer Go programs are weak

• Problem: recognition of patterns

• Top Go programs: Go4++, Many Faces of Go, GnuGo, and Handtalk

Awari

Scrabble

• Maven beats every human opponent

• Author Brian Sheppard

• Ph.D. (UM): “Towards Perfect Play of Scrabble” (02)

• Maven can play scrabble in any language

Overview

Computer Olympiad

• Initiative of David Levy (1989)
• Since 1989 there have been 8 olympiads; 4x Londen, 3x Maastricht, 1x Graz
• Goal:
• Finding the best computer program for each game
• Connecting programmers / researchers of different games
• Computers play each other in competition
• Demonstrations:
• Man versus Machine
• Man + Machine versus Man + Machine

Computer versus Computer

Computer Olympiad

• Last time in Graz 2004
• Also World Championship Computer Chess and World Championship Backgammon
• 80 particpants in several categories
• Competitions in olympiad’s history:
• Abalone, Awari, Amazons, Backgammon, Bao, Bridge, Checkers, Chess, Chinese Chess, Dots and Boxes, Draughts, Gipf, Go-Moku, 19x19 Go, 9x9 Go, Hex, Lines of Action, Poker, Renju, Roshambo, Scrabble, and Shogi

UM Programs on the Computer Olympiads

Computer Game-playing

• Can computers beat humans in board games like Chess, Checkers, Go, Bao?

• This is one of the first tasks of Artificial Intelligence (Shannon 1950)

• Successes obtained in Chess (Deep Blue), Checkers, Othello, Draughts, Backgammon, Scrabble...

Computer Game-Playing

• Sizes of game trees:

• Nim-5: 28 nodes
• Tic-Tac-Toe:  105 nodes
• Checkers:  1031 nodes
• Chess:  10123 nodes
• Go:  10360 nodes

• In practice it is intractable to find a solution with minimax: so use heuristic search

Three Techniques

• Minimax Search

• α-β Search

• Opponent Modelling

Game-playing

• Domain: two-player zero-sum game with perfect information (Zermelo, 1913)

• Task: find best response to opponent’s moves, provided that the opponent does the same

• Solution: Minimax procedure (von Neumann, 1928)

Minimax Search

Minimax Search

Minimax Search

Pruning

• You do not need the total solution to play (well): only the move at the root is needed

• Methods exist to find this move without a need for a total solution: pruning

• Alpha-beta search (Knuth & Moore ‘75)
• Proof-number search (Allis et al. ‘94), etc.

• Playing is solving a sequence of game trees

Heuristic Search

Heuristic Search

• The approach works very well in Chess, but...

• Is solving a sequence of reduced games the best way to win a game?

• Heuristic values are used instead of pay-offs
• Additional information in the tree is unused
• The opponent is not taken into account

• We aim at the last item: opponents

Minimax

α-β algorithm

The strength of α-β

The importance of α-β algorithm

• THE NUMBER OF DIFFERENT, REACHABLE

• POSITIONS IN CHESS IS

• (CHINCHALKAR): 1046

A Clever Algorithm (α-β)

• SAVES THE SQAURE ROOT OF THE NUMBER OF POSSIBILITIES, N, THIS IS MORE THAN

• 99,999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999%

A Calculation

• NUMBER OF POSSIBILITIES: 1046

• SAVINGS BY α-Β ALGORITHM: 1023

• 1000 PARALLEL PROCESSORS: 103

• POSITIONS PER SECOND: 109

• LEADS TO: 1023-12 = 1011 SECONDS

• A CENTURY IS 109 SECONDS

• SOLVING CHESS: 102 CENTURIES

• SO 100 CENTURIES OR 10,000 YEAR

Using opponent’s strategy (NIM-5)

Using opponent’s strategy

• Well known Tic-Tac-Toe strategy:

• R1: make 3-in-a-row if possible
• R2: prevent opponent’s 3-in-a-row
• if possible
• H1: occupy central square if possible
• H2: occupy corner square if possible

Opponent-Model search

• Iida, vd Herik, Uiterwijk, Herschberg (1993)
• Carmel and Markovitch (1993)

• Opponent’s evaluation function is known (unilateral: the opponent uses minimax)

• This is the opponent model

• It is used to predict opponent’s moves

• Best response is determined, using the own evaluation function

OM Search

• Procedure:

• At opponent’s nodes: use minimax (alpha-beta) to predict the opponent’s move. Return the own value of the chosen move
• At own nodes: Return (the move with) the highest value
• At leaves: Return the own evaluation

• Implementation: one-pass or probing

OM Search Equations

OM Search Example

OM Search Algorithm (probing)

Risks and Gains in OM search

• Gain: difference between the predicted move and the minimax move

• Risk: difference between the move we expect and the move the opponent really selects

• Prediction of the opponent is important, and depends on the quality of opponent model.

Additional risk

• Even if the prediction is correct, there are traps for OM search

• Let P be the set of positions that the opponent selects, v0 be our evaluation function and vop the opponent’s function.

Four types of error

• V0 overestimates a position in P (bad)

• V0 underestimates a position in P

• Vop underestimates a position that enters P (good for us)

• Vop overestimates a position in P

Pruning in OM Search

• Pruning at MAX nodes is not possible in OM search, only pruning at MIN nodes can take place (Iida et al, 1993).

• Analogous to α-β search, the pruning version is called β-pruning OM search

Pruning Example

Two Implementations

• One-pass:

• visit every node at most once
• back-up both your own and the opponent’s value

• Probing:

• At MIN nodes use α-β search to predict the opponent’s move
• back-up only one value

One-Pass β-pruning OM search

Probing β-pruning OM search

Best-case time complexity

Best-case time complexity

Best-case time complexity

• The time complexity for the one-pass version is equal to that of the theoretical best

• The time complexity for the probing version is different:

• first detect the number of leaf evaluations needed:
• Then find the number of probes needed:

Best-case time complexity

Best-case time complexity

Time complexities compared

Average-case time complexity

Probabilistic Opponent-model Search

• Donkers, vd Herik, Uiterwijk (2000)

• More elaborate opponent model:

• Opponent uses a mixed strategy: n different evaluation functions (opponent types) plus a probability distribution
• It is assumed to approximate the true opponent’s strategy
• Own evaluation function is one of the opponent types

PrOM Search

• Procedure:

• At opponent’s nodes: use minimax (alpha-beta) to predict the opponent’s move for all opponent types separately. Return the expected own value of the chosen moves
• At own nodes: Return (the move with) the highest value
• At leafs: Return the own evaluation

• Implementation: one-pass or probing

PrOM Search Equations

PrOM Search Example

PrOM Search Algorithm

How did chess players envision the future of non-human chess players?

• - Euwe

• - Donner

• - De Groot

• - Timman

• - Sosonko

• - Böhm

• Question: Do you think that a computer will be able to play at grandmaster level?

Euwe (June 10, 1980)

• “I don’t believe so.

• I am almost convinced of that, too”

Timman (June 22, 1980):

• “If you would express it in ELO-points, than I believe that a computer will not be able to obtain more than ...... let’s say ...... 2500 ELO-points.”

Sosonko (August 26, 1980):

• “I haven’t thought about that so much, but I believe that it will certainly not be harmful for the human chess community. It will become more interesting. I am convinced that computer chess will play a increasingly important role. It will be very interesting, I think”

Donner (April 13, 1981):

• “But the computer cannot play chess at all and will never be able to play the game, at least not the first two thousand years, (...)

• What it does now has nothing to do with chess.”

De Groot (June 19, 1981):

• “No, certainly not. As a matter of fact, I believe it will not even possible that it can reach a stable master level.

• I believe it is possible that the computer can reach a master level, but not that it is a stable master.”

Contributions from Science

• COMPUTERS PLAY STRONGER THAN HUMANS.

• COMPUTERS CAN NOT SOLVE CHESS.

• COMPUTERS ENABLE AN ALTERNATIVE FORM OF GAME EXPERIENCE.

Conclusions

• 1. Chess is a frontrunner among the games

• 2. Kasparov’s defeat has become a victory for brute force in combination with knowledge and opponent modelling

The Inevitable Final Conclusion

• TECHNOLOGY, AND IN PARTICULAR

• OPPONENT MODELLING,

• MAKES THE BEST BETTER,

• BUT DOES NOT LEAVE THE

• WEAKER PLAYERS WITH

• EMPTY HANDS

• SINCE THEIR LEVEL

• WILL INCREASE TOO.