Progress on Loki

[niel5946]

Staged move generation done right
Yesterday, I got staged move generation to work for the first time! The previous attempts that I have made, were all centered around the following stages:

1. Hash move, if one is found.
2. Generation and scoring of captures.
3. Good and equal captures.
4. Generation and scoring of quiets.
5. Quiets
6. Bad captures

Although this order seems reasonable enough, I never got it to work, and I think the reason for that is two-fold: 1) The bad captures needs to be identified with SEE which was done at fetch-time, and a failed SEE - resulting in trying a new capture - slowed the engine down greatly. 2) Due to the way I update the move ordering heuristics, I need the entire list of moves searched and that wasn't really possible without doing a lot of deleting and copying during move fetching. This was also a big slowdown.
Now, this time I decided to do something similar to Erik Madsen (MadChess author) with the following stages:

1. Hash move if one is found.
2. Generation and scoring of captures
3. All captures, good and bad.
4. Generation and scoring of quiets.
5. All quiets.

This is not only simpler, but faster and easier to implement. I suppose the speed gain of this method compared to the earlier one relies on bad captures being refuted very quickly. Thus, if the search function is faster at refuting them, than the fetching function is at storing them in a "bad captures list", there will be a speed gain.
I ran an SPRT test on this implementation yesterday, and this was the results (elo0 = 0, elo1 = 10):

Code: Select all

Score of Lokidev vs Loki350: 309 - 232 - 321  [0.545] 862
...      Lokidev playing White: 164 - 105 - 162  [0.568] 431
...      Lokidev playing Black: 145 - 127 - 159  [0.521] 431
...      White vs Black: 291 - 250 - 321  [0.524] 862
Elo difference: 31.1 +/- 18.4, LOS: 100.0 %, DrawRatio: 37.2 %
SPRT: llr 2.98 (101.2%), lbound -2.94, ubound 2.94 - H1 was accepted

Which is not at all bad
The implementation can be found in movestager.h and movestager.cpp in the staged-move-generation branch of Loki's repository. In the future these files will of course be in the master branch.
The only thing I need to do before merging this into master is to clean up my search_root method. I would like to add a derived class of MoveStager called RootMoveStager which will work exactly as search_root does at the moment. The only reason for this is the easier maintainability from not having two entirely different move ordering implementations.

The future of Loki
As a last thing, I feel like I should mention what Loki's future holds... I just graduated high-school in June (celebrations of this is also the reason I haven't worked much on Loki the last weeks) and because of that, I will have to start working. This in turn means that I probably won't have as much time for developing Loki as I have had previously Although it is exciting to not be in school anymore, it really saddens me that I can't work as much on Loki as I used to. Chess engine development has really become addicting
But fear not, despite of slower progress, Loki 4.0 will be released some day; And it will be a lot stronger than version 3.5

[amanjpro]

Staged move generation done right
Yesterday, I got staged move generation to work for the first time! The previous attempts that I have made, were all centered around the following stages:

1. Hash move, if one is found.
2. Generation and scoring of captures.
3. Good and equal captures.
4. Generation and scoring of quiets.
5. Quiets
6. Bad captures

Although this order seems reasonable enough, I never got it to work, and I think the reason for that is two-fold: 1) The bad captures needs to be identified with SEE which was done at fetch-time, and a failed SEE - resulting in trying a new capture - slowed the engine down greatly. 2) Due to the way I update the move ordering heuristics, I need the entire list of moves searched and that wasn't really possible without doing a lot of deleting and copying during move fetching. This was also a big slowdown.
Now, this time I decided to do something similar to Erik Madsen (MadChess author) with the following stages:

1. Hash move if one is found.
2. Generation and scoring of captures
3. All captures, good and bad.
4. Generation and scoring of quiets.
5. All quiets.

This is not only simpler, but faster and easier to implement. I suppose the speed gain of this method compared to the earlier one relies on bad captures being refuted very quickly. Thus, if the search function is faster at refuting them, than the fetching function is at storing them in a "bad captures list", there will be a speed gain.
I ran an SPRT test on this implementation yesterday, and this was the results (elo0 = 0, elo1 = 10):

Code: Select all

Score of Lokidev vs Loki350: 309 - 232 - 321  [0.545] 862
...      Lokidev playing White: 164 - 105 - 162  [0.568] 431
...      Lokidev playing Black: 145 - 127 - 159  [0.521] 431
...      White vs Black: 291 - 250 - 321  [0.524] 862
Elo difference: 31.1 +/- 18.4, LOS: 100.0 %, DrawRatio: 37.2 %
SPRT: llr 2.98 (101.2%), lbound -2.94, ubound 2.94 - H1 was accepted

Which is not at all bad
The implementation can be found in movestager.h and movestager.cpp in the staged-move-generation branch of Loki's repository. In the future these files will of course be in the master branch.
The only thing I need to do before merging this into master is to clean up my search_root method. I would like to add a derived class of MoveStager called RootMoveStager which will work exactly as search_root does at the moment. The only reason for this is the easier maintainability from not having two entirely different move ordering implementations.

