[(COMP472)Artificial Intelligence] - Adversarial Search | MiniMax | Alpha-Beta Pruning

[ Adversarial Search ] 

:  a strategy used in artificial intelligence for decision-making in competitive scenarios, such as games. It involves representing the problem as a game tree, using the Minimax algorithm, evaluation functions, and techniques like 

(ex) chess, checkers, and in various real-world domains like business strategy, auctions, and negotiations.

 

 

< Minimax >

: Alpha-Beta Pruning to find optimal or near-optimal strategies. 

2 oppenents

-   Max tries to win

-   MIN tries to minimize MAX’s score

-   Heuristic Function for 2-player games

-> e(n) is a heuristic that estimates how favorable a node n is for MAX with respect to MIN

-> e(n) > 0 : MAX 이길확률 높음, e(n) < 0 : MIN이길확률 높음, e(n) =0 neutral

 

With Minimax, we look at all nodes at depth n

 

-> Exhaustive Minimax Search

- Only for small games

- a strategy that explores all possible moves and their outcomes in a game to find the optimal decision

 

 

 

< Minimax – alpha-beta pruning >

: With alpha-beta pruning, we ignore branches that could not possibly contribute to the final decision

-       Optimization of Minimax

-       Ignores (cuts off/prunes) branches of the tree that cannot contribute to the solution

-       Reduces branching factor

-       Allows deeper search with same effort

 

=> Beta-cutoff : 최대 점수 선택, 이미 저장한 점수보다 작으면 그 노드 제외

=> Alpha cutoff : 최소 점수 선택, 이미 저장한 점수보다 크면 그 노드 제외