Progress on Loki

Discussion of chess software programming and technical issues.

Moderators: hgm, Dann Corbit, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Post Reply
niel5946
Posts: 159
Joined: Thu Nov 26, 2020 9:06 am
Full name: Niels Abildskov

Re: Progress on Loki

Post by niel5946 » Tue May 04, 2021 6:22 pm

mvanthoor wrote:
Tue May 04, 2021 6:19 pm
niel5946 wrote:
Tue May 04, 2021 6:07 pm
Update on earlier:
I have now completed two points from the above post. Namely:
  1. Reworked UCI-implementation. The UCI-implementation has been merged into master and seems to work fine. It loses in very short time controls (i.e. 1+0.1s), but seems to be good and stable otherwise.
  2. Join OpenBench. Thanks to Jay Honnold, who has generously let me join his OpenBench server, I am now doing proper testing.
On top of this, I am now using this OpenBench testing to test my LMR implementation properly. After these tests, I will try to make some improvements and then move on to LMP.

All in all, good progress in one day :D
Certainly good progress :)

I've been re-testing my current two versions of the engine (didn't save the games in the previous tests). Everything seems fine, so somewhere in the coming two weeks I'll implement the next feature.

Couldn't you join the server on http://chess.grantnet.us/, or run your own instance?
Yes, I could, but until today I didn't have the slightest idea how OpenBench worked, and Jay offered to let me join his server, with his assistance.
Author of Loki, a C++ work in progress.
Code | Releases | Progress Log |

amanjpro
Posts: 563
Joined: Sat Mar 13, 2021 12:47 am
Full name: Amanj Sherwany
Contact:

Re: Progress on Loki

Post by amanjpro » Tue May 04, 2021 8:33 pm

niel5946 wrote:
Tue May 04, 2021 6:18 am
amanjpro wrote:
Mon May 03, 2021 6:26 pm
Hello Niels,

I am working on Texel tuning for Zahak, currently playing a match between two versions of the engine with very short time control (inf/1+0.08), which means almost all the moves are 5-6 plies deep only. Which makes me worried that their eval might not reflect the actual eval of the position (given the shallow search).

What did you do for the tuning positions? did you use someone else's games, or your engine's with longer time controls?
I used another set of FEN's with game results appended. That seemed like the best idea for two reasons:
1) The positions and their results would probably be more reliable considering that my eval hadn't been tuned beforehand and had rather inaccurate values.
2) It saved time while getting the tuner to work. Before beginning to create my own training sets, I was more focused on just getting a working gradient descent.
Both of these however, aren't needed any more. A goal for version 4.0 is that I create my own framework for generating tuning positions. These positions will be generated with very short time controls too (something like the 1+0.08 you're referring to).

Regarding your question in particular, I am not sure what you are using the self-play games for. Are you using it to generate test positions or to tune your eval?
  • In the first case, I would go for someone else's tuning positions until I was sure the tuner was working correctly. The depth isn't really important here if you're using the same version of the engine. This is because each side would be equally strong and thus equally impaired by the low depths. As long as you make sure to filter out positions with very large scores (like > 600cp or < -600cp) and resolve the captures, I think it'll be fine. This is because large scores are usually caused by tactics while captures lead to many tactics.
  • In the second case, you don't need that. You just need to fit the evaluation function to a kind of winning probability function and then take the squared errors of that compared to each game result. Then you can do gradient descent with that.
Thanks for the detailed answer. I ended up using some ready EPDs + 500K of my own engine, totalling 8M positions to tune ~600 parameters. Probably too few positions, but they are all quiet positions, and I can only improve on that. Texel tuning is currently running, and hopefully will be done by tomorrow. I only hope that I don't have too many bugs in my EPD generation or in the tuning code itself. I will know soon, hopefully. I did the easy but slow Texel implementation with local optimization, which for my simple brain is the right complexity :D

I will also try to join the open-bench, next. I think my engine is strong enough to provide some value, as well as benefit from other engines.

niel5946
Posts: 159
Joined: Thu Nov 26, 2020 9:06 am
Full name: Niels Abildskov

Re: Progress on Loki

Post by niel5946 » Wed May 05, 2021 8:25 am

