Which features offer the best return?

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.
lojic
Posts: 65
Joined: Thu Jan 28, 2021 8:50 pm
Full name: Brian Adkins

Re: Which features offer the best return?

Post by lojic » Fri Jan 29, 2021 5:21 pm

mvanthoor wrote:
Fri Jan 29, 2021 4:47 pm
My engine had the same problem. This is easy to fix with a second King PST for the endgame. Just use a PST with a centralized king after the material dwindles below a certain amount of points. ...
I'm pretty new at this, but it doesn't seem like a PST ("piece square table", right?) alone would solve this. Since I'm only searching 6 or 7 ply, it just couldn't see a mate. Why would drawing my king to the center change this? If a checking move was part of the quiescence search (which I don't have yet), then maybe that would do it by searching deep enough.

User avatar
mvanthoor
Posts: 740
Joined: Wed Jul 03, 2019 2:42 pm
Full name: Marcel Vanthoor

Re: Which features offer the best return?

Post by mvanthoor » Fri Jan 29, 2021 6:59 pm

lojic wrote:
Fri Jan 29, 2021 5:21 pm
I'm pretty new at this, but it doesn't seem like a PST ("piece square table", right?) alone would solve this. Since I'm only searching 6 or 7 ply, it just couldn't see a mate. Why would drawing my king to the center change this? If a checking move was part of the quiescence search (which I don't have yet), then maybe that would do it by searching deep enough.
It does work. The reason is that the preferred location of the king changes during the game. In the middle-game, it is at the edge, behind other pieces, so it can be defended. In the late middle-game or early end-game, the king will actively start to play in the game. In the end-game, the king becomes an attacking piece for the stronger side.

What you want to do is something very simple: if your opponent has a bare king you apply the King PST on top of your current PST values.

This PST gives neutral for the center, but a large penalty for being at the edge. The trick is that, when you are going to mate your opponent, your king has to ALSO approach the edge. Therefore, the closer you are to the edge, the bigger the penalty. ("If I go here, closer to the edge, I get a penalty of 20... but then my opponent MUST go THERE, and then HE gets a penalty of 30. So this is good for me.") This will cause the stronger side to drive the bare king to the edge and mate him there.

Rustic's current PST's

This code applies this KING_EDGE table on top of the current evaluation, if one of the sides has a bare king (or less than a pawn's value) on the board:

Code: Select all

    // If one of the sides is down to a bare king, apply the KING_EDGE PSQT
    // to drive that king to the edge and mate it.
    if w_material < PAWN_VALUE || b_material < PAWN_VALUE {
        let w_king_edge = KING_EDGE[board.king_square(Sides::WHITE)] as i16;
        let b_king_edge = KING_EDGE[board.king_square(Sides::BLACK)] as i16;
        value += w_king_edge - b_king_edge;
    }
You can try it. Download and install Rustic, and then set up white with a KQ in the corners, and black with a K in the center. Then have white play. You can even have Rustic play against Stockfish and it will still mate it.
Author of Rustic.
Releases | Code | Docs

User avatar
hgm
Posts: 25824
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Which features offer the best return?

Post by hgm » Fri Jan 29, 2021 7:31 pm

lojic wrote:
Fri Jan 29, 2021 4:29 pm
For simplicity, instead of iterative deepening, I'm fine with just using the maximum depth I can while having it move in a reasonable amount of time i.e. instead of 1, 2, ... , max-depth, I just went straight to max-depth.
But how do you know what max-depth is? In a complex position it could suddenly start thinking for hours, while before the same depth only needed minutes.
The only move ordering I'm doing now is keeping two lists of moves - quiet moves and capture moves, then I examine the capture moves first. This should help with quiescence since I'll already have a list of capture moves.
It is very important you try capture of the opponent's most dangerous (= valuable) piece first. If you don't do that, you will get regularly in positions where both Queens go on 'plunder raids', capturing protected pieces all over the place, while the engine is 'too busy' capturing stuff with the other player's Queen because it wants to try the many things that can capture first. And then it is going to calculate in how many million ways you can do that. While it was all nonsense from the start.
I think I'll start with adding quiescence, then maybe some refinements to the static evaluation, and then transposition tables. I'm looking forward to the opening book functionality a bit later, and I know I'll need something for the end game, because it just flailed around aimlessly when it had king + queen to the opponent's king :) Although, for my initial purposes, if the engine is clearly in a winning position, I'm satisfied for now w/o actually doing the end game mate, but I'm sure I'll add that for completeness later.
You hardly need any depth (like 2 or 3 ply) to force a mate in KQK, if your evaluation knows the following: Kings (and especially bare Kings) are good in the center, and bad in the corner. And the smaller the distance between Kings, the worse that is for the weak side. (And of course that stalemate is a draw.)

KBNK is hard, if the engine doesn't know what is the safe corner, and the opponent does. The mate is much too far away to see, when the bare King is in the safe corner, and the engine will never allow the bare King to escape from there. In Fairy-Max I solved this problem by switching to a special PST which pushes a King out of a corner, to an adjacent one, when a bare King reaches the corner. The idea is that once the King is in a corner where he can be checkmated, the mate should be close enough for the engine to see, and the evaluation would thus not matter, as it would play by mate score. But if there is no mate, he is apparently in the wrong corner, and you'd better try another one. The advantage is that it doesn't have to know what the deadly corner is. (Which could depend on the pieces it has.)

lojic
Posts: 65
Joined: Thu Jan 28, 2021 8:50 pm
Full name: Brian Adkins

Re: Which features offer the best return?

Post by lojic » Fri Jan 29, 2021 8:08 pm

hgm wrote:
Fri Jan 29, 2021 7:31 pm
lojic wrote:
Fri Jan 29, 2021 4:29 pm
For simplicity, instead of iterative deepening, I'm fine with just using the maximum depth I can while having it move in a reasonable amount of time i.e. instead of 1, 2, ... , max-depth, I just went straight to max-depth.
But how do you know what max-depth is? In a complex position it could suddenly start thinking for hours, while before the same depth only needed minutes. ...
By "max-depth" I simply meant a depth that allowed the engine to move quickly enough for my satisfaction. With my first evaluation function, I found that a depth of 7 allowed it to move speedily enough. There was some variance, as you noted, between positions (I presume to the difference in alpha beta pruning), but the average move time was good. I realize this isn't the "proper" way to code it, but iterative deepening was lower on my list.

lojic
Posts: 65
Joined: Thu Jan 28, 2021 8:50 pm
Full name: Brian Adkins

Re: Which features offer the best return?

Post by lojic » Fri Jan 29, 2021 8:11 pm

Let me give a collective "thank you" to everyone who posted suggestions (and to any that might follow). I'll be studying the info provided and plan my next steps. I appreciate the help.

User avatar
emadsen
Posts: 244
Joined: Wed Apr 25, 2012 11:51 pm
Location: Oak Park, IL, USA
Full name: Erik Madsen
Contact:

Re: Which features offer the best return?

Post by emadsen » Sat Jan 30, 2021 7:57 pm

lojic wrote:
Fri Jan 29, 2021 2:08 am
I'm mainly looking for a few more features that will accomplish my goal of being ~ 1,700 - 1,800, or so. In other words, I'm looking for the "best bang for the buck", as my dad says :)
Hi Brian. I've documented the ELO strength increase I measured after adding features to my chess engine. See the table at the bottom of each blog post linked from the above page. Version 2 of my engine is implemented with a "mailbox" board and is released. Version 3 of my engine is implemented with bitboards and is not yet released. Features in the search and evaluation of a chess engine interact in a non-linear manner so you may not observe the same strength increases as I measured, especially if you add the features in a different order than I did.

Good luck with your engine.
My C# chess engine: https://www.madchess.net

User avatar
emadsen
Posts: 244
Joined: Wed Apr 25, 2012 11:51 pm
Location: Oak Park, IL, USA
Full name: Erik Madsen
Contact:

Re: Which features offer the best return?

Post by emadsen » Sat Jan 30, 2021 8:01 pm

My C# chess engine: https://www.madchess.net

lojic
Posts: 65
Joined: Thu Jan 28, 2021 8:50 pm
Full name: Brian Adkins

Re: Which features offer the best return?

Post by lojic » Sat Jan 30, 2021 8:56 pm

emadsen wrote:
Sat Jan 30, 2021 7:57 pm
lojic wrote:
Fri Jan 29, 2021 2:08 am
I'm mainly looking for a few more features that will accomplish my goal of being ~ 1,700 - 1,800, or so. In other words, I'm looking for the "best bang for the buck", as my dad says :)
Hi Brian. I've documented the ELO strength increase I measured after adding features to my chess engine. See the table at the bottom of each blog post linked from the above page. Version 2 of my engine is implemented with a "mailbox" board and is released. Version 3 of my engine is implemented with bitboards and is not yet released. Features in the search and evaluation of a chess engine interact in a non-linear manner so you may not observe the same strength increases as I measured, especially if you add the features in a different order than I did.

