Discussion :

[tsing]

Bonjour,

Je m'interroge sur l'implémentation de la fonction Alpha-beta ci-dessous.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
 92 def alphaBetaWithMemory(node, alpha, beta, depth, printDepth): 
 93      indent=printDepth-depth 
 94      indentString="    "*indent 
 95      #print indentString,"in ABwM(node=%d, alpha=%d, beta=%d, depth=%d)"%(node,alpha,beta,depth) 
 96      transTableInfo=transTable.lookup(node, depth) 
 97   
 98      if transTableInfo: 
 99          #print indentString,"got transTableInfo: [%d, %d] depth: %d"%(transTableInfo.lowerBound, 
100          #                                                             transTableInfo.upperBound, 
101          #                                                             transTableInfo.furthestDepthSearched) 
102          if transTableInfo.lowerBound >= beta: 
103              return transTableInfo.lowerBound 
104          if transTableInfo.upperBound <= alpha: 
105              return transTableInfo.upperBound 
106          alpha = max(alpha, transTableInfo.lowerBound) 
107          beta = min(beta, transTableInfo.upperBound) 
108   
109      terminal=isTerminal(node) 
110      if depth==0 or terminal: 
111          g=evaluate(node, AIPLAYER) 
112          #print indentString,"evaluating [%d] got %d"%(node,g) 
113      elif isMaximizing(node): 
114          g = NEGINFINITY 
115          a = alpha 
116          for c in getChildren(node): 
117              if g >= beta: 
118                  break 
119              g=max(g,alphaBetaWithMemory(c, a, beta, depth-1, printDepth)) 
120              a=max(a,g) 
121      else: 
122          g = POSINFINITY 
123          b = beta 
124          for c in getChildren(node): 
125              if g <= alpha: 
126                  break 
127              g = min(g,alphaBetaWithMemory(c, alpha, b, depth-1, printDepth)) 
128              b = min(b,g) 
129   
130      if g <= alpha: 
131          transTable.storeUpperBound(node,g) 
132      elif g > alpha and g < beta: 
133          transTable.storeLowerBound(node,g) 
134          transTable.storeUpperBound(node,g) 
135          raise "never happens" 
136      else: 
137          transTable.storeLowerBound(node,g) 
138      transTable.storeDepth(node, depth) 
139      transTable.setTerminal(node, terminal) 
140      return g

Source : http://www.meatengine.com/Docs/MeatE...BetaWithMemory
Tout d'abord, je ne vois pas bien ce que font les fonctions min(arg1, arg2) et max(arg1, arg2). A mon avis la 1ère retourne le plus petit argument et la 2ème le plus grand, mais j'aimerais avoir votre confirmation.
Et enfin, sauriez-vous pour quelle raison cette fonction est dite sans mémoire ?

Merci

[ToTo13]

Bonjour,

Et enfin, sauriez-vous pour quelle raison cette fonction est dite sans mémoire ?

WithMemory veut dire avec mémoire. Sinon il y aurait without memory.

[tsing]

WithMemory veut dire avec mémoire. Sinon il y aurait without memory.

Oula, oui en effet. C'est ce que je voulais dire...
Pardon pour l'erreur

[tsing]

Up

[progfou]

Tout d'abord, je ne vois pas bien ce que font les fonctions min(arg1, arg2) et max(arg1, arg2). A mon avis la 1ère retourne le plus petit argument et la 2ème le plus grand, mais j'aimerais avoir votre confirmation.

Il faut rire ? Non, sérieusement... on n'a pas besoin de te le confirmer quand même

Et enfin, sauriez-vous pour quelle raison cette fonction est dite sans mémoire ?

Pas besoin de répéter ce qu'a écrit ToTo13... Si c'est avec mémoire, ça veut dire qu'il a besoin de mémoire pour fonctionner...
Donc pour t'éviter cela:

http://www.cs.vu.nl/~aske/mtdf.html
Note that the MTD(f) code calls an AlphaBeta version that stores its nodes in memory