My PHP Chess Move Generator is slow. Help!

[AdmiralAdama]

Hey there,

For fun and for programming practice, I recently created a chess move generator. I did it in my most comfortable language (PHP, a server side web language, the same language this forum is written in), without reading any literature on how to structure the program.

Click here to view the code. Click here to view the website (index.php, perft.php)

I ended up using lots of OOP. I created the following classes: ChessRulebook (static), ChessMove, ChessBoard, ChessPiece, ChessSquare.

I believe my move generation code to be bug free. I've tested about 20 perfts to depth 2 and everything passes.

However my code is SLOW. VERY SLOW. So slow that I can't perft beyond depth 2. Here is the speed of my program to compute the legal moves list for 1 board position.
- Originally 1500 ms
- After profiling and optimizing my code (details here), 99ms
- Turning off detailed notation (+ # Rab1 type notation), 33ms

This is still WAY TOO SLOW if I ever want to use this code in a chess engine. I am hoping that you all can give me tips for speeding up my code.

1) What are the best ways to speed up the code without completely redesigning everything? Any easy tweaks I can make? (example: replacing ChessSquare with a string)

2) What are the best ways to speed up the code that would require major re-writing? What are 1 or 2 major changes I could make so that my code matches what good move generators do? (example: switching to 0x88)

Thanks a lot. Looking forward to your feedback.

[Sesse]

You have three problems:

1. You are using PHP.
2. Your board structure is based on text (e.g. “a1”) instead of primitive values (e.g. 0, 0).
3. You are doing this object-oriented.

Fix those three, and your code will be much, much faster.

[maksimKorzh]

You have to sometimes sacrifice your casual programming habbits and even languages to improve the performance. Rewrite the entire move generator is quite common stuff in chess programming e.g. I'm rewriting from scratch my own engine for the third time.

Solutions, as I see them:

1. If you want to write on PHP - forget about OOP, switch to 0x88, don't use string type to store either board array or move but integer instead. This will imrove the speed a lot.

2. If you want to keep OOP style switch to C++...

People say C is even faster than C++, that's why I personally write in C. But if you want simply to test your skills you can leave everything as is and try to get the most out of the alpha beta search. Reducing the number of nodes makes program extremely faster.

Actually chess programming requires a bit different thinking compare to programs that don't rely on performance. Hope this helps

[AlvaroBegue]

People say C is even faster than C++, that's why I personally write in C.

People say a lot of things, but C is not faster than C++. Anything you can write in C you can write in C++, and the performance will be the same. C++ has additional features and some of those might be slow, especially if misused; but you don't have to use them.

[Sven]

1. If you want to write on PHP - forget about OOP

Why should an object-oriented PHP program be significantly slower than a classical PHP program? I think the speed difference would only be marginal.

, switch to 0x88, don't use string type to store either board array or move but integer instead. This will imrove the speed a lot.

I agree that speed issues might be caused by some string types in the internal board representation. But I think that the general organization of data and the choice of algorithms have a much bigger impact on speed. The 8x8 board setup is probably one of the medium problems so yes, a one-dimensional mailbox representation like 0x88 would certainly help a lot. In my opinion the way how legality checking is done (eliminate_king_in_check_moves()) might be the main troublemaker, though, since it calculates the set of all squares attacked by the opponent once for each move in the move list, and that calculation itself is a move generation.

[Sven]

I ended up using lots of OOP. I created the following classes: ChessRulebook (static), ChessMove, ChessBoard, ChessPiece, ChessSquare.

My very first OO design of a chess program actually included similar classes. Later I found out that modelling pieces and squares as objects slows down the program, so I skipped these in favor of a design where Board and Move are the most basic classes. Keep in mind, though, that the speed gain you get by changing the design that way might be much smaller than the gain you might get by choosing more effective algorithms.

I believe my move generation code to be bug free. I've tested about 20 perfts to depth 2 and everything passes.

However my code is SLOW. VERY SLOW. So slow that I can't perft beyond depth 2.

Here you can see that having a very slow implementation can also have an impact on testing, since you are not able to perform the full perft tests (which require more plies in some cases).

1) What are the best ways to speed up the code without completely redesigning everything? Any easy tweaks I can make? (example: replacing ChessSquare with a string)

Think again about the whole legality checking, see also my other post. Calling the move generator from the opponent's view to check legality of each single move sounds like a bad idea to me. At most you need to make a move, test whether your king is in check, and unmake the move. And testing whether the king is in check can be done much faster than by generating all enemy moves (simply go to all directions from the king square). There are even more clever ways for legal move generation. Many chess engines don't even generate a legal move list but stick to pseudo-legal move generation and only test for legality when a move is actually tried during search.

