Graph Theory Quiz

Adversary Search

• Adversary search is a technique used in game playing to determine the best move in a game where the opponent plays optimally.
• It involves analyzing possible moves, considering the opponent's responses, and evaluating outcomes to predict the best result.
• Key games analyzed include Tic-Tac-Toe, 4 in a row, Checkers, Chess, Go.
• Examples of games are visualized in slides.

Index

• The presentation covers an introduction to the topic followed by
  • MiniMax algorithms.
  • αβ-pruning
  • Heuristic search (A-star)
  • Dynamic Programming,
  • Graphs

Introduction

• Adversary search deals with uncertain situations between two players with the goal to model and anticipate the optimal play in different game scenarios, such as Chess, Go.
• It requires modeling the opponent's behaviour.
• A heuristic function that evaluates the position is necessary.
• The search needs to be truncated to a reasonable depth.

MiniMax algorithm

• The minimax algorithm is a recursive algorithm used in adversarial search.
• It assumes the opponent plays optimally to maximize their own gain.
• A game tree is used to model the game, where nodes represent game states and edges represent possible moves.
• Nodes at an odd level are evaluated by the maximizer, at an even level are by the minimizer.
• A heuristic function is applied to evaluate terminal nodes.
• Computation complexity can be very high, therefore αβ-pruning is often used.

αβ-pruning

• αβ-pruning is a branch and bound optimization technique for MiniMax making the decision process less computationally demanding.
• It works by assigning upper (β) and lower (α) bounds to the search.
• If a child node is bounded by values worse than the best found parent then the branch can be pruned, reducing the game tree to be explored.
• It considers a part of the game tree only, reducing the computations.

Heuristic search

• Heuristic search in state spaces algorithms are used to find the best solution from an initial to a final state.
• Represent possible states and possible transitions using a graph.
• Create states using simple forms to represent the problem efficiently for the computer.
• Use a heuristic function to order or organize the states to traverse efficiently.
• Important examples include the sliding tiles puzzle and the N queens problem.
• An example of such heuristic search in state spaces algorithm is A*.

Dynamic Programming

• Dynamic programming is an efficient algorithm design technique for optimization problems.
• It is based on breaking down a problem into smaller sub-problems and reusing their solutions to speed up the process.
• There are two main approaches to implement Dynamic Programming:
• Top-down DP (memoization): Recursively solves subproblems, storing their solutions in a table (cache) to avoid redundant computations. It is faster than brute-force.
• Bottom-up DP: Iteratively solves subproblems starting from base case and working upwards. It is usually faster than top-down, as it does not have recursive overhead.

Graphs

• A graph is a data structure consisting of nodes and edges that connect these nodes.
• Graphs are used to represent relationships and connections between different entities.
• Types of graphs include
  • Directed graphs: Edges have a specific direction.
  • Undirected graphs: Edges have no specific direction
  • Weighted graphs: Edges have numerical weights to represent strength, cost, or importance of the relationship between nodes.
• Graphs can be represented with adjacency matrices or adjacency lists.

Tree Traversal

• A tree is a hierarchical data structure consisting of nodes and edges that connect these nodes.
• Traversal of a tree requires visiting each node in certain order.
• The most common types of tree traversals are
  • Depth-first search (DFS): - Visits nodes in depth order to the leaves and then proceeds to nearby branches, and so on, until it reaches the end of a branch. - Uses stacks.
  • Breadth-first search (BFS): - Visits node level by level. - Uses queues.

Recursion

• Recursion is a method to solve a problem by constantly breaking it down into smaller subproblems.
• Crucial components are the base case (stopping condition) and recursive steps involved.
• Typical use case includes computation for factorial, Fibonacci series, or problems in which there is a natural hierarchical nesting and subproblems have the same form, so recursive function is a natural approach and the problem can be easily solved.
• A stack data structure is commonly used to store function calls.
• Algorithms use memorization to memoize (store) already computed intermediate results to accelerate the process. Tail recursion is an optimization technique that reduces the overhead of recursion.

Complexity

• Algorithms have different computational properties.
• Complexity is a measure of how the resources used by an algorithm (e.g. time) scale with the input size.
• Big O notation (e.g. O(n)) is used to express this scaling. It describes an upper bound on the growth rate of resource usage.
• The input size (n) is normally the number of elements that must be analyzed to arrive at a solution or complete the assignment.
• Common types of complexity include O(1), O(log n), O(n), O(n log n), O(n^2), O(n^3), O(2^n), O(n!).
• Often, the most efficient algorithm is used for larger input size values.