Bitboard CHESS ENGINE in C: applying MOVE ORDERING to sort captures

Hey what's up guys, Code Monkey King's here. In this video we gonna apply our sort moves function within a search to minimize the number of traversed nodes significantly.
SOURCE CODE:
github.com/mak...

[@lanceswenor6528]

This move ordering is wonderful, it definitely makes a big difference.

[@chessprogramming591]

Yup, and it's not even the most optimized way of sorting moves. If moves were scored within a move generator and a single move had a corresponding score than we could sort moves within the loop over the moves - it should give the same savings but at the same time it should work faster because we're not wasting time to order all moves every time, but instead ordering only current and next move. That's how move ordering is done in most of engines. The reason why I did it like so is for didactic purposes and clarity so that move ordering becomes totally modular and we can add/remove it without touching move generator code.

[@ani-dz7wq]

I’m using a 2d array board implementation and using piece objects instead of bit boards and my current engine with move ordering and alphabets pruning takes 1-3 seconds to make the first move on depth 3, im not sure why this is but i’m hoping you have any idea of how i can improve this?

[@chessprogramming591]

Your data structures are too slow. In chess programming people usually sacrifice good programming practices for the sake of performance. Try 1d array and encode pieces as integers - you'll get a much faster move generator. I have an entire playlist on that.

[@willm9886]

Hi, hope you are doing well. Is it fine to use other ways to sort as long as it gives the same level of performance boost? Or will it clash with some concept from a future video?

[@chessprogramming591]

Well, it depends on your implementation.
Generally this series is designed to be as easy to understand and follow as possible and a whole lot of things can be improved a lot either. I suggest following as is and then go for improvements. Generally code is somewhat modular but just changing something on the go might lead to complicated hard to track bugs in future.

[@willm9886]

@@chessprogramming591 Ok, got it. I was using qsort from stdlib and it gave me different numbers but still showed around the same level of reduction in nodes. I'll stick to the given code for now and change it later I guess. Thanks for the prompt reply!

[@sourashismondal5060]

Awesome optimization :)

[@qkzk]

Hey there !
I've found why I kept having different results from you.
I used python native list.sort instead of your custom sort. Since python is slow enough already I thought this might help a bit...
Obviously Python sort isn't "in place" and move with score 0 ends at different places.
It changes the evaluation and produces a different number of traversed nodes.
I hope it's the last bug :)
Thanks again for the support

[@chessprogramming591]

Good job!

[@qkzk]

@@chessprogramming591 I decided to move back from video 70+ to this video and validate your numbers step by step. I still don't know why I was having such strange results but it's working atm ! Whis me luck ;)

[@chessprogramming591]

@@qkzk Oh! Great! Good luck! I don't know whether you've implemented null move pruning already but if you did it's quite helpful to avoid making null moves several times in the row. In BBC I do several null moves in the row and it's still ok, but that's better to be avoided, but in that case you'll definitely going to be having different node counts. Actually for every search feature it's a good idea to add them one by one and run test games after like you have a version with say razoring and the one without and then you play 10 games on ultra fast time control. The new version at least shouldn't be loosing all of the time (which happens quite often). For search optimization it's good to have a look at Crafty's source code. But anyway it all depends on goals)

[@kama2106]

The NPS dropped by like 40% but it is still beautiful

[@kama2106]

I added a very basic time manager and now my version of BBC can somewhat hold up fighting with bottom of CCRL list (loses in 50+ moves) - engines with PVs, Iterative deepening etc. That s kinda nice. As I watch BBCs games right now I can say it loves 1 thing. Pinning random stuff.

[@chessprogramming591]

@@kama2106 writing a chess engine is easy, tuning the parametrs is hard, debuggimg is insane.