In this series, we would be exploring, at a high level, some ideas, techniques, and algorithms that are at the foundation of AI. AI covers a wide range of techniques and in this series I would be covering the following categories of problems:
- Search – searching for a solution to a problem, for example driving directions from point A to point B
- Knowledge – making inferences given some information
- Uncertainty – dealing with uncertain events
- Optimization – locating the best option among a possible set of solutions
- Learning – being able to perform a task by learning from data
- Neural Networks – drawing inspiration from human intelligence
- Language – understanding natural language
In this post, we will explore Search and Knowledge.
1. Search
Search problems are those where the computer tries to figure out what to do when in a particular situation.
Examples
These problems can come in many different types of formats. Some examples are:
- Navigating through a maze to travel from an initial state to a final goal
- Finding driving directions from point A to point B
- Playing games such as Tic-Tac-Toe, Chess, etc.
Approach
The algorithms that are commonly used for solving classical search problems are Depth-first search, Breadth-first search, Greedy Best First search and A* search.
Adversarial search is where the agent is trying to make intelligent decisions and there is someone else such as an opponent who has the opposite objective and trying to win the game for itself. A popular example of this would be a game of Tic-Tac-Toe.
Minimax is an algorithm that can be used to solve adversarial search problems. The algorithm evaluates the various moves the opponent could take in a particular situation and determines the optimal move to make to win the game.
In a simple game such as Tic-Tac-Toe, it is possible to evaluate all the possible moves of the opponent. But in more complex games such as Chess, it is computationally intractable to evaluate all the possible options. This is where optimization methods to estimate the optimal move without having to compute all the alternatives become important. Evaluation function is one such method.
How good the AI is at playing a game would ultimately depend on how good the evaluation function is at estimating how good or bad a particular game state is.
2. Knowledge
Knowledge problems are those where the computer makes inferences or deductions based on facts and logical reasoning.
Examples
Consider the following statements.
- If it didn’t rain, Harry visited Hagrid today.
- Harry visited Hagrid or Dumbledore today, but not both.
- Harry visited Dumbledore today.
From these statements, AI will derive the following:
- Harry did not visit Hagrid today.
- It rained today.
Application for this problem type would be in playing games such as Clue, Mastermind, etc. and solving logical puzzles.
Approach
Knowledge Engineering is the process of encoding known facts and logic in AI and making AI logical so they can do the reasoning and make deductions.
Model Checking is an algorithm behind the scenes. The idea is to encode all the statements using Propositional Logic and apply Model Checking to make deductions.
Another approach is to convert all the statements to Conjunctive Normal Form by using Inference Rules. Then we can apply Inference by Resolution to solve the puzzle. First-Order Logic is another algorithm ideal for complex logical puzzles.
Reference: CS50’s Introduction to Artificial Intelligence with Python