User talk:Wade: Difference between revisions

From OLPC
Jump to navigation Jump to search
No edit summary
Line 11: Line 11:
=== Python Board Game AI Module ===
=== Python Board Game AI Module ===


⚫
"""A basic two player, turn based, game agnostic artificial intelligence.
{{{
⚫
"""A basic two player, turn based, game agnostic artificial intelligence.


Functions:
Functions:
GetMove -- Returns the best move, given a game state and player.
GetMove -- Returns the best move, given a game state and player.
GetRandomMove -- Returns a random valid move, given a game state and player.
GetRandomMove -- Returns a random valid move, given a game state and player.


The AI module interfaces with the game through a State class that is passed
The AI module interfaces with the game through a State class that is passed
to the various functions. This class represents the game from the perspective
to the various functions. This class represents the game from the perspective
of the AI.
of the AI.


It cares nothing about the actual game being played, as long as the State
It cares nothing about the actual game being played, as long as the State
class implements the following set of standard functions. It can be used
class implements the following set of standard functions. It can be used
with anything from Checkers to Tic-Tac-Toe to Risk.
with anything from Checkers to Tic-Tac-Toe to Risk.


State.GenerateMoves()
State.GenerateMoves()
Returns an array of Move objects, representing all possible moves from
Returns an array of Move objects, representing all possible moves from
the current state.
the current state.
State.ApplyMove( Move )
State.ApplyMove( Move )
Executes the contents of a Move object, modifying the game state and
Executes the contents of a Move object, modifying the game state and
incrementing the turn count. The Move object passed in will be one of
incrementing the turn count. The Move object passed in will be one of
those returned by GenerateMoves.
those returned by GenerateMoves.
State.IsMyTurn( Player )
State.IsMyTurn( Player )
Returns True if it is currently Player's turn.
Returns True if it is currently Player's turn.
State.Evaluate( Player )
State.Evaluate( Player )
Returns a heuristic number representing the score of the game state,
Returns a heuristic number representing the score of the game state,
from the perspective of Player.
from the perspective of Player.
State.Copy()
State.Copy()
Returns a copy of the state. Be careful to actually copy objects, not
Returns a copy of the state. Be careful to actually copy objects, not
just reference them.
just reference them.


The apparent intelligence of the AI is highly dependent on three things:
The apparent intelligence of the AI is highly dependent on three things:


1. The quality of the Evaluate function. The better the estimate of the game
1. The quality of the Evaluate function. The better the estimate of the game
state is, the better job the AI will do with limited lookahead.
state is, the better job the AI will do with limited lookahead.


2. The order of moves returned by GenerateMoves. If better moves are sorted
2. The order of moves returned by GenerateMoves. If better moves are sorted
to be earlier, more of the tree will be pruned, and more nodes can be
to be earlier, more of the tree will be pruned, and more nodes can be
searched. This can take into account simple heuristics, like moves which
searched. This can take into account simple heuristics, like moves which
capture a piece, or are towards a goal are returned first.
capture a piece, or are towards a goal are returned first.


3. The performance of the callback functions. Time spent in GetMove is be
3. The performance of the callback functions. Time spent in GetMove is be
dominated by the cost of calling State.GenerateMoves, State.Copy, and
dominated by the cost of calling State.GenerateMoves, State.Copy, and
State.Evaluate. Faster callbacks means a higher depth can be searched in
State.Evaluate. Faster callbacks means a higher depth can be searched in
a reasonable amount of time.
a reasonable amount of time.
Technically, this module implements a MiniMax search with Alpha Beta pruning.
Technically, this module implements a MiniMax search with Alpha Beta pruning.
This is a good, basic AI for simple games, though it will not produce a
This is a good, basic AI for simple games, though it will not produce a
competetive chess game with reasonable search times.
competetive chess game with reasonable search times.


