Download - Juegos minimax AlfaBeta
Juegos
Nelson Becerra Correa
Fundación FABBECOR-ONG
Bibliografía• Conferencia : Miguel Illescas, Gran Maestro Internacional.
Kasparov, Deep Blue y la mente del ajedrecista.
• http://www.ocf.berkeley.edu/~yosenl/extras/alphabeta/alphabeta
• Jorge Egger M. Desarrollo de la maestría ajedrecística computacional. Utilizando recursos restringidos. Universidad de chile. Facultad de ciencias físicas y matemáticas. Departamento de ciencias de la computación, Santiago de chile, Julio 2003.
• Técnicas de inteligencia artificial en Juego. Nelson Becerra Correa, Fondo de publicaciones Universidad Distrital (FJC), Año 2003.
• w.acm.uiuc.edu/sigart/docs/MinimaxPresentation.ppt
TEORIA DE JUEGOS Fué creada para solucionar problemas
económicos. Los pioneros de esta teoría son John Von Newman y Oskar Morgestern.
En la actualidad se aplica a la Psicología, la administarción , las ciencias políticas etc.
Clasificación de los juegos
NUMERO PARTICIPANTES
•Unipersonales•Bipersonales•N-personas N>2
NUMEROESTRATEGIAS
•Finito (estrategias finitas)•Infinitas
DE ACUERDO A LA
INFORMACION
•Información perfecta (Secuenciales)
•Información Imperfecta (Yan ken Po) (Dilema pri)
DE ACUERDO A LA SUMA
•Juegos de suma cero (ajedrez, oso, go,mankala)
•Juegos de suma distinta de cero (F)
Como juegan las maquinas
Como juegan las maquinas
Como juegan las maquinas
Como juegan las maquinas
Como juegan las maquinas
DEEP-BLUE potencia de calculo
Función de evaluación
Función de evaluación
Posición que un programa sin Tablas de Transposición no puede solucionar.Las Blancas ganan mediante 1.Rb1!! Rb7 2.Rc1!!
1. 30 movimientos sería necesaria, y eso tomaría miles de horas de tiempo de CPU.
2. Con tablas Hash 6 movimientos, puesto que existen 130 diferentes tipos de posiciones obtenibles desde la inicial.
Basic Idea
• Search problem– Searching a tree of the possible moves in order
to find the move that produces the best result– Depth First Search algorithm
• Assume the opponent is also playing optimally– Try to guarantee a win anyway!
Árbol de variantes
1. En los inicios de 1970 la búsqueda en árboles de variantes alcanzaba la cantidad aproximada de 200 posiciones por segundo.
2. En año 2003, DEEP BLUE busca en 2.000.000 de posiciones por segundo.
3. Los mejores programas logran examinar todas las secuencias de movimientos con una profundidad de 8 a 10 movidas en el árbol (4 a 5 jugadas por bando).
Required Pieces for Minimax
• An initial state– The positions of all the pieces– Whose turn it is
• Operators– Legal moves the player can make
• Terminal Test– Determines if a state is a final state
• Utility Function
Utility Function• Gives the utility of a game state
– utility(State)
• Examples– -1, 0, and +1, for Player 1 loses, draw, Player 1 wins,
respectively– Difference between the point totals for the two players– Weighted sum of factors (e.g. Chess)
• utility(S) = w1f
1(S) + w
2f
2(S) + ... + w
nf
n(S)
– f1(S) = (Number of white queens) – (Number of black queens), w
1 = 9
– f2(S) = (Number of white rooks) – (Number of black rooks), w
2 =
5– ...
Two Agents• MAX
– Wants to maximize the result of the utility function
• MIN– Wants to minimize the result of the evaluation
function
… MINIMAXEjemplo de definición de función evaluadora:• Si p no es posición ganadora para ningún ganado, entonces:
– e(p)= (el nº de filas, columnas y diagonales completas que todavía estan libres para MAX) – (nº de filas, columnas, diagonales completas que todavía estan libres para MIN)
• Si p es una posición ganadora para MAX, entonces– e(p)= ∞ (donde ∞ indica un número positivo muy grande)
• Si p es una posición ganadora para MIN, entonces– e(p)= -∞
… MINIMAXOX
Se tiene que e(p)=6 – 4 = 2
http://www.ocf.berkeley.edu/~yosenl/extras/alphabeta/alphabeta.html
Basic Algorithm
ALGORITMOS DE JUEGOS
• Algoritmos de primera generación
– se caracterizan por confiar en la capacidad bruta de las maquinas
• Algoritmos de segunda generación:
– Surge la inquietud de que mientras la maquina examina miles de posiciones su oponente humano solo examina algunas de ellas
ALGORITMOS DE PRIMERA GENERACION
• MINIMAX
• NEGAMAX
• ALFA/BETA
• FALFA/BETA
• LALFA/BETA
• PALFA/BETA
• SCOUT
MINIMAX NEGAMAX
ALFA/BETA FALFA/BETA
LALFA/BETA PALFA/BETA
SCOUT
Max
Min
Max
Min
Starting node and labelsMiniMax Search
Max
Min
Max
Min
Continue expand the search space
Max
Min
Max
Min
Continue expand the search space
Max
Min
Max
Min2 3 5 09 7 4
Expand the search space down3-ply
Max
Min
Max
Min2 3 5 09 7 4
Propagate the leaf values backwardPick Max values at Max Level
9 03 77
Max
Min
Max
Min2 3 5 09 7 4
Continue propagate the values backwardPick Min values at Min Level
9 03 77
3 0
Max
Min
Max
Min2 3 5 09 7 4
Continue propagate the values backwardPick Max values at Max Level
9 03 77
3 0
3
Max
Min
Max
Min2 3 5 09 7 4
The move picked by Max
9 03 77
3 0
3
Example MINIMAX
• Coins game– There is a stack of N coins– In turn, players take 1, 2, or 3 coins from the
stack– The player who takes the last coin loses
Coins Game: Formal Definition
• Initial State:
The number of coins in the stack• Operators:
1. Remove one coin
2. Remove two coins
3. Remove three coins
• Terminal Test:
There are no coins left on the stack• Utility Function: F(S)
– F(S) = 1 if MAX wins, 0 if MIN wins
N = 4K =
N = 3K =
N = 2K =
N = 1K =
N = 0K =
N = 1K =
N = 2K =
N = 0K =
N = 0K =
N = 1K =
N = 0K =
N = 1K =
N = 0K =
N = 0K =
12
3
3 21 2 1 1
1211
N = 0K =
1 F(S)=0
F(S)=0
F(S)=0
F(S)=1
F(S)=1
F(S)=1
F(S)=1
MAXMIN
N = 4K = 1
N = 3K = 0
N = 2K = 0
N = 1K = 1
N = 0K = 1
N = 1K = 0
N = 2K = 1
N = 0K = 1
N = 0K = 1
N = 1K = 0
N = 0K = 0
N = 1K = 1
N = 0K = 0
N = 0K = 0
12
3
3 21
2 1 1
1211
N = 0K = 1
1 F(S)=0F(S)=0 F(S)=0
F(S)=1
F(S)=1
FFS(51791527S)=1
F(S)=1
MAXMIN
Solution
F(S)=1
Analysis• Max Depth: 5• Branch factor: 3• Number of nodes: 15• Even with this trivial example, you can see that
these trees can get very big– Generally, there are O(bd) nodes to search for
• Branch factor b: maximum number of moves from each node• Depth d: maximum depth of the tree
– Exponential time to run the algorithm!– How can we make it faster?
Alpha-Beta Pruning
• Main idea: Avoid processing subtrees that have no effect on the result
• Two new parameters– α: The best value for MAX seen so far– β: The best value for MIN seen so far
• α is used in MIN nodes, and is assigned in MAX nodes
• β is used in MAX nodes, and is assigned in MIN nodes
Alpha-Beta Pruning
• MAX (Not at level 0)– If a subtree is found with a value k greater than
the value of β, then we do not need to continue searching subtrees• MAX can do at least as good as k in this node, so MIN
would never choose to go here!
• MIN– If a subtree is found with a value k less than the
value of α, then we do not need to continue searching subtrees• MIN can do at least as good as k in this node, so MAX
would never choose to go here!
Max
Min
Max
Min
Starting node and labelsAlpha-Beta Prune
Max
Min
Max
Min
Perform a DFS
Max
Min
Max
Min
Continue the DFS
Max
Min
Max
Min2 3
Until reach the depth we want, i.e., 3-ply in this case
Max
Min
Max
Min2 3
3
Propagate leaf values backward
Max
Min
Max
Min2 3
3
3
Max
Min
Max
Min2 3
3
3
3
Max
Min
Max
Min2 3
3
3
3 Alpha Node
Beta Node
Max
Min
Max
Min2 3
3
3
3 Alpha
Beta
5
New DFS path Ended with 5
Max
Min
Max
Min2 3
3
3
3 Alpha
Beta
5
5
Propagate backward
Max
Min
Max
Min2 3
3
3
3 Alpha
Beta
5
5
Because 3 < 5
The branch is pruned.
Beta-Prune
Max
Min
Max
Min2 3
3
3
3 Alpha
Beta
5
5
New 3-ply DFSEnded with 0
0
Max
Min
Max
Min2 3
3
3
3 Alpha
Beta
5
5
0
0
Propagate backward
Max
Min
Max
Min2 3
3
3
3 Alpha
Beta
5
5
0
0
Propagate backward
0
Max
Min
Max
Min2 3
3
3
3 Alpha
Beta
5
5
0
0
The branch is cut offBecause 3 > 0
Alpha Prune
0
Algorithm
N = 4K =
N = 3K =
N = 2K =
N = 1K =
N = 0K =
N = 1K =
N = 2K =
N = 0K =
N = 0K =
N = 1K =
N = 3K =
N = 1K =
N = 0K =
N = 0K =
12
3
3 21
2 1 1
1211
N = 0K =
1 F(S)=0F(S)=0 F(S)=0
F(S)=1
F(S)=1
F(S)=1 F(S)=1
MAXMIN
α =β =
α =β =
α =β =
α =β =
α =β =
α =β =
α =β =
α =β =
α =β =
α =β =
α =β =
α =β =
α =β =
α =β =
α =β =
N = 4K = 0 1
N = 3K = 1 0
N = 2K = 1 0
N = 1K = 1
N = 0K = 1
N = 1K = 0
N = 2K = 1
N = 0K = 1
N = 0K = 1
N = 1K =
N = 3K = 0
N = 1K = 1
N = 0K =
N = 0K = 0
12
3
3 21
2 1 1
1211
N = 0K = 1
1 F(S)=0F(S)=0 F(S)=0
F(S)=1
F(S)=1
F(S)=1 F(S)=1
MAXMIN
α =β = 1 0
α = 0β =
α = 0β = 1 0
α =β = 0
α = 1β =
α = 0β = 0
α = 0β = 0
α = 0β = 1
α = 0β =
α = 0β = 0
α = 0β =
α = 1β = 0
α =β =
α = 1β = 0
α = 0β = 1
Conclusion
• Minimax finds optimal play for deterministic, fully observable, two-player games
• Alpha-Beta reduction makes it faster