ideas for move search...!please!!

[pimidrez]

hi to all!! (sorry for my bad english)

I have a problem of speed with my move search algorithm...
My program have her own interface...Im writing it on "Visual Basic 6.0"...

my generator movements do the next thing...
1-generates all movements for the team, and add its to a LISTBOX1 control.
2-then make the first movement on the list, and generates all the movements that can make the opponent...and add this to a second LISTBOX2 control.
3-then make the first movement of second list, and generates all the movements that can make the first team in that position...(ply=3)...and add this to a third LISTBOX3 control.
4-then evals all the moves in the LISTBOX3...

And so on with all the other movements...

I have Min-Max and Alpha-Beta pruning...but it still being too slow..more than 30 seconds to analyse all movements at only 3 plys!!!

maybe is because I store the scores and movements in Objects and not in vectors or arrays...

If anyone can help me will be great!!!

thankss!!!

[Edmund]

First of all, there are programs other than Visual Basic that compile faster code. Secondly, you are right, using Listboxes instead of arrays is slower. And then it very much depends on your movegenerator and so on.

[Harald Johnsen]

1) Don't use listbox, don't use vector, use simple arrays.
2) check how you give parameters to procedure/functions, and add explicit byval/byref.

here is a simple example :

Code: Select all

Option Explicit

Public Enum CPiece
    none
    pawn
    knight
    bishop
    rook
    queen
    king
    special
End Enum

Public Type CMove
    fromSqr     As Integer
    toSqr       As Integer
    piece       As CPiece
    capture     As CPiece
End Type

Function Eval() As Long
    Eval = Rnd() * 100
End Function


Function genMoves(ByRef moveList() As CMove) As Integer

'    feed the moveList array
'   return number of legal moves
    genMoves = Rnd() * 10 + 20

End Function

Sub doMove(ByRef aMove As CMove)
End Sub
Sub undoMove(ByRef aMove As CMove)
End Sub

Function SimpleSearch(ByVal Alpha As Long, ByVal Beta As Long, ByVal Depth As Integer) As Long

    Dim bestVal As Long, moveCount As Integer, moveIdx As Integer
    Dim moveList(100) As CMove, aMove As CMove

    If Depth <= 0 Then
        SimpleSearch = Eval()
        Exit Function
    End If

    moveCount = genMoves(moveList)
    bestVal = -40000
    moveIdx = 0

    While (moveIdx < moveCount) And (Alpha < Beta)
        Dim Val As Long

        aMove = moveList(moveIdx)
        Call doMove(aMove)
        Val = -SimpleSearch(-Beta, -Alpha, Depth - 1)

        If Val > bestVal Then
            bestVal = Val
        End If

        If Val > Alpha Then
            Alpha = Val
        End If

        Call undoMove(aMove)
        moveIdx = moveIdx + 1
    Wend

    SimpleSearch = bestVal

End Function

Sub iterativeSearch()
    Dim Score As Long, d As Integer

    For d = 1 To 10
        Score = SimpleSearch(-32000, 32000, d)
        Debug.Print d, Score
    Next

End Sub

HJ.

[YvesLejeail]

Hi,
Also, generally speaking don't use Objects since the compiler do a late evaluation of them.
Instead, you can use strong typed variables like integers,...If I remember well List are always considered as Objects. Arrays are faster if they contain strong typed variables.
I'm also using VB but the VB.net which is slower than VB6 . You may reach much more faster NPS and deeper depth with your chess engine.
In addition to all that was suggested, I also recommend you to add Quiescence search, which will increase the depth of search and speed
of your programme, helping a lot in the selection of the best variations, and then in the move ordering...
A lot to do
Yves