Interesting ideas

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Karlo Bala
Posts: 313
Joined: Wed Mar 22, 2006 9:17 am
Location: Novi Sad, Serbia

Re: Interesting ideas

Post by Karlo Bala » Wed Sep 09, 2015 11:23 am

Henk wrote:I would like to read about chess ideas, alternative approaches that does not work. Maybe it will help to generate other ideas.

Any interesting (bad) ideas ? Show me the trash.
If you have time, try this:

1. B*
2. Tree Searching by Min / Max Approximation
3. Monte Carlo
4. BPIP-DFISA

I'm not saying that these are bad approaches.
Best Regards,
Karlo Balla Jr.

Dann Corbit
Posts: 11248
Joined: Wed Mar 08, 2006 7:57 pm
Location: Redmond, WA USA
Contact:

Re: Interesting ideas

Post by Dann Corbit » Wed Sep 09, 2015 8:41 pm

Along those lines:
C*
binary search for best move.

Dann Corbit
Posts: 11248
Joined: Wed Mar 08, 2006 7:57 pm
Location: Redmond, WA USA
Contact:

Re: Interesting ideas

Post by Dann Corbit » Wed Sep 09, 2015 8:47 pm

Ref:
https://chessprogramming.wikispaces.com/NegaC*

I always found the idea appealing. Unfortunately, I could never get good results.

Karlo Bala
Posts: 313
Joined: Wed Mar 22, 2006 9:17 am
Location: Novi Sad, Serbia

Re: Interesting ideas

Post by Karlo Bala » Wed Sep 09, 2015 9:02 pm

Dann Corbit wrote:Ref:
https://chessprogramming.wikispaces.com/NegaC*

I always found the idea appealing. Unfortunately, I could never get good results.
There are few things that perhaps can improve NegaC

1. Instead of binary search use golden or fibonacci ratio
2. Instead of global MIN and MAX use some kind of aspiration windows
3. Instead of stop criteria based on score [while (min != max)...] stop when one move is better then others (this may lead to imprecise PV but possibly improve time to depth)
Best Regards,
Karlo Balla Jr.

PK
Posts: 861
Joined: Mon Jan 15, 2007 10:23 am
Location: Warsza
Contact:

Re: Interesting ideas

Post by PK » Fri Sep 11, 2015 4:16 pm

Today I failed with using null move verification search as a replacement for internal iterative deepening. The idea was to retrieve hash move after a verification search (in absence of a real hash move) and order it first. Of course it is stupid, because we know for sure that this move is rather suspect, as it didn't score above beta. If it did, we would have a cutoff and would not need any move ordering in first place :oops:

However, there just might be some point in updating killers, history and refutation moves if verification search produces a cutoff.

User avatar
cdani
Posts: 2166
Joined: Sat Jan 18, 2014 9:24 am
Location: Andorra
Contact:

Re: Interesting ideas

Post by cdani » Sat Sep 12, 2015 9:13 am

Inspired for the post about improving SEE, but not related to SEE, I tried a hash of captures, whose key is the combined keys of the source and destination of the pieces that can capture in a position, and the idea is to store the best capture.

After some tries I arrived to one version that is just level for fastest time controls, and possibly a little loss for 30 seconds or more. For the moment I dismissed it. May be I can use it or something similar for instead try to order better the captures.

My best attempt was by using it only alpha_beta, not in quiescence, and not store it if the best move was the first one.

nionita
Posts: 163
Joined: Fri Oct 22, 2010 7:47 pm
Location: Austria

Re: Interesting ideas

Post by nionita » Sat Sep 12, 2015 1:06 pm

I was fighting a lot trying to use somehow the threat move from the null move search.

At the end I inserted it as a killer move. After about 70k games the resulting gain was ~2cp, a bit smaller then the error margin (more engines involved in the games). But I let the code in place, 'cause I could not accept the idea that that information is useless.

User avatar
cdani
Posts: 2166
Joined: Sat Jan 18, 2014 9:24 am
Location: Andorra
Contact:

Re: Interesting ideas

Post by cdani » Sat Sep 12, 2015 1:15 pm

nionita wrote:I was fighting a lot trying to use somehow the threat move from the null move search.

At the end I inserted it as a killer move. After about 70k games the resulting gain was ~2cp, a bit smaller then the error margin (more engines involved in the games). But I let the code in place, 'cause I could not accept the idea that that information is useless.
I have it also like a killer, with preference in move ordering and less reductions.

jdart
Posts: 3956
Joined: Fri Mar 10, 2006 4:23 am
Location: http://www.arasanchess.org

Re: Interesting ideas

Post by jdart » Mon Sep 14, 2015 2:36 am

Stockfish had code that would extend a previously reduced move if the threat move from a null search was related to that previous move. They also disabled certain pruning/reductions for moves that appeared to counter the null move threat. However IIRC this code was removed from Stockfish at some point.

--Jon

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

Re: Interesting ideas

Post by hgm » Mon Sep 14, 2015 7:19 am

nionita wrote:I was fighting a lot trying to use somehow the threat move from the null move search.
Indeed, I also had that experience. The true threat seems to be masked most of the time by an unrelated harmless Q or R trade, which in the move ordering goes (quite justly) before cashing of an existing threat. The special evasion code that would use this information would then try to avoid that trade, rather than solving the real problem.

Basing the threat on SEE is much more reliable. If the node after nullmove uses SEE to order its captures, the capture with the highest SEE could be labeled as the threat move. The catch is that for efficiency reasons we often don't calculate SEE for good or equal captures, as they are ordered by victim value. LxH captures are easy to recognize, and always represent threats. But for the equal captures of protected pieces it depends on what follows. So you might be forced to subject them to SEE, at least in the node after null move.

Post Reply