Scribd
Upload
100 views

Alpha Beta Example 2 PDF

Uploaded by

FaheemMasood
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
100 views

Alpha Beta Example 2 PDF

Uploaded by

FaheemMasood
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 28

Alpha-Beta Pruning – Example

Minimax on a 6-ply game


Horizon depth: h = 6

Heuristic
Evaluation

0 5 -3 3 3 -3 0 2 -2 3 5 2 5 -5 0 1 5 1 -3 0 -5 5 -3 3 2
Alpha-Beta Pruning – Example

MAX

MIN

MAX

MIN

MAX

MIN

0 5 -3 3 3 -3 0 2 -2 3 5 2 5 -5 0 1 5 1 -3 0 -5 5 -3 3 2
Alpha-Beta Pruning – Example

MAX

MIN

MAX

MIN

MAX

MIN 0

0 5 -3 3 3 -3 0 2 -2 3 5 2 5 -5 0 1 5 1 -3 0 -5 5 -3 3 2
Alpha-Beta Pruning – Example

MAX

MIN

MAX

MIN

MAX 0

MIN 0

0 5 -3 3 3 -3 0 2 -2 3 5 2 5 -5 0 1 5 1 -3 0 -5 5 -3 3 2
Alpha-Beta Pruning – Example

MAX

MIN

MAX

MIN

MAX 0

MIN 0 -3

0 5 -3 3 3 -3 0 2 -2 3 5 2 5 -5 0 1 5 1 -3 0 -5 5 -3 3 2
Alpha-Beta Pruning – Example

MAX

MIN

MAX

MIN

MAX 0

MIN 0 -3

0 5 -3 3 3 -3 0 2 -2 3 5 2 5 -5 0 1 5 1 -3 0 -5 5 -3 3 2
Alpha-Beta Pruning – Example
= pruned
MAX

MIN

MAX

MIN 0

MAX 0

MIN 0 -3

0 5 -3 3 3 -3 0 2 -2 3 5 2 5 -5 0 1 5 1 -3 0 -5 5 -3 3 2
Alpha-Beta Pruning – Example
= pruned
MAX

MIN

MAX

MIN 0

MAX 0 3

MIN 0 -3 3

0 5 -3 3 3 -3 0 2 -2 3 5 2 5 -5 0 1 5 1 -3 0 -5 5 -3 3 2
Alpha-Beta Pruning – Example
= pruned
MAX

MIN

MAX

MIN 0

MAX 0 3

MIN 0 -3 3

0 5 -3 3 3 -3 0 2 -2 3 5 2 5 -5 0 1 5 1 -3 0 -5 5 -3 3 2
Alpha-Beta Pruning – Example
= pruned
MAX

MIN 0

MAX 0

MIN 0

MAX 0 3

MIN 0 -3 3

0 5 -3 3 3 -3 0 2 -2 3 5 2 5 -5 0 1 5 1 -3 0 -5 5 -3 3 2
Alpha-Beta Pruning – Example
= pruned
MAX

MIN 0

MAX 0

MIN 0

MAX 0 3

MIN 0 -3 3 5

0 5 -3 3 3 -3 0 2 -2 3 5 2 5 -5 0 1 5 1 -3 0 -5 5 -3 3 2
Alpha-Beta Pruning – Example
= pruned
MAX

MIN 0

MAX 0

MIN 0

MAX 0 3 2

MIN 0 -3 3 2

0 5 -3 3 3 -3 0 2 -2 3 5 2 5 -5 0 1 5 1 -3 0 -5 5 -3 3 2
Alpha-Beta Pruning – Example
= pruned
MAX

MIN 0

MAX 0

MIN 0

MAX 0 3 2

MIN 0 -3 3 2

0 5 -3 3 3 -3 0 2 -2 3 5 2 5 -5 0 1 5 1 -3 0 -5 5 -3 3 2
Alpha-Beta Pruning – Example
= pruned
MAX

MIN 0

MAX 0 2

MIN 0 2

MAX 0 3 2

MIN 0 -3 3 2

0 5 -3 3 3 -3 0 2 -2 3 5 2 5 -5 0 1 5 1 -3 0 -5 5 -3 3 2
Alpha-Beta Pruning – Example
= pruned
MAX

MIN 0

MAX 0 2

MIN 0 2

MAX 0 3 2

MIN 0 -3 3 2

0 5 -3 3 3 -3 0 2 -2 3 5 2 5 -5 0 1 5 1 -3 0 -5 5 -3 3 2
Alpha-Beta Pruning – Example
= pruned
MAX 0

MIN 0

MAX 0 2

