Problem Solving Revisited

CS123, Intro to AI

Table of Contents

Introduction

What's Happening

All activities are due Sunday night, 10/13/24

• Exercises for Ch. 2, "Problem Solving" in Elements of AI

• Lecture Q and A forum for online students

• Lecture quiz for everyone.

Next week the first project will be due.

Problem Solving

This is based on Ch. 2 of Elements of AI

Search and Problem Solving

Many problems can be thought of as search problems. We normally think of searching as a way to solve problems like finding a web site, finding a book in a library, or finding a product in an online store. But search can also be used to find the shortest route on a road map or the best sequence of moves to win a game.

The kinds of problems we solve with AI can be classified according to the problem's environment¹ One way of classifying environments is by number of agents²

Two types of search problems (there are more than two) are:

• Problems with only one agent—a route finding problem is an example.

• Problems with two agents—a two-player game is an example.

Single-Agent Problems

Just one agent (would be person if it wasn't AI) is making decisions.

River Crossing Problems

If you search the internet you will find a lot of different logic puzzles involving getting things (or people, animals or other entities) across a river. These are examples of single agent problems since there is only one agent (you, the problem solver) directing the action.

They are search problems since you search the state-space³ to find the minimum number of transitions⁴ between states that will solve the problem.

• Ch.2 of Elements of AI describes the "Chicken, feed, and fox" problem.

• Look at a solution to the Zombies and humans river crossing problem.

  • Breadth-First Search (BFS): This algorithm is one way of solving this problem without trying all the combinations of legal transitions. It explores all possible states level by level. It starts from the initial state and explores all possible moves, then moves to the next level of states. BFS guarantees finding the shortest path (minimum number of river crossings) to the goal state because it explores all nodes at the present depth level before moving on to nodes at the next depth level.

Two-Agent Problems

Two agents are making decisions. It could be two AI systems or an AI system and a human.

Game Playing Problems

Two-player games are examples of two-agent problems.

• Ch. 2 of Elements of AI describes making a game tree for tic-tac toe that can be searched using the minimax algorithm⁵ in order to find winning moves.

• These notes from the Australian National University describe making a game tree for the game of nim, assigning values to nodes, and searching the tree for winning moves.

Real World Problems

• Autonomous Vehicles: In scenarios where two drivers of two vehicles need to interact, such as at an intersection or during lane changes.

• Customer Service: AI chatbots can interact with human customers to resolve issues, answer questions, and provide support.

• Collaborative Robotics: In manufacturing or warehouse settings, AI-powered robots can work alongside human workers or other robots to complete tasks.

Game/Search Trees

See the tictactoe search tree in Elements of AI, Ch. 2

MiniMax Algorithm

he minimax algorithm is a recursive (repetative) decision-making algorithm used in two-player zero-sum games, where one player’s gain is the other player’s loss. The goal is to minimize the maximum possible loss for a worst-case scenario (hence “minimax”).

Steps of the Minimax Algorithm:

1. Generate the Game Tree: Create a tree of all possible moves from the current state to the terminal states (end of the game).

2. Evaluate Terminal States: Assign a value to each terminal state based on the outcome:

   • Positive value for a win.

   • Negative value for a loss.

   • Zero for a draw.

3. Backpropagate Values:
   Starting from the terminal nodes, the algorithm moves up the tree, level by level, to the root. At each level, it applies the minimax decision rule:

   • Maximizing Player’s Turn: Choose the value from the move with the highest value from the child nodes.

   • Minimizing Player’s Turn: Choose the value from the move with the lowest value from the child nodes.

Reference

• Elements of AI—The University of Helsinki and MinnaLearn, 2024. Chapter 2 "AI Problem Solving"

• Understand Types of Environments in Artificial Intelligence—Sandeep Kumar, 2020.

Note: Microsoft Copilot (GPT 4) was used to draft parts of these notes.

Intro to AI lecture notes by Brian Bird, written in 2024, are licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.