Interior Node Recognizer

Code, algorithms, languages, construction...
kongsian
Posts: 3
Joined: Thu Jun 10, 2010 5:53 am
Location: Singapore

Interior Node Recognizer

Post by kongsian » Tue Jun 15, 2010 12:03 am

Hi. Are there any open-source engines which implements interior node recognizers? I have coded mine based on Ernst Heinz paper and am interested in seeing how others do it.

Kong Sian

hyatt
Posts: 1242
Joined: Thu Jun 10, 2010 2:13 am
Real Name: Bob Hyatt (Robert M. Hyatt)
Location: University of Alabama at Birmingham
Contact:

Re: Interior Node Recognizer

Post by hyatt » Tue Jun 15, 2010 12:57 am

kongsian wrote:Hi. Are there any open-source engines which implements interior node recognizers? I have coded mine based on Ernst Heinz paper and am interested in seeing how others do it.

Kong Sian
Almost all do it to a degree. For example, who continues searching once you reach a position with king and minor piece vs lone king? So you recognize that as a draw.

I m not a big fan of the idea overall, as you have to be _extremely accurate or the full-width search will lead to a train wreck rather than the correct final destination. Nothing wrong with catching certain well-known cases if you want. KB and wrong rook pawn vs KB, as one example. But there are not every many easily recognizable cases that occur often enough to affect most games. Others get quite dangerous, such as assuming KQQ vs KQ is a win, for example.

kongsian
Posts: 3
Joined: Thu Jun 10, 2010 5:53 am
Location: Singapore

Re: Interior Node Recognizer

Post by kongsian » Tue Jun 15, 2010 2:54 am

hyatt wrote:
kongsian wrote:Hi. Are there any open-source engines which implements interior node recognizers? I have coded mine based on Ernst Heinz paper and am interested in seeing how others do it.

Kong Sian
Almost all do it to a degree. For example, who continues searching once you reach a position with king and minor piece vs lone king? So you recognize that as a draw.

I m not a big fan of the idea overall, as you have to be _extremely accurate or the full-width search will lead to a train wreck rather than the correct final destination. Nothing wrong with catching certain well-known cases if you want. KB and wrong rook pawn vs KB, as one example. But there are not every many easily recognizable cases that occur often enough to affect most games. Others get quite dangerous, such as assuming KQQ vs KQ is a win, for example.
I'm actually looking at trying to be able to identify cases like K<minor>KP. Without recognizer, this is what my engine sees.

8/3nKp2/8/5k2/5P2/8/8/8 w - - 0 1

Code: Select all

