Basic Artificial Intelligence

---

Overview of AI

• Want computer to be an interesting opponent
• Turing test - should feel human
• Stupid opponent = totally random
• Godlike opponent = perfect performance
• Best AI = somewhere in between

AI Algorithms

• Often come down to decision tree
• Analyse current situation
• Look for likely moves
• Choose best move
• Evaluate again based on current situation

Foundations of an AI algorithm

• Well-organized data structure
• A heuristic scoring mechanism
• Recursive searching

Well-Organized data structure

• Data is organized in arrays, associative arrays, databases
• Data is set up so it's easy to figure how things are associated
• EG wargames based on map position, unit data
• Card games set up in two dimension array

Heuristic scoring mechanism

• A heuristic assigns points to each possible outcome
• Computer will choose option with best score
• EG bike-rack choosing algorithm
• Decision matrix
• Strength of heuristic often implies power of program

Recursive search

• Examine current position
• Identify all possible moves
• Assign heuristic score to each potential move
• Make best move
• Repeat until
  • You run out of time
  • You've seen all possible outcomes
  • You see a winning solution
  • You see a losing situation

Example: Tic Tac Toe

• Extremely simple game
• AI can be done with if statements, but it gets complex fast
• No way to reasonably extend to a larger (connect 4) context
• Relatively easily solved with an AI Heuristic

Data structure

• game board is an array called board
• cells are numbered 0-9:

   0 | 1 | 2
  ---+---+---
   3 | 4 | 5
  ---+---+---
   6 | 7 | 8
  

• Each cell contains value "X", "O", or "blank";
• WinningCombo array of all winning combinations:

  0	0	1	2
  1	3	4	5
  2	6	7	8
  3	0	3	6
  4	1	4	7
  5	2	5	8
  6	0	4	8
  7	2	4	6

Heuristic

• Assign initial score to each cell based on number of winning combos that use that cell

•  3 | 2 | 3
  ---+---+---
   2 | 4 | 2
  ---+---+---
   3 | 2 | 3
  

• On each turn, look through all winning combinations
• If any two elements in a combo have the same value,
• Add five points to the rank of the remaining cell
• Determine the highest ranking cell
• Move to that cell