I need help..again..flow diagrams

[pimidrez]

Hi, everyones!

I created a topic to see if someone has a flow diagram of the chess engine structure, basically my problem is that I can not realize how to do the move-generation recursively...
In my very own chess engine, write in VB6, I programmed each ply separately storing each movement and their scores on variables or list objects... but thats wrong.. so the engine is forced to go all the ply that I have written in the code and then make the move.

anyway...I shall be grateful if someone could give me some detailed diagrams.

SI LA RESPUESTA ES EN EPAÑOL MEJOR

[Dann Corbit]

Look at how LarsenVB did it:
http://cap.connx.com/chess-engines/new- ... RSENVB.ZIP

The basic idea is something like this (it probably would not work without some effort, but the skeleton should be OK):

Code: Select all

        Public Function AlphaBeta(ByVal depth As Integer, ByVal alpha As Integer, ByVal beta As Integer, ByVal whiteToMove As Boolean) As Integer
            Me.nodeCount = Me.nodeCount + 1
            If (depth <= 0) Then
                Return Me.Game.evaluate(whiteToMove)
            End If
            Dim s As New Stack
            Me.Game.GenerateMoves(s, whiteToMove)
            If (s.Count <> 0) Then
                Do While (s.Count > 0)
                    Dim currentMove As Move
                    currentMove = s.Pop
                    Me.Game.makeMove(currentMove)
                    ' The recursive call is here.  Notice that we have decremented depth!
                    Me.val = -Me.AlphaBeta((depth - 1), -beta, -alpha, Not whiteToMove)
                    Me.Game.UnmakeMove
                    If (Me.val >= beta) Then
                        Return beta
                    End If
                    If (Me.val > alpha) Then
                        alpha = Me.val
                        If (depth = Me.defaultply) Then
                            Me.bestmove = currentMove
                        End If
                    End If
                Loop
                Return alpha
            End If
            Return 0
        End Function


[pimidrez]

Look at how LarsenVB did it:
http://cap.connx.com/chess-engines/new- ... RSENVB.ZIP

The basic idea is something like this (it probably would not work without some effort, but the skeleton should be OK):

Code: Select all

        Public Function AlphaBeta(ByVal depth As Integer, ByVal alpha As Integer, ByVal beta As Integer, ByVal whiteToMove As Boolean) As Integer
            Me.nodeCount = Me.nodeCount + 1
            If (depth <= 0) Then
                Return Me.Game.evaluate(whiteToMove)
            End If
            Dim s As New Stack
            Me.Game.GenerateMoves(s, whiteToMove)
            If (s.Count <> 0) Then
                Do While (s.Count > 0)
                    Dim currentMove As Move
                    currentMove = s.Pop
                    Me.Game.makeMove(currentMove)
                    ' The recursive call is here.  Notice that we have decremented depth!
                    Me.val = -Me.AlphaBeta((depth - 1), -beta, -alpha, Not whiteToMove)
                    Me.Game.UnmakeMove
                    If (Me.val >= beta) Then
                        Return beta
                    End If
                    If (Me.val > alpha) Then
                        alpha = Me.val
                        If (depth = Me.defaultply) Then
                            Me.bestmove = currentMove
                        End If
                    End If
                Loop
                Return alpha
            End If
            Return 0
        End Function


Thanks Dann, thanks this will help me a lot ...
but I still have some doubts about it means the following parts of code:

Dim s As New Stack '----> the variable s is like a counter that has kept the number of the quantity of movement, right?

currentMove = s.Pop '-----> what did you mean with "s.pop"


thanks again!

[Daniel Uranga]

Un "stack" es una pila. Es como decirte una lista, donde solo se pueden agregar elementos al principio, y solo se pueden sacar los del principio (pensa en una pila de monedas, que para agregar una moneda siempre la colocas arriba de todas, y para sacar solo podes sacar la de mas arriba tambien). Cuando hace "currentMove = s.Pop" esta sacando el elemento de "mas arriba" de la pila s, y se lo esta asignando a currentMove. Repite eso mientras queden movimientos en la pila s (que lo comprueba con s.Count > 0).
Ojala te sirva. Saludos!

[pimidrez]

Gracias Daniel! se entendio a la perfeccion... dejo unas preguntas más para quien me pueda seguir ayudando:

ENGLISH
1) When I call for the first time this function:

Public Function AlphaBeta(ByVal depth As Integer, ByVal alpha As Integer, ByVal beta As Integer, ByVal whiteToMove As Boolean) As Integer

What value should I give to the variables depth,alpha,beta?? or how do I get it??

2)The next portion of code, what does it exactly? Just take part in the final of the search or before in the beginning?

If (depth <= 0) Then
Return Me.Game.evaluate(whiteToMove)
End If


**************************************************
**************************************************

ESPAÑOL
1) Cuando se llama por primera vez a la funcion:

Public Function AlphaBeta(ByVal depth As Integer, ByVal alpha As Integer, ByVal beta As Integer, ByVal whiteToMove As Boolean) As Integer