info depth 1 seldepth 2 score cp -100 nodes 3 time 15 pv Ke7xd7 Kf5xf4 
info depth 2 seldepth 2 score cp -100 nodes 15 time 15 pv Ke7xd7 Kf5xf4 
info depth 3 seldepth 4 score cp -100 nodes 50 time 15 pv Ke7xd7 Kf5xf4 Kd7c6 
info depth 4 seldepth 4 score cp -100 nodes 137 time 15 pv Ke7xd7 Kf5xf4 Kd7c6 f7f6 
info depth 5 seldepth 6 score cp -100 nodes 310 time 15 pv Ke7xd7 Kf5xf4 Kd7c6 f7f6 Kc6b5 
info depth 6 seldepth 6 score cp -100 nodes 781 time 16 pv Ke7xd7 Kf5xf4 Kd7c6 f7f6 Kc6b5 f6f5 
info depth 7 seldepth 8 score cp -100 nodes 1554 time 16 pv Ke7xd7 Kf5xf4 Kd7c6 f7f6 Kc6b5 f6f5 Kb5a4 
info depth 8 seldepth 8 score cp -100 nodes 3269 time 17 pv Ke7xd7 Kf5xf4 Kd7c6 f7f6 Kc6b5 f6f5 Kb5a4 Kf4e4 
info depth 9 seldepth 10 score cp -100 nodes 5534 time 17 pv Ke7xd7 Kf5xf4 Kd7c6 f7f6 Kc6b5 f6f5 Kb5a4 Kf4e4 Ka4a3 
info depth 10 seldepth 10 score cp -100 nodes 9534 time 19 pv Ke7xd7 Kf5xf4 Kd7c6 f7f6 Kc6b5 f6f5 Kb5a4 Kf4e4 Ka4a3 f5f4 
info depth 11 seldepth 12 score cp -100 nodes 14423 time 21 pv Ke7xd7 Kf5xf4 Kd7c6 f7f6 Kc6b5 f6f5 Kb5a4 Kf4e4 Ka4a3 f5f4 Ka3a2 
info depth 12 seldepth 12 score cp -100 nodes 22011 time 23 pv Ke7xd7 Kf5xf4 Kd7c6 f7f6 Kc6b5 f6f5 Kb5a4 Kf4e4 Ka4a3 f5f4 Ka3a2 f4f3 
info depth 13 seldepth 15 score cp -100 nodes 33548 time 27 pv Ke7xd7 Kf5xf4 Kd7e7 f7f5 Ke7f6 Kf4e4 Kf6g5 f5f4 Kg5g4 f4f3 Kg4g3 Ke4e3 Kg3h2 
info depth 14 seldepth 16 score cp -100 nodes 44348 time 31 pv Ke7xd7 Kf5xf4 Kd7e7 f7f5 Ke7f6 Kf4e4 Kf6g5 f5f4 Kg5g4 f4f3 Kg4g3 Ke4e3 Kg3h2 f3f2 
info depth 15 seldepth 19 score cp -100 nodes 57888 time 36 pv Ke7xd7 Kf5xf4 Kd7e7 f7f5 Ke7f6 Kf4e4 Kf6g5 f5f4 Kg5g4 f4f3 Kg4g3 Ke4e3 Kg3h2 f3f2 Kh2g2 
info depth 16 seldepth 18 score cp -100 nodes 73276 time 41 pv Ke7xd7 Kf5xf4 Kd7e7 f7f5 Ke7f6 Kf4e4 Kf6g5 f5f4 Kg5g4 f4f3 Kg4g3 Ke4e3 Kg3h2 f3f2 Kh2g2 Ke3e2 
info depth 17 seldepth 19 score cp -975 nodes 86930 time 46 pv Ke7xd7 Kf5xf4 Kd7e7 f7f5 Ke7f6 Kf4e4 Kf6g5 f5f4 Kg5g4 f4f3 Kg4g3 Ke4e3 Kg3h2 f3f2 Kh2g2 Ke3e2 Kg2h1 f2f1q+ Kh1h2 
info depth 17 seldepth 27 score cp -225 nodes 28867418 time 6107 pv Ke7xf7 Nd7c5 Kf7e7 Nc5b3 Ke7d7 Nb3a1 Kd7c6 Na1c2 Kc6b5 Nc2d4+ Kb5a4 Kf5e6 Ka4a3 Nd4b5+ Ka3a2 Ke6f7 Ka2a1 Kf7e7 Ka1b1 
With a recognizer which give KNKP an upper bound of draw score.

Code: Select all

info depth 1 seldepth 2 score cp -100 nodes 3 time 15 pv Ke7xd7 Kf5xf4 
info depth 1 seldepth 2 score cp 0 nodes 5 time 15 pv Ke7xf7 
info depth 2 seldepth 1 score cp 0 nodes 11 time 15 pv Ke7xf7 Kf5xf4 
info depth 3 seldepth 1 score cp 0 nodes 25 time 15 pv Ke7xf7 Kf5xf4 
info depth 4 seldepth 1 score cp 0 nodes 46 time 15 pv Ke7xf7 Kf5xf4 
info depth 4 seldepth 4 score cp 0 nodes 71 time 15 pv Ke7xf7 Kf5xf4 
Certainly more sensible. I guess everyone is now using tablebases instead as a more generic approach. I should probably look at those engines and see how they do it. It should probably be very similar to an interior node recognizer.

Kong Sian

hyatt
Posts: 1242
Joined: Thu Jun 10, 2010 2:13 am
Real Name: Bob Hyatt (Robert M. Hyatt)
Location: University of Alabama at Birmingham
Contact:

Re: Interior Node Recognizer