The future of Loki
As a last thing, I feel like I should mention what Loki's future holds... I just graduated high-school in June (celebrations of this is also the reason I haven't worked much on Loki the last weeks) and because of that, I will have to start working. This in turn means that I probably won't have as much time for developing Loki as I have had previously Although it is exciting to not be in school anymore, it really saddens me that I can't work as much on Loki as I used to. Chess engine development has really become addicting
But fear not, despite of slower progress, Loki 4.0 will be released some day; And it will be a lot stronger than version 3.5

Good to see you around
and congrats for your graduation, I am so happy for you

Loki is currently competing in ZaTour, and I believe it needs a bit of performance boost, looking forwrad to Loki 4

[mvanthoor]

The future of Loki
As a last thing, I feel like I should mention what Loki's future holds... I just graduated high-school in June (celebrations of this is also the reason I haven't worked much on Loki the last weeks) and because of that, I will have to start working. This in turn means that I probably won't have as much time for developing Loki as I have had previously Although it is exciting to not be in school anymore, it really saddens me that I can't work as much on Loki as I used to. Chess engine development has really become addicting
But fear not, despite of slower progress, Loki 4.0 will be released some day; And it will be a lot stronger than version 3.5

Good luck, and thanks for the update.

I've been in the workforce for about 15 years now (keep repeating: "I'm not old, I'm not old, still about 27 years to go..."). The problem with work is that there's so much stuff to do and learn outside of work.

I always say I should have been born 20 years earlier. It would have been better:
- I would have been in my 20's in the 80's
- If I'd known stuff about computers back then I could have become rich (without doing it through social media)
- Lots of software still wasn't written back then, so there was lots of research (on a level I could actually understand)
- I would have been 20 years closer to retirement

[emadsen]

Now, this time I decided to do something similar to Erik Madsen (MadChess author) with the following stages:

1. Hash move if one is found.
2. Generation and scoring of captures
3. All captures, good and bad.
4. Generation and scoring of quiets.
5. All quiets.

This is not only simpler, but faster and easier to implement... Score of Lokidev vs Loki350: 309 - 232 - 321 [0.545] 862

I just graduated high-school in June (celebrations of this is also the reason I haven't worked much on Loki the last weeks) and because of that, I will have to start working.

I'm glad you found some ELO in staged move generation. You measured a gain of 31 ELO. That roughly aligns with the 39 ELO I measured in MadChess.

Congrats Neil on graduating high school! I graduated HS 28 years ago. Eh, I still feel young. Ran 12 miles this morning in the heat and humidity... Where are you located in Denmark, if you don't mind me asking? My father was born in Aarhus. I've visited Denmark a few times over the past 20 years. Beautiful country with nice people. I like the combination of Medieval history and hyper-modern design. Flat paving bricks recently placed in the hundreds year old cobblestone in Copenhagen to facilitate smooth passage of baby strollers is a good illustration of old and new living in harmony.

Yes, work takes time from your week. But it also increases your professional skills and provides a certain level of quality-of-life, so to speak. There's still time for relationships and hobbies. Best of luck in the adventures that await you.

[niel5946]

Loki is currently competing in ZaTour, and I believe it needs a bit of performance boost, looking forwrad to Loki 4

I have been checking in on how Loki has been doing in ZaTour occasionally, and I agree. I am actually considering releasing Loki 4.0 with all the new features except the neural network because of this. I believe that a working neural network evaluation will be hard to accomplish for version 4.0 because of two reasons: 1) It will take a lot of time to get right, generate proper training data and train properly. And 2) Perhaps the strength increase will actually be a little too large. What I mean by that is that I would rather have a 100 elo increase from 3.5 to 4.0 and then a 200-300 point increase from 4.0 to 5.0, instead of a 300-400 point increase directly from 4.0 to 5.0...
I don't know yet, but postponing the neural network inclusion is definitely a consideration at the moment.

I always say I should have been born 20 years earlier. It would have been better:
- I would have been in my 20's in the 80's
- If I'd known stuff about computers back then I could have become rich (without doing it through social media)
- Lots of software still wasn't written back then, so there was lots of research (on a level I could actually understand)
- I would have been 20 years closer to retirement

I don't know enough about computer science in the 80's to say whether I agree or not, but I do understand your 3rd point: As a field grows and becomes more specialized it can be hard to feel like you have an understanding of it entirely. A similar example could be physics: In the early 20th century, Einstein worked on both quantum physics and relativity, whereas it is hard to master (enough to get a big breakthrough) both subjects in today's physics. I think this tendency is both good and bad since it on one hand gives us a bigger understanding of the subject, but on the other hand, it requires lots more teamwork and trust in each other's results.

Congrats Neil on graduating high school! I graduated HS 28 years ago. Eh, I still feel young. Ran 12 miles this morning in the heat and humidity... Where are you located in Denmark, if you don't mind me asking? My father was born in Aarhus. I've visited Denmark a few times over the past 20 years. Beautiful country with nice people. I like the combination of Medieval history and hyper-modern design. Flat paving bricks recently placed in the hundreds year old cobblestone in Copenhagen to facilitate smooth passage of baby strollers is a good illustration of old and new living in harmony.