amanjpro wrote:
Tue May 04, 2021 8:33 pm
I ended up using some ready EPDs + 500K of my own engine, totalling 8M positions to tune ~600 parameters. Probably too few positions, but they are all quiet positions, and I can only improve on that.
Actually, when I just started tuning the evaluation, I only used 725k positions, which gave around 100 elo. I have gotten a set of 30M (i think that's the number) now, but when just starting out with tuning, a low number of positions seems to be fine. This is because the error is so big, that these few positions will pick it up. Later on though, the error in the evaluation will be more subtle, requiring bigger tuning sets.
amanjpro wrote:
Tue May 04, 2021 8:33 pm
I did the easy but slow Texel implementation with local optimization, which for my simple brain is the right complexity :D
That is also a good idea in the beginning! I chose to be risky and start out with SPSA, which could have ended in a total mess! Thankfully it didn't though :D
Although this local optimization is easiest to implement and works in a lot of cases, there are two things you should be aware of:
  1. As the name suggests, it is local. This means that the objective function can very well (and often does) end up settling down in a local minimum. This is still an improvement, but it could be better.
  2. The time it takes is unneccesarily long. As you know, local optimization measures the objective function for every parameter, in every iteration, which is very time consuming. This is especially true when using larger data-sets.
Stochastic gradient descent will usually solve both of these problems:
  1. It uses random perturbations, which are usually larger than 1, in order to explore the space while also measuring the objective function. This has the effect that it usually finds either global minima or very strong local ones. When it does find a minimum, it won't be able to recognize it itself like local optimization does, but this isn't a problem since it'll just hover around that minimum.
  2. It only measures the objective function twice in every iteration, which means that tuning 6000 parameters will take the same time as tuning only 1. This results in a very significant speedup. It does lose some accuracy though, since a perturbation of one parameter will affect another one, but this usually isn't a very big issue.
Author of Loki, a C++ work in progress.
Code | Releases | Progress Log |

niel5946
Posts: 159
Joined: Thu Nov 26, 2020 9:06 am
Full name: Niels Abildskov

Re: Progress on Loki

Post by niel5946 » Wed May 05, 2021 11:32 am

Loki has a new look!
While being bored in my online physics class, I decided to begin working on a logo and icon for Loki. The latter will somehow be added to the output exectuable when building Loki.

The logo:
Image

The icon:
Image

I just need to find a way for the makefile to include this as the executable icon, but then it should be good to go :D

EDIT: Apparently, the images won't show up, so here's the links:
Logo: https://github.com/BimmerBass/Loki/blob/master/Logo.png
Icon: https://github.com/BimmerBass/Loki/blob/master/Icon.png

Note, I have intentionally made the images very large because it is easier to scale down than up :)
Author of Loki, a C++ work in progress.
Code | Releases | Progress Log |

Ras
Posts: 2036
Joined: Tue Aug 30, 2016 6:19 pm
Full name: Rasmus Althoff
Contact:

Re: Progress on Loki

Post by Ras » Wed May 05, 2021 5:09 pm

niel5946 wrote:
Wed May 05, 2021 11:32 am
I just need to find a way for the makefile to include this as the executable icon, but then it should be good to go :D
You could have a look at my releases. In source/application-uci/, check out the combo of the .ico file, the .rc file (with some more useful info to put into the exe), and the win.bat file how this fits together.
Rasmus Althoff
https://www.ct800.net

niel5946
Posts: 159
Joined: Thu Nov 26, 2020 9:06 am
Full name: Niels Abildskov

Re: Progress on Loki

Post by niel5946 » Fri May 07, 2021 10:49 am

Ras wrote:
Wed May 05, 2021 5:09 pm
niel5946 wrote:
Wed May 05, 2021 11:32 am
I just need to find a way for the makefile to include this as the executable icon, but then it should be good to go :D
You could have a look at my releases. In source/application-uci/, check out the combo of the .ico file, the .rc file (with some more useful info to put into the exe), and the win.bat file how this fits together.
I will have a look at it, thanks :)

Regarding the win.bat file: Does the inclusion of a batch file make the addition of an icon to the .exe restricted to windows?
Author of Loki, a C++ work in progress.
Code | Releases | Progress Log |

Ras
Posts: 2036
Joined: Tue Aug 30, 2016 6:19 pm
Full name: Rasmus Althoff
Contact:

Re: Progress on Loki

Post by Ras » Fri May 07, 2021 12:28 pm

niel5946 wrote:
Fri May 07, 2021 10:49 am
Regarding the win.bat file: Does the inclusion of a batch file make the addition of an icon to the .exe restricted to windows?
No - I actually build on Linux these days and use the make_ct800_win.sh script instead. The MingW cross compiler suite and its dependencies need to be installed, but that should be available in the package manager.
Rasmus Althoff
https://www.ct800.net

