[Résolu] Algorithme du MinMax

Discussion dans 'Programmation' créé par Pe|i, 9 Mars 2008.

Statut de la discussion:
N'est pas ouverte pour d'autres réponses.
  1. Pe|i

    Pe|i Green heart ^.^

    J'aime reçus:
    501
    Points:
    113
    Salam les amis,


    svp j'ai besoin d'aide pour programmer cet algo.

    Ce dont j'ai besoin est comment construire un arbre n-aire en java, afin de lui appliquer l'algo du MinMax.

    J'arrive pas à implémenter cette arbre !!

    ila chi wa7ed fikoum 3andou m3a java i7en 3lina [22h]

    Merci
     
  2. Saad.

    Saad. Accro

    J'aime reçus:
    99
    Points:
    48
    function minimax(node, depth)
    if node is a terminal node or depth = CutoffDepth
    return the heuristic value of node
    if the adversary is to play at node
    let beta := +∞
    foreach child of node
    beta := min(beta, minimax(child, depth+1))
    return beta
    else {we are to play at node}
    let α := -∞
    foreach child of node
    α := max(α, minimax(child, depth+1))
    return α



    exemple :

    [​IMG]

    Suppose the game being played only has a maximum of two possible moves per player each turn. The algorithm generates the tree on the right, where the circles represent the moves of the player running the algorithm (maximizing player), and squares represent the moves of the opponent (minimizing player). Because of the limitation of computation resources, as explained above, the tree is limited to a look-ahead of 4 moves.

    The algorithm evaluates each leaf node using a heuristic evaluation function, obtaining the values shown. The moves where the maximizing player wins are assigned with positive infinity, while the moves that lead to a win of the minimizing player are assigned with negative infinity. At level 3, the algorithm will choose, for each node, the smallest of the child node values, and assign it to that same node (e.g the node on the left will choose the minimum between "10" and "+∞", therefore assigning the value "10" to himself). The next step, in level 2, consists of choosing for each node the largest of the child node values. Once again, the values are assigned to each parent node. The algorithm continues evaluating the maximum and minimum values of the child nodes alternatively until it reaches the root node, where it chooses the move with the largest value (represented in the figure with a blue arrow). This is the move that the player should make in order to minimize the maximum possible loss.


    Minimax theorem with simultaneous moves

    [​IMG]



    The following example of a zero-sum game, where A and B make simultaneous moves, illustrates the minimax algorithm. Suppose each player has three choices and consider the payoff matrix for A displayed at right. Assume the payoff matrix for B is the same matrix with the signs reversed (i.e. if the choices are A1 and B1 then B pays 3 to A). Then, the minimax choice for A is A2 since the worst possible result is then having to pay 1, while the simple minimax choice for B is B2 since the worst possible result is then no payment. However, this solution is not stable, since if B believes A will choose A2 then B will choose B1 to gain 1; then if A believes B will choose B1 then A will choose A1 to gain 3; and then B will choose B2; and eventually both players will realize the difficulty of making a choice. So a more stable strategy is needed.

    Some choices are dominated by others and can be eliminated: A will not choose A3 since either A1 or A2 will produce a better result, no matter what B chooses; B will not choose B3 since B2 will produce a better result, no matter what A chooses.

    A can avoid having to make an expected payment of more than 1/3 by choosing A1 with probability 1/6 and A2 with probability 5/6, no matter what B chooses. B can ensure an expected gain of at least 1/3 by using a randomized strategy of choosing B1 with probability 1/3 and B2 with probability 2/3, no matter what A chooses. These mixed minimax strategies are now stable and cannot be improved.

    John von Neumann proved the Minimax theorem in 1928, stating that such strategies always exist in two-person zero-sum games and can be found by solving a set of simultaneous equations.



    zidak hadi b francais : http://fr.wikipedia.org/wiki/Algorithme_MinMax
     
  3. Pe|i

    Pe|i Green heart ^.^

    J'aime reçus:
    501
    Points:
    113
    lprincipe dial algo 3arfou mziane, le probleme b9a f l'arbre de decision kifach ghadi nsaybha en java. ctt

    merci :)
     
  4. Saad.

    Saad. Accro

    J'aime reçus:
    99
    Points:
    48
    function minimax(node, depth)
    if node is a terminal node or depth = CutoffDepth
    return the heuristic value of node
    if the adversary is to play at node
    let beta := +∞
    foreach child of node
    beta := min(beta, minimax(child, depth+1))
    return beta
    else {we are to play at node}
    let α := -∞
    foreach child of node
    α := max(α, minimax(child, depth+1))
    return α
     
  5. Pe|i

    Pe|i Green heart ^.^

    J'aime reçus:
    501
    Points:
    113
    had algorithme Alpha-Beta (une évolution du MinMax) <D
     
  6. Psy

    Psy Visiteur

    J'aime reçus:
    71
    Points:
    0
  7. Pe|i

    Pe|i Green heart ^.^

    J'aime reçus:
    501
    Points:
    113
    merci khouya amine ^^
     
  8. fola22

    fola22 Visiteur

    J'aime reçus:
    94
    Points:
    0
    c koi svp had algorithme???? ht on vine de commenecer une leçon d'info o dba lina f algo????????
     
  9. Pe|i

    Pe|i Green heart ^.^

    J'aime reçus:
    501
    Points:
    113
    C'est algo d'IA (Intelligence Artificielle). Il permet de simuler le joueur informatique dans pas mal de jeu (morpion, tic-tac-toe, échecs...) :)

    Ps: Problème résolu :)


    Un très grand merci pour vous tous, et un merci spécial pour Saad, Psy et Sadalif
    [23h][23h]
     
Statut de la discussion:
N'est pas ouverte pour d'autres réponses.

Partager cette page