Con que valor entra la variable DEPTH??...es decir yo llamo a la funcion, que valores le tengo que dar a cada una de las variables: DEPTH,ALPHA,BETA??? o como los obtengo??

2) La siguiente porción del codigo que hace exactamente? solo tomar parte en el principio o al final de cada busqueda?

If (depth <= 0) Then
Return Me.Game.evaluate(whiteToMove)
End If


Gracias de nuevo!

[Dann Corbit]

Gracias Daniel! se entendio a la perfeccion... dejo unas preguntas más para quien me pueda seguir ayudando:

ENGLISH
1) When I call for the first time this function:

Public Function AlphaBeta(ByVal depth As Integer, ByVal alpha As Integer, ByVal beta As Integer, ByVal whiteToMove As Boolean) As Integer

What value should I give to the variables depth,alpha,beta?? or how do I get it??

alpha and beta are the search window.
depth is the number of plies you want to search.

2)The next portion of code, what does it exactly? Just take part in the final of the search or before in the beginning?

If (depth <= 0) Then
Return Me.Game.evaluate(whiteToMove)
End If

When your engine is done, you will really have a call to quiesce() here, but for starters you can just return evaluate().
The idea is that you have searched all the plies and it is time to return, but return what?
A zero ply search is approximately an evaluation (though a real search of zero plies will really make sure that all beneficial exchanges have been examined).

**************************************************
**************************************************

ESPAÑOL
1) Cuando se llama por primera vez a la funcion:

Public Function AlphaBeta(ByVal depth As Integer, ByVal alpha As Integer, ByVal beta As Integer, ByVal whiteToMove As Boolean) As Integer

Con que valor entra la variable DEPTH??...es decir yo llamo a la funcion, que valores le tengo que dar a cada una de las variables: DEPTH,ALPHA,BETA??? o como los obtengo??

2) La siguiente porción del codigo que hace exactamente? solo tomar parte en el principio o al final de cada busqueda?

If (depth <= 0) Then
Return Me.Game.evaluate(whiteToMove)
End If


Gracias de nuevo!

[pimidrez]

So when I have searched all the plies and "depth <= 0" then I call to evaluate the last ply in every move??

for example the engine is searching at 3 plies:

e2e4 e7e5 g1f3

the engine will evaluate only the final position with the knight in f3?? and return then the value of the position??

[Dann Corbit]

So when I have searched all the plies and "depth <= 0" then I call to evaluate the last ply in every move??

for example the engine is searching at 3 plies:

e2e4 e7e5 g1f3

the engine will evaluate only the final position with the knight in f3?? and return then the value of the position??

The value of that position will be returned only for a zero ply search.
The value of the search will be returned for any search of more than one ply.

So you can think of it another way:
A zero ply search is what you will get for any leaf on the end of the tree.
A one ply search will give you the best leaf from that group.
A two ply search will give you the best mini-maxed leaf value from each 2 ply group of one ply groups.
I can't think of a simpler way to put it. Have you read Bruce Moreland's article on alpha-beta? He describes it a lot better than I can.
http://web.archive.org/web/200404200223 ... habeta.htm

[pimidrez]

Thanks Dann, now I get the idea! I read the article and is very clear.
but now let me ask you about one detail of the alpha-beta algorithim...

if the engine find a bad movement, for ex. g1f3, and should cut off because is not necesary to keep searching in that way...now..do I have to eliminate that movement (g1f3) from the list? Or is this not necessary?

pimidrez

[Dann Corbit]

Thanks Dann, now I get the idea! I read the article and is very clear.
but now let me ask you about one detail of the alpha-beta algorithim...

if the engine find a bad movement, for ex. g1f3, and should cut off because is not necesary to keep searching in that way...now..do I have to eliminate that movement (g1f3) from the list? Or is this not necessary?

pimidrez

The alpha-beta routine I posted does the cutoff.

[Dann Corbit]

Thanks Dann, now I get the idea! I read the article and is very clear.
but now let me ask you about one detail of the alpha-beta algorithim...

if the engine find a bad movement, for ex. g1f3, and should cut off because is not necesary to keep searching in that way...now..do I have to eliminate that movement (g1f3) from the list? Or is this not necessary?

pimidrez

The alpha-beta routine I posted does the cutoff.

Let me add more:
You will see things like:
makemove(TheMove) ' Perform the move TheMove
unmake() ' Undo the last move that was made
in the code.

Those handle that bit for you, but it assumes you have written those routines.

[pimidrez]

yes I already write those routines, now let me give easy an example and maybe you can say me how goes the cutoff of the alpha-beta:

*black side to move after the first movement of the white pieces ---> 1. e2e4 ....
*Now suppose that the black have the following possible responses, with the value of the position in parentheses:
1.... e7e5 (2)
1.... d7d5 (1)
1.... b8c6 (2.5)

*now suppose that the WHITES have the following possible responses for each one of the previusly responses of the blacks.