Good luck with your engine.
Awesome - I'll check out your info on the strength improvements.

Regarding bitboards, I was just reading some articles today and wondering maybe I should go ahead and bite the bullet and implement bitboards. What was your experience like switching from mailbox to bitboards? While I may want to continue to improve my engine, I'll likely use it more for teaching purposes later (vs. trying to be competitive, given my implementation language), and if so, keeping the 10x12 board may serve that purpose better.

One option is to see how far I can get with the 10x12 board, and then consider switching to bitboards, but the more code I implement that assumes a 10x12 implementation, the harder that will be to change later.

User avatar
mvanthoor
Posts: 740
Joined: Wed Jul 03, 2019 2:42 pm
Full name: Marcel Vanthoor

Re: Which features offer the best return?

Post by mvanthoor » Sat Jan 30, 2021 10:12 pm

emadsen wrote:
Sat Jan 30, 2021 7:57 pm
lojic wrote:
Fri Jan 29, 2021 2:08 am
I'm mainly looking for a few more features that will accomplish my goal of being ~ 1,700 - 1,800, or so. In other words, I'm looking for the "best bang for the buck", as my dad says :)
Hi Brian. I've documented the ELO strength increase I measured after adding features to my chess engine. See the table at the bottom of each blog post linked from the above page. Version 2 of my engine is implemented with a "mailbox" board and is released. Version 3 of my engine is implemented with bitboards and is not yet released. Features in the search and evaluation of a chess engine interact in a non-linear manner so you may not observe the same strength increases as I measured, especially if you add the features in a different order than I did.