Possible extensions that would improve the AI include iterative deepening, and
Possible extensions that would improve the AI include iterative deepening, and
a state hash database. For real performance though, the AI will probably have
a state hash database. For real performance though, the AI will probably have
to be implemented in C.
to be implemented in C.
"""
"""
import time
import time
import random
import random


# Values for very good and very bad states (+/- infinity for our purposes)
# Values for very good and very bad states (+/- infinity for our purposes)
VeryGood = 1000000
VeryGood = 1000000
VeryBad = -1000000
VeryBad = -1000000


def GetMove( State, Player, CutoffDepth ):
def GetMove( State, Player, CutoffDepth ):
"""Returns the best (highest score) Move for Player given State.
"""Returns the best (highest score) Move for Player given State.
CutoffDepth moves in advance will be searched, this can be used to tune
CutoffDepth moves in advance will be searched, this can be used to tune
the amount of time taken in the search."""
the amount of time taken in the search."""
def MiniMaxAlphaBeta(State, Alpha, Beta, Depth):
def MiniMaxAlphaBeta(State, Alpha, Beta, Depth):
if Depth == 0:
if Depth == 0:
return State.Evaluate( Player )
return State.Evaluate( Player )
Moves = State.GenerateMoves()
Moves = State.GenerateMoves()
if len(Moves) == 0:
if len(Moves) == 0:
return State.Evaluate( Player )
return State.Evaluate( Player )
if State.IsMyTurn( Player ):
if State.IsMyTurn( Player ):
for Move in Moves:
for Move in Moves:
Next = State.Copy()
Next = State.Copy()
Next.ApplyMove( Move )
Next.ApplyMove( Move )
Alpha = max(Alpha, MiniMaxAlphaBeta(Next, Alpha, Beta, Depth-1))
Alpha = max(Alpha, MiniMaxAlphaBeta(Next, Alpha, Beta, Depth-1))
if Beta <= Alpha:
if Beta <= Alpha:
return Alpha
return Alpha
return Alpha
return Alpha
else:
else:
for Move in Moves:
for Move in Moves:
Next = State.Copy()
Next = State.Copy()
Next.ApplyMove( Move )
Next.ApplyMove( Move )
Beta = min(Beta, MiniMaxAlphaBeta(Next, Alpha, Beta, Depth-1))
Beta = min(Beta, MiniMaxAlphaBeta(Next, Alpha, Beta, Depth-1))
if Beta <= Alpha:
if Beta <= Alpha:
return Beta
return Beta
return Beta
return Beta


BestScore = VeryBad
BestScore = VeryBad
BestMove = None
BestMove = None
Moves = State.GenerateMoves()
Moves = State.GenerateMoves()
for Move in Moves:
for Move in Moves:
Next = State.Copy()
Next = State.Copy()
Next.ApplyMove( Move )
Next.ApplyMove( Move )
Score = MiniMaxAlphaBeta(Next, VeryBad, VeryGood, CutoffDepth)
Score = MiniMaxAlphaBeta(Next, VeryBad, VeryGood, CutoffDepth)
if Score > BestScore or (Score == BestScore and random.randint(0, 10) > 5):
if Score > BestScore or (Score == BestScore and random.randint(0, 10) > 5):
BestScore = Score
BestScore = Score
BestMove = Move
BestMove = Move
return BestMove
return BestMove


def GetRandomMove( State, Player ):
def GetRandomMove( State, Player ):
"""Returns a completely random valid move.
"""Returns a completely random valid move.
This can be useful for implementing the absolute lowest level AI possible."""
This can be useful for implementing the absolute lowest level AI possible."""
moves = State.GenerateMoves()
moves = State.GenerateMoves()
return moves[random.randint(0, len(moves)-1)]
return moves[random.randint(0, len(moves)-1)]
}}}

Revision as of 22:14, 16 June 2007