Code: Select all

     *PLY1*     *PLY2*            *PLY1*     *PLY2*                 *PLY1*        *PLY2*
1.... e7e5 (2)  2.g8f6 (1)   1.... d7d5 (1)  2.b1c3 (3)        1.... b8c6 (2.5)   2.b1c3 (1)
                2.d2d4 (1.5)                 2.d2d4 (1)                           2.d2d4 (2)
                2.b1c3 (2)                   2.d2d3 (1.5)                         2.g8f6 (1.5)

[Dann Corbit]

yes I already write those routines, now let me give easy an example and maybe you can say me how goes the cutoff of the alpha-beta:

*black side to move after the first movement of the white pieces ---> 1. e2e4 ....
*Now suppose that the black have the following possible responses, with the value of the position in parentheses:
1.... e7e5 (2)
1.... d7d5 (1)
1.... b8c6 (2.5)

*now suppose that the WHITES have the following possible responses for each one of the previusly responses of the blacks.

Code: Select all

     *PLY1*     *PLY2*            *PLY1*     *PLY2*                 *PLY1*        *PLY2*
1.... e7e5 (2)  2.g8f6 (1)   1.... d7d5 (1)  2.b1c3 (3)        1.... b8c6 (2.5)   2.b1c3 (1)
                2.d2d4 (1.5)                 2.d2d4 (1)                           2.d2d4 (2)
                2.b1c3 (2)                   2.d2d3 (1.5)                         2.g8f6 (1.5)

See:
http://www.cs.mcgill.ca/~cs251/OldCourses/1997/topic11/
http://en.wikipedia.org/wiki/Alpha-beta_pruning
https://chessprogramming.wikispaces.com/Alpha-Beta

[pimidrez]

yes I already write those routines, now let me give easy an example and maybe you can say me how goes the cutoff of the alpha-beta:

*black side to move after the first movement of the white pieces ---> 1. e2e4 ....
*Now suppose that the black have the following possible responses, with the value of the position in parentheses:
1.... e7e5 (2)
1.... d7d5 (1)
1.... b8c6 (2.5)

*now suppose that the WHITES have the following possible responses for each one of the previusly responses of the blacks.

Code: Select all

     *PLY1*     *PLY2*            *PLY1*     *PLY2*                 *PLY1*        *PLY2*
1.... e7e5 (2)  2.g8f6 (1)   1.... d7d5 (1)  2.b1c3 (3)        1.... b8c6 (2.5)   2.b1c3 (1)
                2.d2d4 (1.5)                 2.d2d4 (1)                           2.d2d4 (2)
                2.b1c3 (2)                   2.d2d3 (1.5)                         2.g8f6 (1.5)

See:
http://www.cs.mcgill.ca/~cs251/OldCourses/1997/topic11/
http://en.wikipedia.org/wiki/Alpha-beta_pruning
https://chessprogramming.wikispaces.com/Alpha-Beta

So I was looking a gif animation inside of the wiki link: http://en.wikipedia.org/wiki/File:Minmaxab.gif
and I see that the evaluation function is applied to the final leaf and then start to cutoff the branches with alpha-beta algorithim. Does this applies to chess?
if Im right this not applies to chess... unless we have constant plies to search.

[Dann Corbit]

Alpha beta is a basic algorithm that works the same everywhere.

It you looke at the bit here:

Code: Select all

                    If (Me.val >= beta) Then
                        Return beta
                    End If
                    If (Me.val > alpha) Then
                        alpha = Me.val
                        If (depth = Me.defaultply) Then
                            Me.bestmove = currentMove
                        End If
                    End If


That is where it returning the value to the caller.
For a one ply search, it will return your best move.
For a two ply search it will return the result of:
{for each of my moves, which one has the worst result for the opponent after his reply?}
For a three ply search it will return the result of:
{for each of my moves, which one has the worst result for the opponent after my reply to his reply?}

I suggest that you take a very simple alpha-beta and actually trace the code as it searches. Then it will become both clear and obvious what is going on.

[pimidrez]

Thanks Dann, then I think I am going in the right direction..
Now Im apling a small evaluation function with only material values, and let's supoose that the side to move is black...
at ply 1 the evaluation result will be:

Value = BlackMaterial - WhiteMaterial (?) and ALPHA will be the max value

and at ply 2 the evaluation result will be:

Value = BlackMaterial - WhiteMaterial (?) and BETA will be the min value

is this right??

[Dann Corbit]

Thanks Dann, then I think I am going in the right direction..
Now Im apling a small evaluation function with only material values, and let's supoose that the side to move is black...
at ply 1 the evaluation result will be:

Value = BlackMaterial - WhiteMaterial (?) and ALPHA will be the max value

and at ply 2 the evaluation result will be:

Value = BlackMaterial - WhiteMaterial (?) and BETA will be the min value

is this right??

At ply 2 the value will be:
-(WhiteMaterial - BlackMaterial)
Since for ply 2, the analysis will be from white's perspective, but negated by the caller.