Discussion :

[oliverell62]

bonjour,

je viens chercher de l aide sur un algo negamax pour un moteur d echecs,
celuici tourne correctement en minimax, mais la nécessite de passer la vitesse supérieure m oblige a changer pour un alpha_beta ( ou negamax )

je me tourne vers le negamax car moins lourd ...


voici ce que j ai pondu en me referent a divers cite ( wiki fr / en / chessprogramming ...)

precision :
alpha de lancement = - 3 * valeur.val_roi
beta de lancement = 3* valeur.val_roi

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
  Public Function negamax(ByVal chessboard As bitboard, ByVal profondeur As Integer, ByVal alpha As Integer, ByVal beta As Integer) As Integer
 
 
            Dim eval As New evaluation
            Dim best As Integer = -(5 * valeur.val_roi)
            Dim value As Integer = 0
 
            If profondeur = 0 Then
                eval.eval_all_score(chessboard)
                Return eval.score
            End If
 
            Dim mvts As New mouvement.list_of_move
            mvts = chessboard.generate_move
            Dim nb_total As Integer = mvts.moves.Count - 1
            'pour chaque coup possible
            For i = 0 To nb_total
                ' on ajoute le coup a l echiquier
                chessboard.jouer(mvts.moves.Item(i))
 
                ' on ajoute une node
                add_nodes()
 
                value = -negamax(chessboard, profondeur - 1, -beta, -alpha)
 
                If (value > best) Then
                    best = value
                End If
 
                If (best > alpha) Then
                    alpha = best
                End If
 
                If (best >= beta) Then
                    '  MsgBox("exit for")
                    Exit For
                End If
 
 
                chessboard.dejouer(mvts.moves.Item(i))
            Next
 
            Return best
 
 
        End Function

je n arrive a rien
j ai tente une algo alpha beta avec un appel different si min ou max, et rien n y a fait



il doit y avoir une coquille quelque part ...et ca ne doit pas venir de tous les pseudo codes utilisés mais de moi :s

[oliverell62]

ola

j ai avancé pas mal :

ca a l air de fonctionner
ca demande qq vérifications

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
    Public Function negamax(ByVal chessboard As bitboard, ByVal profondeur As Integer, ByVal alpha As Integer, ByVal beta As Integer) As Integer
 
            Dim eval As New evaluation
            Dim local_best_eval As Integer = -4 * valeur.val_roi
            Dim first_time As Boolean = True
            'si feuille : 0
            If profondeur = 0 Then
                eval.eval_all_score(chessboard)
                Return eval.score
            End If
 
            ' création de la liste de coups possible
            Dim mvts As New mouvement.list_of_move
            mvts = chessboard.generate_move
            Dim nb_total As Integer = mvts.moves.Count - 1
            'pour chaque coup possible
            For i = 0 To nb_total
                ' on ajoute le coup a l echiquier
                chessboard.jouer(mvts.moves.Item(i))
 
                ' on ajoute une node
                add_nodes()
 
                If alpha < beta Then
                    local_best_eval = -negamax(chessboard, profondeur - 1, -beta, -alpha)
                    If (local_best_eval > alpha) Then
                        alpha = local_best_eval
                    End If
 
                End If
                ' on dejoue le coup
                chessboard.dejouer(mvts.moves.Item(i))
            Next
 
            Return alpha
 
 
        End Function