Ideas for Laptop Software

  • Lemonade Stand - Teaches economics. Cons: Text heavy.
  • Math Practice - High speed practice of different mathematical formulas.
  • Math Puzzle - Rearrange equations by applying transformations, to solve simple problems.
  • Generic board game AI in Python
  • BattleZone - 3D open environment multiplayer game. Note: Need to replace violence/war aspect.
  • Better Calculator - 3 modes (simple, advanced, scientific). Simple graphs, fun interface
  • Scanline flat shaded 3D software renderer for PyGame

Python Board Game AI Module

"""A basic two player, turn based, game agnostic artificial intelligence.

Functions: GetMove -- Returns the best move, given a game state and player. GetRandomMove -- Returns a random valid move, given a game state and player.

The AI module interfaces with the game through a State class that is passed to the various functions. This class represents the game from the perspective of the AI.

It cares nothing about the actual game being played, as long as the State class implements the following set of standard functions. It can be used with anything from Checkers to Tic-Tac-Toe to Risk.

State.GenerateMoves() Returns an array of Move objects, representing all possible moves from the current state. State.ApplyMove( Move ) Executes the contents of a Move object, modifying the game state and incrementing the turn count. The Move object passed in will be one of those returned by GenerateMoves. State.IsMyTurn( Player ) Returns True if it is currently Player's turn. State.Evaluate( Player ) Returns a heuristic number representing the score of the game state, from the perspective of Player. State.Copy() Returns a copy of the state. Be careful to actually copy objects, not just reference them.

The apparent intelligence of the AI is highly dependent on three things:

1. The quality of the Evaluate function. The better the estimate of the game state is, the better job the AI will do with limited lookahead.

2. The order of moves returned by GenerateMoves. If better moves are sorted to be earlier, more of the tree will be pruned, and more nodes can be searched. This can take into account simple heuristics, like moves which capture a piece, or are towards a goal are returned first.

3. The performance of the callback functions. Time spent in GetMove is be dominated by the cost of calling State.GenerateMoves, State.Copy, and State.Evaluate. Faster callbacks means a higher depth can be searched in a reasonable amount of time.

Technically, this module implements a MiniMax search with Alpha Beta pruning. This is a good, basic AI for simple games, though it will not produce a competetive chess game with reasonable search times.

Possible extensions that would improve the AI include iterative deepening, and a state hash database. For real performance though, the AI will probably have to be implemented in C. """ import time import random

# Values for very good and very bad states (+/- infinity for our purposes) VeryGood = 1000000 VeryBad = -1000000

def GetMove( State, Player, CutoffDepth ): """Returns the best (highest score) Move for Player given State.

CutoffDepth moves in advance will be searched, this can be used to tune the amount of time taken in the search."""

def MiniMaxAlphaBeta(State, Alpha, Beta, Depth): if Depth == 0: return State.Evaluate( Player )

Moves = State.GenerateMoves() if len(Moves) == 0: return State.Evaluate( Player )

if State.IsMyTurn( Player ): for Move in Moves: Next = State.Copy() Next.ApplyMove( Move ) Alpha = max(Alpha, MiniMaxAlphaBeta(Next, Alpha, Beta, Depth-1)) if Beta <= Alpha: return Alpha return Alpha else: for Move in Moves: Next = State.Copy() Next.ApplyMove( Move ) Beta = min(Beta, MiniMaxAlphaBeta(Next, Alpha, Beta, Depth-1)) if Beta <= Alpha: return Beta return Beta

BestScore = VeryBad BestMove = None Moves = State.GenerateMoves() for Move in Moves: Next = State.Copy() Next.ApplyMove( Move ) Score = MiniMaxAlphaBeta(Next, VeryBad, VeryGood, CutoffDepth) if Score > BestScore or (Score == BestScore and random.randint(0, 10) > 5): BestScore = Score BestMove = Move return BestMove

def GetRandomMove( State, Player ): """Returns a completely random valid move.

This can be useful for implementing the absolute lowest level AI possible."""

moves = State.GenerateMoves() return moves[random.randint(0, len(moves)-1)]

Retrieved from "http://wiki.laptop.org/mediawiki/index.php?title=User_talk:Wade&oldid=43886"