I don't even know if I could manage 4 miles, so congrats on that
I am from Copenhagen, and you're right. I love the way that Copenhagen is a modern city while not being covered in skyscrapers with glass facades. I've only visited Aarhus a few times, but it's pretty much the same there i think (although Copenhagen doesn't have a "The Old Town"). It's funny because I actually thought there had to be at least something Scandinavian when I saw your name (especially Erik with a k )

Yes, work takes time from your week. But it also increases your professional skills and provides a certain level of quality-of-life, so to speak. There's still time for relationships and hobbies. Best of luck in the adventures that await you.

Thank you very much

[niel5946]

Attempts at PSQT tuning
Over the last couple of days, I have been browsing the forum looking for new ideas to try. One of the threads that caught my eye was the one by Ed Schröder, Just an untested idea, and it made me think about my own piece-square tables. So before trying to tune them with history scores, I wanted to squeeze a little more elo out of Texel tuning.
Therefore, I began tuning them on a new, bigger dataset (~3.2M positions) and the results looked promising. The error went down a lot, so one would think that the new tables had a fair chance of gaining some elo over the old ones... But they failed miserably

The reason for this is that I didn't think about checking whether or not my data contained positions with captures, which it did. Now I'll have to write a method to resolve those positions with quiescence

Such kinds of stupid mistakes will hopefully make me think twice the next time I want to tune my eval

[niel5946]

Loki 4.0 is finally nearing it's release
As I have mentioned earlier in this thread, I have been contemplating whether or not to postpone the neural network evaluation function, and I have made my decision: It will, sadly, not be available until version 5.0.. This is primarily because of the massive amounts of time it takes to develop, which doesn't seem feasible since I want to release Loki 4.0 rather soon. The neural network library, I have written, will however be available in the source code of Loki 4.0, but it won't be used anywhere in the engine.

My final list of changes between Loki 3.5 and Loki 4.0 will be the following:

1. Add staged move generation (gains ~20-30 elo)
2. Make the transposition table thread-safe for 32-bit builds (has been done, but no elo change is expected for single-threaded use).
3. Fix a bug where Loki freezes after deep searches with multiple threads running (has also been fixed now).
4. Add late move reductions. These have been added, but I need to run a final test between this and master.
5. Add late move pruning.
6. Add an evaluation hash table. This has been added, but there are some memory-corruption bugs that need to be sorted out before merging.
7. Re-tune the evaluation function on a bigger dataset.
8. Merge the neural branch into master (what I described above).
9. Test - and potentially re-add - disabled search features. These include verified null move pruning, IID, Delta pruning and futility pruning in quiescence.
10. A little bit of code cleanup.

This, in comparison to the old list, seems more feasible to accomplish in the near future. My biggest problem with Loki 4.0 is the disappointment of not getting the neural network evaluation... But hey, at least it's ready for Loki 5
And speaking of Loki 5, this is my current ideas:

1. Incorporate the neural network evaluation and train a network.
2. Add MultiPV for analysis.
3. Better time management.
4. Test new pruning methods or other search features.

All in all, I am happy with the new goal for Loki 4.0, even though an NN would've been nice

[CMCanavessi]

Does Loki play FRC?

[niel5946]

Does Loki play FRC?

No, not at the moment, but now that you mention it, Chess960 would be a nice addition

[niel5946]

The great refactor
Hello everyone
I know it has been some time since I was active on this forum, but I thought that I would give you all a little update on how Loki is doing. I have been very preoccupied with my new job recently, and have therefore not worked much on chess programming, but now I feel a renewed motivation to give Loki a little makeover before making it stronger.
I have decided to do a complete refactoring of Loki due to the following reasons:

• I have learned a lot (C#, C++ and general programming knowledge) from my job, and I therefore think I am a better programmer now than before. Therefore, a refactoring of Loki would be a way of "proving" this to myself.
• Even though I would not call Loki a derivative of other engines, I feel that it's too close to be one. For one, the structure of Loki's code is not really my preferred way of writing/designing C++ applications - it has some times felt like I was coding C and not C++. Secondly, some algorithms has been implemented with great inspiration from other engines (magic bitboards is the most obvious example of this), and I would like to understand these better and write my own implementations.
• There are probably a lot of subtle bugs and bottlenecks, which I would like to remove. I just saw in another thread, that someone suspects Loki of playing illegal moves, which is of course a pretty significant bug, that I should fix.

This means that my goal of the refactoring is the following:

• Write more object-oriented code and remove all global variables that are not constexpr. Additionally, more safety should be added by strongly preferring smart pointers instead of raw pointers.
• Fix bugs that I find along the way.
• Make the code more manageable by writing it in my own style.

I haven't given the potential elo gain/loss of this refactoring any thought, but I would like to think that any losses will pay off in the long term by making Loki more bug-free and easier to work on.
Lastly, as I mentioned in the start, I spend a lot of time working, so this project might take some time. But I will not quit development of Loki in the near future!