Chapter 10 Artificial Intelligence
----------------------------------

Can Computers and Robots be as intelligent as a human being?

Artificial Intelligence - term coined to denote intelligence of 
a machine.

Some examples of AI
-------------------

(1) Language Understanding

Can computers understand natural languages?

(2) Game Playing

lots of success in this area;
1996 Chess program - Deep Blue from IBM beat the
World Chess Champion Kasparov in a game
1997 - Deep Blue won a match

basic strategy is to look forward several moves,
evaluate each possibility and choose the next move
based on highest gains.

Tic Tac Toe

def play():
  # Initialize board
  board = makeBoard()

  # set who moves first/next: X always moves first
  player = 'X'

  # Display the initial board
  display(board)

  # The game loop
  while (not gameOver(board)):
    move(board,player)
    display(board)
    player = opponrnt(player)

  # game over; show outcome
  winningPiece = winner(board)

  if winningPiece != 'Tie':
    print winningPiece, "won."
  else:
    print "It is a tie."


makeBoard(): returns a fresh new board representing the start of the game.
For Tic Tac Toe, this will return a empty board with nine blanks.

displayBoard(board): displays board on the screen.

opponent(player): returns the opponent of the current player (if 
player is X return O otherwise return X)

move(board,player): update board by making one move (for player
read move from input; for computer decide how best to move - smart
move)

gameOver(board): returns True if no more moves left to be made;
False otherwise.

winner(board): examine board and return winner (X, O, TIE, or blank if
game is not over)

Assume X always goes first.

board = [' ',' ',' ',' ',' ',' ',' ',' ',' ']

#############################################################
def makeBoard():
    # A 3x3 board is represented as a list of 9 elements.
    # We will use the following numbering to locate a square
    #  0 | 1 | 2
    # ---|---|---
    #  3 | 4 | 5
    # ---|---|---
    #  6 | 7 | 8

    return [' ',' ',' ',' ',' ',' ',' ',' ',' ']

def display(board):
    for i in range(0, 9, 3):
        if i > 0:
            print '---|---|---'
        print " %c | %c | %c "%(board[i],board[i+1],board[i+2])

def opponent(player):
    if player == "X":
        return "O"
    else:
        return "X"

from random import choice

You = 'X'
Me = 'O'

def move(board, player):
    if player == You:       # user's move?
        square = input("Enter your move: ") - 1
    else:                   # my turn
        # player is the computer, make a random choice
        square = choice(possibleMoves(board, player))

    # place player's piece on the chosen square
    applyMove(board, player, square)

def possibleMoves(board, player):
# return possible moves for given player
    moves = []
    for i in range(9):
        if board[i] == ' ':
            moves.append(i)
    return moves

def applyMove(board, player, square):
    board[square] = player

# These square triples represent wins (three in a row).

WINS = [[0, 1, 2],[3, 4, 5],[6, 7, 8],      # the rows
        [0, 3, 6],[1, 4, 7],[2, 5, 8],      # the columns
        [0, 4, 8],[2, 4, 6]]                # diagonals

def winner(board):
    for win in WINS:
        posWinner = board[win[0]]
        if (posWinner != ' ' and
            posWinner == board[win[1]] and
            posWinner == board[win[2]]):
            return posWinner

    # No winner yet, are there empty squares left?
    for i in range(9):
        if board[i] == ' ':
            return ' '

    # The board is full and no one has three in a row
    return 'Tie'

def gameOver(board):
    return winner(board) != ' '

def play():
    # Initialize board
    board = makeBoard()
    
    # set who moves first/next: X always moves first
    player = 'X'
    
    # Display the initial board
    display(board)
    
    # The game loop
    while (not gameOver(board)):
        move(board, player)
        display(board)
        player = opponent(player)
       
    # game over, show outcome
    winningPiece = winner(board)
     
    if winningPiece != 'Tie':
        print winningPiece, "won."
    else:
        print "It is a tie."

play()
########################################

Play the game with the computer - easy to beat the computer!
This is because computer is picking the move randomly!

square = choice(possibleMoves(board,player))

Now we will add intelligence to the computer's move;

square = bestMove(board,player,possibleMoves(board,player))

Strategies: defensive - try not to lose
offensive - try to win
if win or loss is not imminent; try best move