Minimax and alpha beta reduction l.jpg
1 / 22

Minimax and Alpha-Beta Reduction.


67 views
Uploaded on:
Category: Animals / Pets
Description
Minimax and Alpha-Beta Reduction. Borrows from Spring 2006 CS 440 Lecture Slides. Motivation. Want to create programs to play games Want to play optimally Want to be able to do this in a reasonable amount of time. Types of Games. Nondeterministic (Chance). Deterministic. Chess
Transcripts
Slide 1

Minimax and Alpha-Beta Reduction Borrows from Spring 2006 CS 440 Lecture Slides

Slide 2

Motivation Want to make projects to play diversions Want to play ideally Want to have the capacity to do this in a sensible measure of time

Slide 3

Types of Games Nondeterministic (Chance) Deterministic Chess Checkers Go Othello Backgammon Monopoly Fully Observable Battleship Card Games Partially Observable Minimax is for deterministic, completely perceptible recreations

Slide 4

Basic Idea Search issue Searching a tree of the conceivable moves keeping in mind the end goal to discover the move that creates the best result Depth First Search calculation Assume the adversary is likewise playing ideally Try to ensure a win in any case!

Slide 5

Required Pieces for Minimax An underlying state The positions of the considerable number of pieces Whose turn it is Operators Legal moves the player can make Terminal Test Determines if a state is a last state Utility Function

Slide 6

Utility Function Gives the utility of an amusement state utility(State) Examples - 1, 0, and +1, for Player 1 loses, draw, Player 1 wins, individually Difference between the point aggregates for the two players Weighted total of elements (e.g. Chess) utility(S) = w 1 f 1 (S) + w 2 f 2 (S) + ... + w n f n (S) f 1 (S) = (Number of white rulers) – (Number of dark rulers), w 1 = 9 f 2 (S) = (Number of white rooks) – (Number of dark rooks), w 2 = 5 ...

Slide 7

Two Agents MAX Wants to amplify the consequence of the utility capacity Winning system if, on MIN's turn, a win is reachable for MAX for all moves that MIN can make MIN Wants to minimize the aftereffect of the assessment capacity Winning procedure if, on MAX's turn, a win is possible for MIN for all moves that MAX can make

Slide 8

Basic Algorithm

Slide 9

Example Coins diversion There is a pile of N coins In turn, players take 1, 2, or 3 coins from the stack The player who takes the last coin loses

Slide 10

Coins Game: Formal Definition Initial State: The quantity of coins in the stack Operators: 1. Expel one coin 2. Expel two coins 3. Evacuate 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

Slide 11

MAX MIN N = 4 K = 1 3 2 N = 3 K = N = 2 K = N = 1 K = 1 3 2 1 N = 0 K = N = 1 K = N = 2 K = N = 0 K = N = 1 K = N = 0 K = F(S)=1 1 2 F(S)=1 1 F(S)=1 N = 3 K = N = 1 K = N = 0 K = N = 0 K = F(S)=0 1 F(S)=0 N = 0 K = F(S)=1

Slide 12

Solution MAX MIN N = 4 K = 1 3 2 N = 3 K = 0 N = 2 K = 0 N = 1 K = 1 3 2 1 N = 0 K = 1 N = 1 K = 0 N = 2 K = 1 N = 0 K = 1 N = 1 K = 0 N = 0 K = 1 F(S)=1 1 2 F(S)=1 1 F(S)=1 N = 3 K = 0 N = 1 K = 1 N = 0 K = 0 N = 0 K = 0 F(S)=0 1 F(S)=0 N = 0 K = 1 F(S)=1

Slide 13

Analysis Max Depth: 5 Branch element: 3 Number of hubs: 15 Even with this unimportant illustration, you can see that these trees can get huge Generally, there are O(b d ) hubs to look for Branch element b: most extreme number of moves from every hub Depth d: greatest profundity of the tree Exponential time to run the calculation! In what capacity would we be able to make it quicker?

Slide 14

Alpha-Beta Pruning Main thought: Avoid handling subtrees that have no impact on the outcome Two new parameters α: The best esteem for MAX seen so far β: The best esteem for MIN seen so far α is utilized as a part of MIN hubs, and is alloted in MAX hubs β is utilized as a part of MAX hubs, and is allocated in MIN hubs

Slide 15

Alpha-Beta Pruning MAX (Not at level 0) If a subtree is found with a worth k more noteworthy than the estimation of β, then we don't have to keep looking subtrees MAX can do in any event in the same class as k in this hub, so MIN could never go here! MIN If a subtree is found with a worth k not exactly the estimation of α, then we don't have to keep looking subtrees MIN can do at any rate in the same class as k in this hub, so MAX could never go here!

Slide 16

Algorithm

Slide 17

MAX MIN N = 4 K = α = β = 1 3 α = β = 2 N = 3 K = α = β = N = 2 K = α = β = N = 1 K = 1 α = β = α = β = 3 2 1 N = 0 K = N = 1 K = α = β = N = 2 K = α = β = N = 0 K = N = 1 K = α = β = N = 0 K = F(S)=1 1 2 F(S)=1 1 F(S)=1 α = β = N = 3 K = N = 1 K = N = 0 K = N = 0 K = α = β = α = β = α = β = α = β = F(S)=0 1 F(S)=0 N = 0 K = α = β = F(S)=1

Slide 18

MAX MIN N = 4 K = 0 1 α = 0 β = 1 3 α = 0 β = 1 2 N = 3 K = 1 0 α = β = 1 0 N = 2 K = 1 0 α = 0 β = 0 N = 1 K = 1 α = 0 β = α = 1 β = 3 2 1 N = 0 K = 1 N = 1 K = 0 α = 0 β = 1 0 N = 2 K = 1 α = β = 0 N = 0 K = 1 N = 1 K = α = 0 β = 0 N = 0 K = 1 F(S)=1 1 2 F(S)=1 1 F(S)=1 α = 0 β = 1 N = 3 K = 0 N = 1 K = 1 N = 0 K = N = 0 K = 0 α = 0 β = α = 1 β = 0 α = β = α = 0 β = 0 F(S)=0 1 F(S)=0 N = 0 K = 1 α = 1 β = 0 F(S)=1

Slide 19

Nondeterministic Games Minimax can likewise be utilized for nondeterministic amusements (those that have a component of chance) There is an extra hub included (Random hub) Random hub is amongst MIN and MAX (and the other way around) Make subtrees over the greater part of the possibilities,and normal the outcomes

Slide 20

Example Weighted coin .6 Heads (1) .4 Tails (0) N = 2 K = 8.6 Random Node K = .4*5 + .6*11 = 8.6 K = .4*2 + .6*7 = 5 0 1 0 1 K = 5 K = 11 K = 2 K = 7

Slide 21

Our Project We will concentrate on deterministic, two-player, completely perceptible recreations We will attempt to take in the evaluator capacity, so as to spare time when playing the diversion Training on information from Minimax runs (Neural Network) Having the system play against itself (Genetic Algorithms)

Slide 22

Conclusion Minimax finds ideal play for deterministic, completely recognizable, two-player amusements Alpha-Beta decrease makes it quicker