## two-player games

~~~ ~~~ - in a puzzle, 1 player makes all moves -- to solve puzzle, search state space for best possible outcome - 2-player games? chess, Go, hex, ... how to solve? - ideas from chess -- [https://en.wikipedia.org/wiki/The_Turk 1770 the Turk automaton] -- 1913 [http://webdocs.cs.ualberta.ca/~hayward/396/asn/zermelo.pdf zermelo] /on the application of counting theory to the theory of chess/ -- 1947? [https://en.wikipedia.org/wiki/Alan_Turing Alan Turing], [https://en.wikipedia.org/wiki/Claude_Shannon Claude Shannon] discussed chess algs, e.g. minimax -- 1997 [https://en.wikipedia.org/wiki/Deep_Blue_(chess_computer) Deep Blue] defeats Kasparov 3.5--2.5 -- UAlberta connection [https://www.ualberta.ca/science/science-news/2014/august/murray-campbell-and-kasparovs-blue-day Murray Campbell] BSc (1979) MSc (1981) ~~~ ~~~ {}{raw}

~~~ ~~~ - simplest multi-player games? e.g.~ Go, tic-tac-toe, checkers, chess -- 2 players -- alternate turn -- zero-sum (only 1 winner) - *adversarial search*: searching a 2-player game tree - consider a player about to move - in order to pick best move, need to know how opponent will respond - worst case for player, but simplest to analyse (requires no opponent modelling) -- assume opponent *perfect*, always makes best possible move - what does it mean to solve a game? -- *state* position and player-to-move -- *reachable state* any state reachable by sequence of legal moves -- *strategy* for a player, a function that, for any reachable state, returns a legal move -- in 2-player game, to *solve a state* is to find a strategy with best worst-case performance, ie. that guarantees the best possible score, over all possible opponent strategies (so, assuming opponent always makes a best possible move) - initial move for any such strategy can be found by *minimax search*, score is player-to-move's *minimax score* #- [http://csci431.artifice.cc/notes/adversarial-search.html adversarial search by Joshua Eckroth] #- [http://cse3521.artifice.cc/adversarial-search.html adversarial search by Joshua Eckroth] #- [https://player.vimeo.com/video/49134866 video] - play that follows a minimax strategy called *perfect play* - if you missed this lecture, [https://www.youtube.com/watch?reload=9&v=STjW3eH0Cik watch this] ~ [http://inst.eecs.berkeley.edu/~cs61b/fa14/ta-materials/apps/ab_tree_practice/ practice this] ~~~ ~~~ {}{raw}

## minimax

~~~ ~~~ - to find minimax value, explore game-state tree in any order that finds values of children before value of node - minimax algorithm: search space to find root state minimax value ~~~ ~~~ {minimax algm, max/min format}{} root node is a max node each child of a max node is a min node each child of a min node is a max node def eval(s): for player MAX, return score of s def minimax(s): if terminal(s): return eval(s) if s.player() == MAX: return max(for all children c of s, minimax(c)) if s.player() == MIN: return min(for all children c of s, minimax(c)) ~~~~ ~~~ {}{raw}

## minimax example, min/max format

~~~ ~~~ {}{} node: state edge (root, level 1): p1 move edge (level 1, level 2): p2 move leaf label: p1 score for each node, p1 minimax value ? best play? * / | \ / | \ * * * / | \ / \ / | \ * * * * * * * * 2 3 -1 1 6 -4 2 9 1 / | \ / | \ -1 1 -4 / | \ / \ / | \ * * * * * * * * 2 3 -1 1 6 -4 2 9 p1 best play from root: middle p2 best play at level 1: after p1 left: right (p1 scores -1) after p1 middle: left (p1 scores 1) after p1 right: left (p1 scores -4) ~~~ ~~~ {}{raw}

## pruning game trees

~~~ ~~~ when solving a state, usually not necessary to examine the whole tree - once one winning move is found, remaining moves can be ignored - this motivates alpha-beta search - [http://webdocs.cs.ualberta.ca/~hayward/396/asn/mmx.pdf pruning example] ~~~ ~~~ {minimax pruning example, min/max format}{} recall min/max format: p1 max, p2 min, show p1 values a / \ b c / \ /|\ d e f g h 7 5 3 ? ? assume dfs with children explored left-to-right * / \ 5 <=3 / \ /|\ 7 5 3 ? ? after examining node we know ... d val(b) <= 7 e val(b) = min(7,5) = 5 c val(c) <= 3 now, no need to learn more about val(c) ... val(c) <=3 < val(b) ... p1 prefers b to c ... so prune remaining children of c from our search ~~~ ~~~ {}{raw}

## alpha-beta search

~~~ ~~~ - {{αβ}}-search = minimax search with {{αβ}} pruning - {{α}}: value, best p1 option so far, on path current-to-root - {{β}}: value, best p2 option so far, on path current-to-root - minimax, so can be used as a solver -- leaf scores must be true scores -- must be able to reach all leaf nodes in reasonable time - can *also* be used as heuristic player -- find fast heuristic, use on all leaves at a fixed depth -- eg. simple chess player ~~~ ~~~ {examples} - [https://www.youtube.com/watch?v=xBXHtz4Gbdo video example] - to see our algorithm run on this example, go to directory +simple/alphabeta+ and run +alphabeta.py+ on input +t2.in+ - [http://inst.eecs.berkeley.edu/~cs61b/fa14/ta-materials/apps/ab_tree_practice/ practice here] ~~~