MIN 0 2

MAX 0 3 2

MIN 0 -3 3 2

0 5 -3 3 3 -3 0 2 -2 3 5 2 5 -5 0 1 5 1 -3 0 -5 5 -3 3 2
Alpha-Beta Pruning – Example
= pruned
MAX 0

MIN 0

MAX 0 2

MIN 0 2

MAX 0 3 2

MIN 0 -3 3 2 5

0 5 -3 3 3 -3 0 2 -2 3 5 2 5 -5 0 1 5 1 -3 0 -5 5 -3 3 2
Alpha-Beta Pruning – Example
= pruned
MAX 0

MIN 0

MAX 0 2

MIN 0 2

MAX 0 3 2 1

MIN 0 -3 3 2 1

0 5 -3 3 3 -3 0 2 -2 3 5 2 5 -5 0 1 5 1 -3 0 -5 5 -3 3 2
Alpha-Beta Pruning – Example
= pruned
MAX 0

MIN 0

MAX 0 2

MIN 0 2

MAX 0 3 2 1

MIN 0 -3 3 2 1 -3

0 5 -3 3 3 -3 0 2 -2 3 5 2 5 -5 0 1 5 1 -3 0 -5 5 -3 3 2
Alpha-Beta Pruning – Example
= pruned
MAX 0

MIN 0

MAX 0 2

MIN 0 2

MAX 0 3 2 1

MIN 0 -3 3 2 1 -3

0 5 -3 3 3 -3 0 2 -2 3 5 2 5 -5 0 1 5 1 -3 0 -5 5 -3 3 2
Alpha-Beta Pruning – Example
= pruned
MAX 0

MIN 0

MAX 0 2 1

MIN 0 2 1

MAX 0 3 2 1

MIN 0 -3 3 2 1 -3

0 5 -3 3 3 -3 0 2 -2 3 5 2 5 -5 0 1 5 1 -3 0 -5 5 -3 3 2
Alpha-Beta Pruning – Example
= pruned
MAX 0

MIN 0

MAX 0 2 1

MIN 0 2 1

MAX 0 3 2 1

MIN 0 -3 3 2 1 -3 -5

0 5 -3 3 3 -3 0 2 -2 3 5 2 5 -5 0 1 5 1 -3 0 -5 5 -3 3 2
Alpha-Beta Pruning – Example
= pruned
MAX 0

MIN 0

MAX 0 2 1

MIN 0 2 1

MAX 0 3 2 1

MIN 0 -3 3 2 1 -3 -5

0 5 -3 3 3 -3 0 2 -2 3 5 2 5 -5 0 1 5 1 -3 0 -5 5 -3 3 2
Alpha-Beta Pruning – Example
= pruned
MAX 0

MIN 0

MAX 0 2 1

MIN 0 2 1 -5

MAX 0 3 2 1 -5

MIN 0 -3 3 2 1 -3 -5

0 5 -3 3 3 -3 0 2 -2 3 5 2 5 -5 0 1 5 1 -3 0 -5 5 -3 3 2
Alpha-Beta Pruning – Example
= pruned
MAX 0

MIN 0

MAX 0 2 1

MIN 0 2 1 -5

MAX 0 3 2 1 -5

MIN 0 -3 3 2 1 -3 -5

0 5 -3 3 3 -3 0 2 -2 3 5 2 5 -5 0 1 5 1 -3 0 -5 5 -3 3 2
Alpha-Beta Pruning – Example
= pruned
MAX 1

MIN 0 1

MAX 0 2 1

MIN 0 2 1 -5

MAX 0 3 2 1 -5

MIN 0 -3 3 2 1 -3 -5

0 5 -3 3 3 -3 0 2 -2 3 5 2 5 -5 0 1 5 1 -3 0 -5 5 -3 3 2
Alpha-Beta Pruning – Example
= pruned
MAX 1

MIN 0 1

MAX 0 2 1 2

MIN 0 2 1 -5 2

MAX 0 3 2 1 -5 2

MIN 0 -3 3 2 1 -3 -5 2

0 5 -3 3 3 -3 0 2 -2 3 5 2 5 -5 0 1 5 1 -3 0 -5 5 -3 3 2
Alpha-Beta Pruning – Example
= pruned
MAX 1

MIN 0 1

MAX 0 2 1 2

MIN 0 2 1 -5 2

MAX 0 3 2 1 -5 2

MIN 0 -3 3 2 1 -3 -5 2

0 5 -3 3 3 -3 0 2 -2 3 5 2 5 -5 0 1 5 1 -3 0 -5 5 -3 3 2

You might also like