niel5946
Posts: 159
Joined: Thu Nov 26, 2020 9:06 am
Full name: Niels Abildskov

Re: Progress on Loki

Post by niel5946 » Sun May 09, 2021 6:50 pm

Late move reductions progress
After I joined the OpenBench SPRT testing framework, I have been testing all LMR features in Loki. Sadly, a lot of them turned out to not work, but I will perhaps try to re-add them later (hence why they're commented out in the repo).
My current LMR implementation is the following:

Code: Select all

// Step 13A. Late move reductions (~111 elo). If we haven't beaten beta yet, we're probably in an ALL-node,
//	so we'll reduce the search depth and do a full-depth re-search if the score is (surprisingly) above alpha.
// NOTE: All elo measurements below are from self-play. They are used to give an image of which features give the best returns, but they
//	shouldn't be taken literally. Their sum is bigger than the real elo gain of LMR.
if (moves_searched >= lmr_limit && depth > lmr_depth && !is_tactical && !is_pv && !root_node && extensions == 0) {
	// Look up the logarithmic base reduction. (~28 elo)
	int R = late_move_reduction(depth, moves_searched);
					
	// Increase reduction for moves with history < 0 
	if (ss->stats.history[(ss->pos->side_to_move == WHITE) ? BLACK : WHITE][fromSq][toSq] < 0) {
		R += 1;
	}
					
	// Increase reduction for captures with SEE < 0. Decrease otherwise (~12 elo).
	if (capture) {
		if (moves[m]->score < 0) {
			R += 1;
		}
		else {
			R -= 2;
		}
	}

	int d = std::max(1, std::min(depth - 1, depth - 1 - R));

	score = -alphabeta(ss, d, -(alpha + 1), -alpha, true, &line);
}
Note, the 111 elo at the top is self-play.
I want to try the following features before moving on to LMP:
  1. Make the conditions for reducing more relaxed. Perhaps allow checking moves or moves out of checks to be reduced if they meet certain criteria.
  2. Increasing reduction if our static eval isn't improving.
  3. The TT-probe trick I tried before. If the transposition table returned an entry indicating an ALL-node, increase the reduction. This should only be done if the depth of the tt-entry is close to the depth we're searching the position at though.
  4. A more aggressive futility pruning idea. If our static eval is below alpha by a futility margin, increase the reduction.
  5. Allow reductions of PV nodes.
Note about the new evaluation feature: I have begun working on the earlier mentioned "coordination" term in the evaluation function. I decided to scale down the term's score based on how closed the position is. This "closedness" function is the following:

Code: Select all

		int closedness(const GameState_t* pos, Evaluation& eval) {

			int score = 0;

			// Step 1. Give two points for each pawn on the board
			score += 2 * countBits(pos->pieceBBS[PAWN][WHITE] | pos->pieceBBS[PAWN][BLACK]);

			// Step 2. Give 32 points for blocked E and/or D pawns, and half of that for blocked C and F pawns
			// Note: We just use White's blocked pawn count here since it is arbitrary which side to use.
			score += 32 * countBits(eval.blocked_pawns[WHITE] & (BBS::FileMasks8[FILE_D] | BBS::FileMasks8[FILE_E]));
			score += 16 * countBits(eval.blocked_pawns[WHITE] & (BBS::FileMasks8[FILE_C] | BBS::FileMasks8[FILE_F]));

			// Step 3. Give four points for all other blocked pawns
			score += 4 * countBits(eval.blocked_pawns[WHITE] & ~(BBS::FileMasks8[FILE_C] | BBS::FileMasks8[FILE_D] | BBS::FileMasks8[FILE_E] | BBS::FileMasks8[FILE_F]));


			// Step 4. Closed positions have very few possible pawn breaks, so score accordingly.
			// Note: Here, a pawn break is defined as a move of a pawn that will attack a blocked enemy pawn.

			// Step 4A. Define all legal pawn pushes.
			Bitboard white_pushes = shift<NORTH>(pos->pieceBBS[PAWN][WHITE]) & ~(pos->all_pieces[WHITE] | pos->all_pieces[BLACK]);
			Bitboard black_pushes = shift<SOUTH>(pos->pieceBBS[PAWN][BLACK]) & ~(pos->all_pieces[WHITE] | pos->all_pieces[BLACK]);

			white_pushes |= shift<NORTH>(shift<NORTH>(pos->pieceBBS[PAWN][WHITE] & BBS::RankMasks8[RANK_2]) & ~(pos->all_pieces[WHITE] | pos->all_pieces[BLACK])) &
				~(pos->all_pieces[WHITE] | pos->all_pieces[BLACK]);
			black_pushes |= shift<SOUTH>(shift<SOUTH>(pos->pieceBBS[PAWN][BLACK] & BBS::RankMasks8[RANK_7]) & ~(pos->all_pieces[WHITE] | pos->all_pieces[BLACK])) &
				~(pos->all_pieces[WHITE] | pos->all_pieces[BLACK]);

			// Step 4B. Now count the breaks as amount of pawn moves that attack enemy blocked pawns
			int white_breaks = countBits((shift<NORTHEAST>(white_pushes) | shift<NORTHWEST>(white_pushes)) & eval.blocked_pawns[BLACK]);
			int black_breaks = countBits((shift<SOUTHEAST>(black_pushes) | shift<SOUTHWEST>(black_pushes)) & eval.blocked_pawns[WHITE]);

			// Step 4C. Increase the score depending on the reciprocal of the amount of pawn breaks.
			score += 112 / (white_breaks + black_breaks);

			// Step 5. Return the closedness score and make sure it is between 1 and 256
			return std::max(0, std::min(score, 256));
		}
Which just analyzes the pawn structure and increments a "closedness"-score based on for example the amount of blocked pawns, the amount of pawn breaks possible etc..
Additionally, I added a bishop coordination term which just rewards having both bishops on the same "quadrant". A quadrant is defined as either the queen side or the king side, on our own half of the board. The reason for this is that two bishops in the same corner usually coordinates really well since they control a lot of squares together. I think that I will modify this to give another bonus if they are on the same quadrant, on the other side of the board than the opponent king.

One last point: I am planning on releasing Loki 3.5 which is OpenBench compatible and has a new, better UCI-implementation. I am just testing it to make sure it doesn't lose on time anymore.

I am hoping that all this work will give Loki 4.0 a strength gain similar to the one Loki 3.0 experienced :D
Author of Loki, a C++ work in progress.
Code | Releases | Progress Log |

niel5946
Posts: 159
Joined: Thu Nov 26, 2020 9:06 am
Full name: Niels Abildskov

Re: Progress on Loki

Post by niel5946 » Mon May 10, 2021 2:01 pm

New release! :D

I have just released Loki 3.5.0 which has, as mentioned earlier in this thread, a new and better UCI protocol handling. Apart from this two strength related changes has been made.

Firstly, a bug where there would be duplicate killers at the same ply has been fixed, which should hopefully increase move ordering. Secondly, I have tested and re-added aspiration windows which gave around 10 self-play elo points.
Considering self-play elo is usually bigger than real elo gain, this version isn't expected to be significantly stronger than the latter. The real reason I'm releasing Loki 3.5.0 is because the old UCI implementation was unstable on linux, which needed to be fixed in order to join OpenBench.

Release: https://github.com/BimmerBass/Loki/releases/tag/v3.5.0

Now I can hopefully get on to making Loki stronger for version 4.0.0 :D
Author of Loki, a C++ work in progress.
Code | Releases | Progress Log |

amanjpro
Posts: 563
Joined: Sat Mar 13, 2021 12:47 am
Full name: Amanj Sherwany
Contact:

Re: Progress on Loki

Post by amanjpro » Mon May 10, 2021 2:51 pm

niel5946 wrote:
Mon May 10, 2021 2:01 pm
New release! :D

I have just released Loki 3.5.0 which has, as mentioned earlier in this thread, a new and better UCI protocol handling. Apart from this two strength related changes has been made.

Firstly, a bug where there would be duplicate killers at the same ply has been fixed, which should hopefully increase move ordering. Secondly, I have tested and re-added aspiration windows which gave around 10 self-play elo points.
Considering self-play elo is usually bigger than real elo gain, this version isn't expected to be significantly stronger than the latter. The real reason I'm releasing Loki 3.5.0 is because the old UCI implementation was unstable on linux, which needed to be fixed in order to join OpenBench.

Release: https://github.com/BimmerBass/Loki/releases/tag/v3.5.0

Now I can hopefully get on to making Loki stronger for version 4.0.0 :D
Congrats for the release :)

Post Reply