Re: [pygame] Just finished TicTacToe, but How would I do some AI?

["Dave LeCompte (really)" <dave@xxxxxxxxxxxx>]

"Lamonte Harris" <pyth0nc0d3r@xxxxxxxxx> wrote:

> Anywho about the AI, wouldn't it constain a lot of code?

It wouldn't have to be a lot of code.


> Is it possible to
> make this as little code as possible?

Sure.

Other people have pointed you at A*, but you might also look up "minimax"
or "Alpha-Beta Pruning". These are algorithms designed for adversarial
play. Another algorithm that I've played with lately is MTD(f), which is
competitive with higher-end algorithms used for desktop chess games
(leaving aside the chess-specific board evaluation functions).

Some tools that you probably already have will be useful in putting
together a computer player:

- a board representation. This might be a 3x3 array of piece information
for Tic-tac-toe. I suggest wrapping it in a class to help organize the
rest of the code.
- a function or method that determines what moves are legal. If you have
code that knows that the AI can't play on a square that's already taken,
that's enough for Tic-tac-toe.
- a static board evaluation function or method. This may or may not be
connected to determining the winner, if any. A function that returns 100
if x wins, -100 if O wins, and 0 if there's no winner (game still in play,
or a draw) will be sufficient.

Using just those pieces, it's possible to create a "one ply lookahead"
computer player, which isn't very smart at all. The computer player will
take a winning move if it finds one, but it won't block an attack. You can
easily expand it to use minimax search, which will then play perfect
Tic-tac-toe, if that's what you want.

def onePlyLookahead(board):
  bestScore=None
  bestMove=None

  for move in board.legalMoves():

    #create a board object that would be the result of making this move
    newBoard=board.applyMove(move)

    #how good is this new board?
    newScore=newBoard.staticEvaluate()

    if ((bestScore is None) or
        (newScore>bestScore)):
        bestScore=newScore
        bestMove=move

  return bestMove



One of the big challenges in working with game AI is creating computer
players that are good matches for players abilities. An unbeatable
computer player is sometimes possible to code, but almost never fun to
play against. One downside to working with Tic-tac-toe is that the middle
ground between "too smart" and "too dumb" is awfully narrow. Most human
players will be able to play a perfect game all the time, so even a
perfectly matched computer player will consistently play to a draw, which
isn't very fun.

You could add in a randomization element - one move out of three, the
computer player makes a mistake, and chooses a less-than-perfect move.
This might make the computer player a little more satisfying to play
against.


If you're interested in this sort of game, and want to explore adversarial
AI a bit further without biting off very much more complexity, you might
consider the 2x2 Dots and Boxes game:
http://en.wikipedia.org/wiki/Dots_and_Boxes

It's got a similar complexity to Tic-tac-toe, but human players don't tend
to have as much familiarity with the game, so there's more room for a
challenging computer player between the "too smart" and "too dumb"
regions.


Not long ago, as I was exploring this topic, I explored the entire space
of Tic-tac-toe: http://www.bigdicegames.com/tictactoe.pdf

As you already knew, the game is a draw when played perfectly, but I found
it somewhat interesting to see that the rule of thumb I learned as a kid
about always starting in the center square isn't actually important - the
first player can play anywhere on the board and the game's still a draw.


-Dave LeCompte