Good luck with your engine.
Hi Eric :)

I referred some new engine developers to your site with regard to your strength progression log. I'm going to make use of this myself, now that my first version of Rustic has been released, and I'm going to keep a similar log at https://rustic-chess.org/. I'll start writing some stuff there in the near future.

I like Madchess, and I'll certainly include it in my testing when I reach that level of play. Is there a way to compile the .NET Core version into one executable that runs on top of an installed framework? In that case, I'd do so.

(Euh... not targeted against your engine in particular, but against .NET Core... I think it's junk to have to release a 25 MB ZIP-file containing 30 bazillion files to run the engine.)
Author of Rustic.
Releases | Code | Docs

User avatar
mvanthoor
Posts: 740
Joined: Wed Jul 03, 2019 2:42 pm
Full name: Marcel Vanthoor

Re: Which features offer the best return?

Post by mvanthoor » Sat Jan 30, 2021 10:18 pm

lojic wrote:
Sat Jan 30, 2021 8:56 pm
One option is to see how far I can get with the 10x12 board, and then consider switching to bitboards, but the more code I implement that assumes a 10x12 implementation, the harder that will be to change later.
Personally I switched to bitboards just before implementing perft. I just couldn't stand the thought of having to switch later. For some time, my engine was partly a 10x12 mailbox, and partly bitboard. That's possible, and it works fine. I'm glad I switched.

You -could- implement the board as 10x12, and put an interface on top of it, and run all the other modules through that interface. Then they'd never need to know how the board is implemented. Then you can later implement a bitboard, and run a module partly through the 10x12, and partly through the bitboard version. That will work. The interface will slow the engine down somewhat (because of the dynamic binding and extra function calls needed), and it will require more code. It does facilitate a way to finish your current engine and then switch later.
Author of Rustic.
Releases | Code | Docs

Post Reply