Back to index

gcompris  8.2.2
minmax.py
Go to the documentation of this file.
00001 #  gcompris - connect4 
00002 # 
00003 # Time-stamp: 
00004 # 
00005 # Copyright (C) 2005 Laurent Lacheny 
00006 # 
00007 #   This program is free software; you can redistribute it and/or modify
00008 #   it under the terms of the GNU General Public License as published by
00009 #   the Free Software Foundation; either version 2 of the License, or
00010 #   (at your option) any later version.
00011 # 
00012 #   This program is distributed in the hope that it will be useful,
00013 #   but WITHOUT ANY WARRANTY; without even the implied warranty of
00014 #   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00015 #   GNU General Public License for more details.
00016 # 
00017 #   You should have received a copy of the GNU General Public License
00018 #   along with this program; if not, write to the Free Software
00019 #   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
00020 
00021 #
00022 # This code comes from the project 4stattack
00023 # http://forcedattack.sourceforge.net/
00024 #
00025 #########################################################################
00026 #                            4st Attack 2                               #
00027 #########################################################################
00028 # Created by:                                                           #
00029 # Developer            - "slm" - Jeroen Vloothuis                       #
00030 # Graphics             - "Korruptor" - Gareth Noyce                     #
00031 # Music                - "theGREENzebra"                                #
00032 #########################################################################
00033 # Specail thanks:                                                       #
00034 # chakie(Jan Elkholm)    - letting me "embrace and extend" his gui lib  #
00035 # Mighty(Xander Soldaat) - for the Makefile and the Debian packages     #
00036 # Han                    - for the rpms                                 #
00037 # jk                     - for the FreeBSD port                         #
00038 # Tjerk Nan              - for the Windows version                      #
00039 # Micon                  - for the webdesign                            #
00040 # Everyone in #pygame and the opensource community in general           #
00041 #########################################################################
00042 # This software is licensed under the GPL - General Public License      #
00043 #########################################################################
00044 
00045 import rules
00046 from player import *
00047 from random import *
00048 import copy
00049 from board import *
00050 
00051 class Node:
00052   def __init__(self, board, move, player):
00053     self.board = board
00054     #self.parent = parent
00055     self.value = 0
00056     self.childs = []
00057     self.move = move
00058     self.player = player
00059 
00060   def __repr__(self):
00061     if self.childs > 1:
00062       number=0
00063       for child in self.childs:
00064         number=number+1
00065       return "Has %s child(s)" % number
00066     return "STATE"
00067 
00068 class MinMax(Player):
00069   type = 'AI'
00070 
00071   def __init__(self, difficulty, f):
00072     self.search_depth = difficulty
00073     self.f = f
00074 
00075   def setDifficulty(self, difficulty):
00076     self.search_depth = difficulty
00077 
00078   def evaluate(self, node, player, opponent, depth):
00079     if len(node.childs) > 0:
00080       list = []
00081       for child in node.childs:
00082         list.append(child.value)
00083       if node.player != player:
00084         node.value = min(list)
00085         #print 'min =', node.value,
00086       else:
00087         node.value = max(list)
00088         #print 'max =', node.value,
00089 
00090     else:
00091       node.value = self.score(node, player, opponent)  / (depth + 1)
00092 
00093   def score(self, node, player, opponent):
00094     return int(random() * 100) - 50
00095 
00096 
00097   def makeBoard(self, move, board, player):
00098     temp_board = copy.deepcopy(board)
00099     temp_board.move(move, player)
00100     return temp_board
00101 
00102   def listMoves(self, board, player):
00103     checkmove = rules.isMoveLegal
00104 
00105     options = []
00106     for move in range(7):
00107       if checkmove(board, move):
00108         options.append(move)
00109     return options
00110 
00111   def statespace(self, node, depth, current_player, player, opponent):
00112     self.f() 
00113     if rules.isWinner(node.board, opponent):
00114       #print "a lose up ahead"
00115       node.value = -10000 + depth
00116       return node
00117     elif rules.isWinner(node.board, player):
00118       node.value = 10000 - depth
00119       return node
00120 
00121     elif self.listMoves(node.board, 0) < 1:
00122       self.evaluate(node, player, opponent, depth)
00123       return node
00124     elif depth < self.search_depth:
00125       if current_player==2:
00126         next_player = 1
00127       else:
00128         next_player = 2
00129       for move in self.listMoves(node.board, current_player):
00130         node.board.move(move, current_player)
00131 
00132         node.childs.append(self.statespace(Node( node.board, move, next_player), depth+1, next_player, player, opponent))
00133         node.board.undomove(move)
00134     self.evaluate(node, player, opponent, depth)
00135     #print 'v=%d p=%d' %(node.value,node.player)
00136     return node
00137 
00138 
00139   def doMove(self, current_board, player, event):
00140     board = copy.deepcopy(current_board)
00141 
00142     if player == 1: opponent = 2
00143     else: opponent = 1
00144 
00145     node = Node(board, 0, player)
00146 
00147     node =  self.statespace( node, 0, player, player, opponent);
00148 
00149     bestscore = -100000
00150     best_moves = []
00151     #print "New Round"
00152     for child in node.childs:
00153       #print "Child value=", child.value, "move=", child.board.last_move
00154       if child.value >= bestscore:
00155         #if rules.isMoveLegal(board, child.board.last_move):
00156         if bestscore == child.value:
00157           #print "Move added"
00158           best_moves.append(child.move)
00159         else:
00160           #print "New best move"
00161           bestscore = child.value
00162           best_moves = [child.move]
00163     return best_moves[int(random()*len(best_moves))]
00164 
00165   def gameOver(self, move):
00166     return None
00167 #try:
00168 #  psyco.bind(MinMax)
00169 #  psyco.bind(Node)
00170 #except:
00171 #  pass