Post by hyatt » Tue Jun 15, 2010 3:03 am

I deal with that in eval. That way I don't stop when I see the initial position, which can be misleading. I wait until I hit a tip position and then do something similar in my eval. If it sees (for example) KN vs KP or KN vs KPP, etc, it does a normal eval and produces a normal score, but the score is clipped by a "can_win" variable. Near the top of evaluate, I call a function that answers the question can white win? and can black win? If the answer to either is "no" then the score is clipped. If white can't win, the score can never go above zero, but it can go negative if black can win. This has worked well for me over the years where I catch many of the usual cases (KR+minor vs KR is normally a draw, for example, unless the king is trapped on the edge of the board where the winning side may well whip up a mating net that requires sacrificing the rook for the minor to delay, or K + rook pawn + wrong bishop vs K).

I like the idea of dealing with this in the eval, so that the tree is not cut off too quickly and searches as deeply as possible to make sure there are no tactical tricks hiding way out there.

Pawel Koziol
Posts: 20
Joined: Fri Jun 11, 2010 7:19 am
Real Name: Pawel Koziol

Re: Interior Node Recognizer

Post by Pawel Koziol » Tue Jun 15, 2010 8:36 am

if You code KBP vs K with a rook pawn and a Bishop of the wrong color as a draw, be sure to code KRP vs K with the rook pawn as well. Otherwise Your program will look for a "win" establishing a position like that: White: Kc7, Ba7, pa6, Black: Ka8 (last White move being made with a King).

doing the recognition in eval() is much safer. for the start You may code something like:

if (stronger side has only a minor piece and no pawns) return 0;

as You move to more complex cases, however, You *have to* think about all the similar positions. For example, if You code a rule that KQB va KQ is a draw, then You should do something about KQB vs KQP(P), otherwise the engine will think "well, I'm ahead if I don't take that last pawn".

sometimes a good idea is to divide eval score if certain material configuration occurs. In the lats example, the safe way of doing things would probably be

if (stronger side has only QB or QN, no pawns) result /= 8

hyatt
Posts: 1242
Joined: Thu Jun 10, 2010 2:13 am
Real Name: Bob Hyatt (Robert M. Hyatt)
Location: University of Alabama at Birmingham
Contact:

Re: Interior Node Recognizer

Post by hyatt » Tue Jun 15, 2010 3:59 pm

Pawel Koziol wrote:if You code KBP vs K with a rook pawn and a Bishop of the wrong color as a draw, be sure to code KRP vs K with the rook pawn as well. Otherwise Your program will look for a "win" establishing a position like that: White: Kc7, Ba7, pa6, Black: Ka8 (last White move being made with a King).

doing the recognition in eval() is much safer. for the start You may code something like:

if (stronger side has only a minor piece and no pawns) return 0;

as You move to more complex cases, however, You *have to* think about all the similar positions. For example, if You code a rule that KQB va KQ is a draw, then You should do something about KQB vs KQP(P), otherwise the engine will think "well, I'm ahead if I don't take that last pawn".

sometimes a good idea is to divide eval score if certain material configuration occurs. In the lats example, the safe way of doing things would probably be

if (stronger side has only QB or QN, no pawns) result /= 8

Most of that is exactly what I do. I don't really like "outright draw scores" in the eval, it is better to "drag" the scores closer to draw, because if you are not careful, the positions that you call draws (because they are with normal play) can become losses if you play completely stupidly and let your king get walked into a corner where it suddenly falls into a mating net that costs it material or the game. Dividing the score by some constant still keeps a bit of positional judgement going in the final score, while letting the program know that the score is becoming far more drawish if it follows this path (which could be good if it is losing, or bad if it is winning, obviously).

The interior node recognizer approach is a sort of win/lose/draw eval with no knowledge of any kind beside that used in the recognizer itself. For a simple example, KRB vs KR is a draw. But the KRB side can win pretty easily if the KR side plays stupidly and gets stuck on the edge of the board. If you just say "all KRB vs KR positions are drawn" you'd better hope that you don't reach one that is lost and report it as a draw, else you end up losing. You might guess it sounds like I have done this before. :) I have. And got burned badly a few times.

