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.
My PHP Chess Move Generator is slow. Help!
Moderators: hgm, Rebel, chrisw
-
- Posts: 3
- Joined: Wed Sep 19, 2018 6:36 am
- Full name: Jeff Lewis
-
- Posts: 300
- Joined: Mon Apr 30, 2018 11:51 pm
Re: My PHP Chess Move Generator is slow. Help!
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.
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.
-
- Posts: 771
- Joined: Sat Sep 08, 2018 5:37 pm
- Location: Ukraine
- Full name: Maksim Korzh
Re: My PHP Chess Move Generator is slow. Help!
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
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
Didactic chess engines:
https://www.chessprogramming.org/Maksim_Korzh
Chess programming YouTube channel:
https://www.youtube.com/channel/UCB9-pr ... KKqDgXhsMQ
https://www.chessprogramming.org/Maksim_Korzh
Chess programming YouTube channel:
https://www.youtube.com/channel/UCB9-pr ... KKqDgXhsMQ
-
- Posts: 931
- Joined: Tue Mar 09, 2010 3:46 pm
- Location: New York
- Full name: Álvaro Begué (RuyDos)
Re: My PHP Chess Move Generator is slow. Help!
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.maksimKorzh wrote: ↑Thu Sep 20, 2018 9:04 am People say C is even faster than C++, that's why I personally write in C.
-
- Posts: 4052
- Joined: Thu May 15, 2008 9:57 pm
- Location: Berlin, Germany
- Full name: Sven Schüle
Re: My PHP Chess Move Generator is slow. Help!
Why should an object-oriented PHP program be significantly slower than a classical PHP program? I think the speed difference would only be marginal.
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.maksimKorzh wrote: ↑Thu Sep 20, 2018 9:04 am , 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.
Sven Schüle (engine author: Jumbo, KnockOut, Surprise)
-
- Posts: 4052
- Joined: Thu May 15, 2008 9:57 pm
- Location: Berlin, Germany
- Full name: Sven Schüle
Re: My PHP Chess Move Generator is slow. Help!
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.AdmiralAdama wrote: ↑Wed Sep 19, 2018 10:55 pm I ended up using lots of OOP. I created the following classes: ChessRulebook (static), ChessMove, ChessBoard, ChessPiece, ChessSquare.
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).AdmiralAdama wrote: ↑Wed Sep 19, 2018 10:55 pm 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.
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.AdmiralAdama wrote: ↑Wed Sep 19, 2018 10:55 pm 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)
Calculating the set of squares attacked by the enemy only once outside the loop in function eliminate_king_in_check_moves() might already help.
Rewrite the legality checkingAdmiralAdama wrote: ↑Wed Sep 19, 2018 10:55 pm 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)
Sven Schüle (engine author: Jumbo, KnockOut, Surprise)
-
- Posts: 27
- Joined: Mon Sep 03, 2018 12:59 pm
- Location: Romania
- Full name: Cristi Ilovan
Re: My PHP Chess Move Generator is slow. Help!
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:
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
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
Last edited by Aldus on Thu Sep 20, 2018 11:14 pm, edited 1 time in total.
-
- Posts: 300
- Joined: Mon Apr 30, 2018 11:51 pm
Re: My PHP Chess Move Generator is slow. Help!
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.
-
- Posts: 4052
- Joined: Thu May 15, 2008 9:57 pm
- Location: Berlin, Germany
- Full name: Sven Schüle
Re: My PHP Chess Move Generator is slow. Help!
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.Sesse wrote: ↑Thu Sep 20, 2018 11:09 pmMost 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.
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.
Sven Schüle (engine author: Jumbo, KnockOut, Surprise)
-
- Posts: 3
- Joined: Wed Sep 19, 2018 6:36 am
- Full name: Jeff Lewis
Re: My PHP Chess Move Generator is slow. Help!
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.
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.
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.Sesse wrote:2. Your board structure is based on text (e.g. “a1”) instead of primitive values (e.g. 0, 0).
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.Sven wrote: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).
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.Sven wrote: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.