Calculating the set of squares attacked by the enemy only once outside the loop in function eliminate_king_in_check_moves() might already help.

2) What are the best ways to speed up the code that would require major re-writing? What are 1 or 2 major changes I could make so that my code matches what good move generators do? (example: switching to 0x88)

Rewrite the legality checking

[Aldus]

2)

Convert board[file][rank] to board[square]. It's faster, because every matrix is internally represented as an array, and it's easier to code, because instead of file_offset and rank_offset you only need one offset now, for every direction. Add 2 borders to your matrix, so board[8x8] becomes board [12x12] (actually board[10x12] = board[120] would suffice) and put an illegal piece on each border square. Then, when you generate moves, you no longer need to test if you're outside the board. You only have to test if you hit a piece. You will always hit a piece - friendly, opposite or illegal - in which case you're outside the board.

Therefore, your code for rook moves becomes:

Code: Select all

for (i=1; i<=4; i++) {                      // for each rook direction
  dest = source + rook_offset[i];              // next square on that direction
  while (board[dest] == empty) {              // non-capture move
    AddMove(source,dest);                      // add it to move list
    dest += rook_offset[i];                       // next square on same direction
  }
  if enemy_piece(board[dest])                  // we hit an enemy piece
      AddMove(source,dest);                      // add it to move list
 } 

Depending on how you implement pieces and colors, you could write the test enemy_piece(board[dest]) as an inline bitwise operation or something of that sort. The less functions you call and the less arguments you pass to them, the faster the code.

I think that should be much faster then your approach.

You can find much more info about this topic here: https://www.chessprogramming.org/Board_Representation

[Sesse]

Why should an object-oriented PHP program be significantly slower than a classical PHP program?

Most importantly, because you are generating a ton of objects that need to be garbage collected, which takes significant amounts of time. You are also introducing an abstraction penalty that PHP's rather weak optimizer will have problems getting rid of efficiently.

[Sven]

Why should an object-oriented PHP program be significantly slower than a classical PHP program?

Most importantly, because you are generating a ton of objects that need to be garbage collected, which takes significant amounts of time. You are also introducing an abstraction penalty that PHP's rather weak optimizer will have problems getting rid of efficiently.

By developing in an object-oriented manner, you are not forced to generate "a ton of [small] objects". This is a matter of design and maybe of granularity. Even a design like the one presented here, with Piece and Square objects, can be implemented much more effectively if you deal appropriately with it and do not copy everything whenever you access it. A board instance has 64 Square objects, and there are at most 32 Piece objects. Creating and destroying lots of copies of these instances would in fact introduce a significant performance penalty. Making a move can also be implemented as changing the assocation between a piece and a square.

The PHP program presented here does not always follow that guideline, one counter-example is add_castling_moves_to_moves_list() in ChessRulebook.php which creates lots of new ChessSquare instances each time it is called. That is not necessary and can be done differently. Another example: square_exists_and_not_occupied_by_friendly_piece() which often returns a newly created ChessSquare instance. Instead of this I would provide a way to return a reference to the existing ChessSquare instance that corresponds to the given x/y deltas.

[AdmiralAdama]

Hello all,

Thank you for the awesome feedback. Just wanted to let you know that I am reading all of it and I will implement several of the suggestions.

2. Your board structure is based on text (e.g. “a1”) instead of primitive values (e.g. 0, 0).

I went ahead and replaced constant strings with constant ints wherever I could, and I also added a ChessSquare->get_int() function, and this gave me a speed increase.

Calling the move generator from the opponent's view to check legality of each single move sounds like a bad idea to me. At most you need to make a move, test whether your king is in check, and unmake the move. And testing whether the king is in check can be done much faster than by generating all enemy moves (simply go to all directions from the king square).

This is a great idea. I noticed this slow point myself, but I couldn't think of a better way to do it. You've given me the better way here. I think I'll refactor eliminate_king_in_check_moves() to use a new square_is_threatened() function that fires rays in all directions (and L-shape for knights) to see if an enemy piece of the correct type is on that rank/file. That should be much faster than generating all of the enemy's legal moves for each node in my tree.

The PHP program presented here does not always follow that guideline, one counter-example is add_castling_moves_to_moves_list() in ChessRulebook.php which creates lots of new ChessSquare instances each time it is called. That is not necessary and can be done differently. Another example: square_exists_and_not_occupied_by_friendly_piece() which often returns a newly created ChessSquare instance. Instead of this I would provide a way to return a reference to the existing ChessSquare instance that corresponds to the given x/y deltas.

Another great idea. According to my profiler, during a perft(3), ChessSquare->__construct() is called 59,000 times. By just creating 64 ChessSquares, then always passing by reference, we can slim that down to 64! That should give a significant speed boost.