kongsian
Posts: 3
Joined: Thu Jun 10, 2010 5:53 am
Location: Singapore

Re: Interior Node Recognizer

Post by kongsian » Wed Jun 16, 2010 5:03 am

hyatt wrote: The interior node recognizer approach is a sort of win/lose/draw eval with no knowledge of any kind beside that used in the recognizer itself. For a simple example, KRB vs KR is a draw. But the KRB side can win pretty easily if the KR side plays stupidly and gets stuck on the edge of the board. If you just say "all KRB vs KR positions are drawn" you'd better hope that you don't reach one that is lost and report it as a draw, else you end up losing. You might guess it sounds like I have done this before. :) I have. And got burned badly a few times.
Actually that is not quite correct. The interior node recognizer can return bounds as well, not just win/lose/draw. So for KNKP my recognizer returns drawscore as an upperbound for white. The search than proceeds as normal.

Anyway I feel there is a lot of potential with this and will continue to pursue this further. Thanks.

Kong Sian

Pawel Koziol
Posts: 20
Joined: Fri Jun 11, 2010 7:19 am
Real Name: Pawel Koziol

Re: Interior Node Recognizer

Post by Pawel Koziol » Wed Jun 16, 2010 6:10 am

for KNKP my recognizer returns drawscore as an upperbound for white. The search than proceeds as normal.
actually this is a good illustration of dangers inherent to coding interior node recognizers and forgetting about exceptions. There is a KNKP position with a rook pawn, the king of the weaker side in front of it and the king of the stronger side in a horizontal opposition that leads to a forced mate.

zugzwang regards,

pawel

hyatt
Posts: 1242
Joined: Thu Jun 10, 2010 2:13 am
Real Name: Bob Hyatt (Robert M. Hyatt)
Location: University of Alabama at Birmingham
Contact:

Re: Interior Node Recognizer

Post by hyatt » Wed Jun 16, 2010 5:19 pm

kongsian wrote:
hyatt wrote: The interior node recognizer approach is a sort of win/lose/draw eval with no knowledge of any kind beside that used in the recognizer itself. For a simple example, KRB vs KR is a draw. But the KRB side can win pretty easily if the KR side plays stupidly and gets stuck on the edge of the board. If you just say "all KRB vs KR positions are drawn" you'd better hope that you don't reach one that is lost and report it as a draw, else you end up losing. You might guess it sounds like I have done this before. :) I have. And got burned badly a few times.
Actually that is not quite correct. The interior node recognizer can return bounds as well, not just win/lose/draw. So for KNKP my recognizer returns drawscore as an upperbound for white. The search than proceeds as normal.

Anyway I feel there is a lot of potential with this and will continue to pursue this further. Thanks.

Kong Sian

I don't see how a "bound" helps. If you make the bound large enough to avoid the problems, then suddenly your interior node recognizers are not doing their job, which is to terminate the search _immediately_ when they reach a particular type of position. The whole idea was to stop the search at interior nodes when a recognizer "kicks in" which can greatly speed up endgame searches. The "bounds" you artificially set are only applicable below this node, not above, which reduces effectiveness. I eventually decided to move all of this into the eval to give a chance for lots of piece shuffling that will discover those unusual mates/material wins, before we get to a position where we apply a heuristic to evaluate each side's winning chances.

zamar
Posts: 16
Joined: Thu Jun 10, 2010 1:28 am

Re: Interior Node Recognizer

Post by zamar » Wed Jun 16, 2010 6:01 pm

Pawel Koziol wrote:
for KNKP my recognizer returns drawscore as an upperbound for white. The search than proceeds as normal.
actually this is a good illustration of dangers inherent to coding interior node recognizers and forgetting about exceptions. There is a KNKP position with a rook pawn, the king of the weaker side in front of it and the king of the stronger side in a horizontal opposition that leads to a forced mate.

Pawel
That's why it's recommendable to check your recognizers using tablebases or bitbases when possible (even if you don't want to use them in the final version of your program).

KK, KBK, KNK are always draw. Anything beyond that you need to be very careful :-)

Post Reply