Minimax Algorithm in Game Theory (Alpha-Beta Pruning)

 

Minimax Algorithm in Game Theory (Alpha-Beta Pruning) in C

---

Description

Aplha-Beta pruning is a optimization technique used in minimax algorithm. The idea benind this algorithm is cut off the branches of game tree which need not to be evaluated as better move exists already.

This algorithm introduces two new fields −

• Alpha − This is best value(maximum) that maximizer player can guaratee at current level or its above level
• Beta − This is the best value(minimum) that minimizer player can guaratee at the current level or its above level.

Example

If game tree is −

arr [] = {13, 8, 24, -5, 23, 15, -14, -20}

then optimal value will be 13 if maximizer plays first

Algorithm

1. Start DFS traversal from the root of game tree
2. Set initial values of alpha and beta as follows:
a. alpha = INT_MIN(-INFINITY)
b. beta = INT_MAX(+INFINITY)
3. Traverse tree in DFS fashion where maximizer player tries to get the highest score possible while the minimizer player tries to get the lowest score possible.
4. While traversing update the alpha and beta values accordingly

Finding a solution that meets a set of constraints is the goal of constraint satisfaction problems (CSPs), a type of AI issue. Finding values for a group of variables that fulfill a set of restrictions or rules is the aim of constraint satisfaction problems. For tasks including resource allocation, planning, scheduling, and decision-making, CSPs are frequently employed in AI.
There are mainly three basic components in the constraint satisfaction problem:
Variables:    The things that need to be determined are variables. Variables in a CSP are the objects that must have values assigned to them in order to satisfy a particular set of constraints. Boolean, integer, and categorical variables are just a few examples of the various types of variables Variables, for instance, could stand in for the many puzzle cells that need to be filled with numbers in a sudoku puzzle.
Domains:     The range of potential values that a variable can have is represented by domains. Depending on the issue, a domain may be finite or limitless. For instance, in Sudoku, the set of numbers from 1 to 9 can serve as the domain of a variable representing a problem cell.
Constraints: The guidelines that control how variables relate to one another are known as constraints. Constraints in a CSP define the ranges of possible values for variables. Unary constraints, binary constraints, and higher-order constraints are only a few examples of the various sorts of constraints. For instance, in a sudoku problem, the restrictions might be that each row, column, and 3×3 box can only have one instance of each number from 1 to 9.
Constraint Satisfaction Problems (CSP) representation:
The finite set of variables V1, V2, V3 ……………..Vn.
Non-empty domain for every single variable D1, D2, D3 …………..Dn.
The finite set of constraints C1, C2 …….…, Cm. 
where each constraint Ci restricts the possible values for variables,
e.g., V1 ≠ V2
 Each constraint Ci is a pair <scope, relation>  
Example: <(V1, V2), V1 not equal to V2> 
Scope = set of variables that participate in constraint. 
Relation = list of valid variable value combinations. 
There might be a clear list of permitted combinations. Perhaps a relation that is abstract and that allows for membership testing and listing.
Constraint Satisfaction Problems (CSP) algorithms:
The backtracking algorithm is a depth-first search algorithm that methodically investigates the search space of potential solutions up until a solution is discovered that satisfies all the restrictions. The method begins by choosing a variable and giving it a value before repeatedly attempting to give values to the other variables. The method returns to the prior variable and tries a different value if at any time a variable cannot be given a value that fulfills the requirements. Once all assignments have been tried or a solution that satisfies all constraints has been discovered, the algorithm ends.
The forward-checking algorithm is a variation of the backtracking algorithm that condenses the search space using a type of local consistency. For each unassigned variable, the method keeps a list of remaining values and applies local constraints to eliminate inconsistent values from these sets. The algorithm examines a variable’s neighbors after it is given a value to see whether any of its remaining values become inconsistent and removes them from the sets if they do. The algorithm goes backward if, after forward checking, a variable has no more values.
Algorithms for propagating constraints are a class that uses local consistency and inference to condense the search space. These algorithms operate by propagating restrictions between variables and removing inconsistent values from the variable domains using the information obtained.