2

First, here's some context. My chess engine uses bitboards and works like this: A single gameboard is created as a 2d array at the start of the program. Like this:

[[-4 -2 -3 -5 -6 -3 -2 -4]
 [-1 -1 -1 -1 -1 -1 -1 -1]
 [ 0  0  0  0  0  0  0  0]
 [ 0  0  0  0  0  0  0  0]
 [ 0  0  0  0  0  0  0  0]
 [ 0  0  0  0  0  0  0  0]
 [ 1  1  1  1  1  1  1  1]
 [ 4  2  3  5  6  3  2  4]]

Where each number represents a piece. This 2d board is then converted to 12 bitboards, each representing a set of white or black pieces for each color. The possible legal moves are then generated using various bitboard techniques.

Now to my question: I've written the engine in Python, and so far, the search and evaluate function (a.k.a the minimax function) can only reach a ply of 4. When I try to start going to a ply of 6, the program takes about a good 45-60 seconds to calculate the best move. Any higher ply would make the computer take too long.

Is my implementation inefficient? If not, then any advice on why my engine is so slow would be appreciated. I imagined that with bitboards I could at least reach a ply of 8-12 in Python, even though it's not a very efficient language.

Edit: Also yes, I'm using alpha-beta pruning.

3
  • Does the execution of the evaluation function take a relatively short amount of time? What about the algorythm that searches the move tree? How your board is not the only potential reason why your program is slow
    – David
    May 21, 2021 at 15:29
  • @David, yeah I understand that, but both my evaluation function and minimax function are both, from what I can see, pretty efficient. The evaluation function is just summing up a numpy array, very efficient. And the minimax function is based on the algorithm, so I imagine it's fairly efficient as well. I also already tested the move generation function and at a ply of 6, it begins working incredibly slow. May 21, 2021 at 16:31
  • Have you tried using a profiler? Do you have a perft function? (It's mainly for debugging tasks, but it's a way to compare how good your move generator is with other engines's). Don't know how efficient is python managing 2d arrays, but in other languages like C a 64 length array seems to be preferred to represent the board.
    – emdio
    May 22, 2021 at 5:35

2 Answers 2

5

Generally, I would avoid using Python for chess programming altogether. Consider converting to Cython or better yet, use a modern system language such as Rust, Zig, etc.

3
  • Hmm yeah, unfortunately, that's what I figured. I've been considering golang, do you think it would be efficient enough? May 22, 2021 at 1:45
  • 2
    It is an absolutely defendable choice for your hobby project, but if you would make it to the top on CCRL with that language, this would be a big surprise.. Game search is not efficient, you are literally counting cycles at the tips and can measure every edge easily. That leads to compiled, non gargabe collected, efficiency oriented, simple languages. Stay away from object orientated design also, this won't give you points in the community.
    – user27863
    May 22, 2021 at 8:08
  • 3
    It's worth noting that Python is probably not the only problem here- engines such as Sunfish have been written in Python before and have decent efficiency. There are most likely issues elsewhere in the program
    – pulsar512b
    May 30, 2021 at 19:46
1

If you are not yet using move ordering, I would strongly suggest you do so. Even some basic MVV-LVA helped increase my Python engine's speed by almost 500 percent. Here is some sample code if you want:

def OrderMoves(board, moveList):
    moveScores = []
    pieceIndexDelta = 6 * sideToMove  # given as zero or one, one for white
    for moveIndex in range(len(moveList)):
        currentMove = moveList[moveIndex]
        if move is castling:  # this is only necessary if you handle castling weirdly
            moveScores.append(0)
        elif move is promotion:
            moveScores.append(37 + promotionType)
        elif board[endSquare]:  # if move is a capture
            moveScores.append(6 * (board[endSquare] - pieceIndexDelta) -(board[startSquare] + PieceIndexDelta - 6))
        else:
            moveScores.append(0)
    return [n for _, n in sorted(zip(moveScores, moveList), reverse = True)]

This function will return the moves but sorted with good captures in front. If you have already done this I recommend you explore some more options such as null move pruning, MTD(f), iterative deepening, and quiescence search, all of which are easily accessible on Chess Programming Wiki.

Edit: for this code my piece list is as follows:

0: empty square
1: white pawn
2: white knight
3: white bishop
4: white rook
5: white queen
6: white king
7: black pawn
8: black knight
9: black bishop
10: black rook
11: black queen
12: black king

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.