Discussion :

[Sumoner]

Bonjour,
Je voudrais réaliser une intelligence artificiel pour mon jeu de dame. Mais je ne dois pas bien comprendre le principe de l'alpha beta pruning.
J'aimerais que la parcours de l'arbre s’arrête à un certain temps. Mais j'ai l'impression qu'avec mon algorithme il n'y a qu'une seule branche de visiter. De plus il ne coupe jamais de branche.
Si quelqu'un pourrais m'expliquer clairement la demarche à suivre, je serais très reconnaissant.
L'importance n'est pas mon code mais qu'elle est la méthode à appliquer pour arriver à un algorithme qui fonctionne.
Voici ce que j'ai écris en python:

La fonction "evaluation" donne une valeur par rapport à la position sur le damier d'une pièce.

Code python :

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
 
def calc_move(self, pBoard, pDue):
      score =0
      validMoves = pBoard.find_possible_moves(CELL_OWN)
       if len(validMoves) == 1:
          return validMoves[0]
      for move in validMoves:
        pBoard.do_move(move)
        score_move = self.max_value(pBoard, move, pDue, -float('inf'), float('inf'))
        if score_move > score:
          score = score_move
          best_move = move
      return best_move
 
def max_value(self, pBoard, move, pDue, alpha, beta):
    if pDue - time.time() < 0.5 or move.is_EOG():
      return self.evaluation(move, CELL_OWN)
    v = -float('inf')
    validMoves = pBoard.find_possible_moves(CELL_OWN)
    for single_move in validMoves:
      pBoard.do_move(single_move)
      v = max(v, self.min_value(pBoard, single_move, pDue, alpha, beta))
      if v >= beta:
        return v
      alpha = max(alpha, v)
    return v
 
  def min_value(self, pBoard, move, pDue, alpha, beta):
    if pDue - time.time() < 0.5 or move.is_EOG():
      return self.evaluation(move, CELL_OTHER)
    v = float('inf')
    validMoves = pBoard.find_possible_moves(CELL_OTHER) 
    for single_move in validMoves:
      pBoard.do_move(single_move)
      v = min(v, self.max_value(pBoard, single_move, pDue, alpha, beta))
      if v <= alpha:
        return v
      beta = min(beta, v)
    return v

Merci d'avance.

[Pouet_forever]

Pourrais-tu être plus explicite sur ce que tu ne comprends pas ?
Le principe de l'alpha beta est d'explorer l'arbre et d'élaguer les coups inutiles. Si tu ne peux pas explorer l'arbre entier, il te faut ce qu'on appelle une profondeur, pour savoir jusqu'où tu iras explorer ton arbre. Ca permet de garder une cohérence dans ton arbre (tous les noeuds sont explorés à la même profondeur). Si tu utilises le temps, tu risques d'avoir des surprises je pense en fonction des noeuds explorés.

Si tu veux pouvoir jouer en un temps précis, je te conseille l'utilisation de l'algo appelé 'iterative deepening' qui consiste à explorer ton arbre à profondeur 1, puis s'il reste du temps, passer à profondeur 2, puis 3 etc.. Par contre, avec cet algo, tu es obligé d'implémenter des tables de transpositions (stockage des coups intermédiaires) sinon aucun intérêt.

Pour revenir à ton alpha beta, tu veux l'implémenter en négamax ou en simple alpha beta ?