New Search Method(s)

[Don]

I have read about very selective tactical program in mid 1980's that could find deep combinations using very narrow search tree. The problem that it does not return any move when there are no tactical solution in the given test position, so it could not play full chess.

If you are talking about Botvinik's program I have had many discussions with top chess program authors and so far not one of them thinks this was legitimate.

What he wrote on this was highly abstract to the point of absurdity. It was one of those things that appealed to the artistic side of the brain, but was pure double-talk or gibberish. This same observation is shared with many program authors.

Botvinnik never had an actual program. He wrote his algorithm in mathematical language adapted to chess. He then paper executed his algorithm on a select position or so to demonstrate how the algorithm could find deep winning tactics. To all but Botvinnik his mathematical rendition of the algorithm would look like utter gibberish. Then in the 80's some group of programmers tried to create a program based on Botvinnik's algorithm and failed. It was not known if Botvinnik had any meaningful interaction with the programmers.

Yes, but then the Ipollito programmers succeeded in using Botvinniks ideas to make a highly unique and superior program.

Did they?

I cannot find it now, but somewhere on one the web sites for these programs they give some credit to Botvinnik for their ideas.

[bob]

I have read about very selective tactical program in mid 1980's that could find deep combinations using very narrow search tree. The problem that it does not return any move when there are no tactical solution in the given test position, so it could not play full chess.

If you are talking about Botvinik's program I have had many discussions with top chess program authors and so far not one of them thinks this was legitimate.

What he wrote on this was highly abstract to the point of absurdity. It was one of those things that appealed to the artistic side of the brain, but was pure double-talk or gibberish. This same observation is shared with many program authors.

Botvinnik never had an actual program. He wrote his algorithm in mathematical language adapted to chess. He then paper executed his algorithm on a select position or so to demonstrate how the algorithm could find deep winning tactics. To all but Botvinnik his mathematical rendition of the algorithm would look like utter gibberish. Then in the 80's some group of programmers tried to create a program based on Botvinnik's algorithm and failed. It was not known if Botvinnik had any meaningful interaction with the programmers.

The problem with Botvinnik's publication(s) on this algorithm is that they contain provably fabricated analysis. In light of no implementation, and fabricated "paper analysis" I don't see any way this would get any credibility.

[Michael Sherwin]

I have read about very selective tactical program in mid 1980's that could find deep combinations using very narrow search tree. The problem that it does not return any move when there are no tactical solution in the given test position, so it could not play full chess.

If you are talking about Botvinik's program I have had many discussions with top chess program authors and so far not one of them thinks this was legitimate.

What he wrote on this was highly abstract to the point of absurdity. It was one of those things that appealed to the artistic side of the brain, but was pure double-talk or gibberish. This same observation is shared with many program authors.

Botvinnik never had an actual program. He wrote his algorithm in mathematical language adapted to chess. He then paper executed his algorithm on a select position or so to demonstrate how the algorithm could find deep winning tactics. To all but Botvinnik his mathematical rendition of the algorithm would look like utter gibberish. Then in the 80's some group of programmers tried to create a program based on Botvinnik's algorithm and failed. It was not known if Botvinnik had any meaningful interaction with the programmers.

The problem with Botvinnik's publication(s) on this algorithm is that they contain provably fabricated analysis. In light of no implementation, and fabricated "paper analysis" I don't see any way this would get any credibility.

I am interested in the underlying theme of his idea and how it can be applied in a modern alpha-beta searcher and not the character or lack of character that Botvinnik may have possessed. The idea can have credibility or a lack of credibility independent of the person that first proposed it based on a discussion of its possible merits in a forum such as this. I will try to show my adaptation of the underlying theme of Botvinnik's algorithm to modern computer chess by the use of symbols. First, I will say that the underlying theme seems to be a series of very specific type moves by one side while the other side plays null moves. So, now:

Let L = a single legal generated move
Let LLL = a list of legal generated moves
Let M = any legal move that meets the test for inclusion
Let MMM = the list of legal moves that are included
Let m = a legal move that that does not meet the test for inclusion
Let mmm = the list of legal moves that do not meet the test for inclusion
Let N = a null move

Gen LLL1
Get first LLL1->L1
L1 becomes M1->MMM1 or m1->mmm1 based on single N test, get next LLL1
Get first m1 make N, Gen LLL2
Get first LLL2->L2, if L2 is a member of MMM1 then Get next LLL2->L2
if m1 + N + L2 + N + search is > alpha (- margin) then mmm1->m1->M1->MMM1, Get next m1
Get next LLL2
For all remaining mmm1 do similar to above=> (*)
m1 + N + L2 + N + L3 + N + search, if search > alpha then mmm1->m1->M1->MMM1
* check L2, L3 not in MMM1

Is there any merit to this?

[bob]

I have read about very selective tactical program in mid 1980's that could find deep combinations using very narrow search tree. The problem that it does not return any move when there are no tactical solution in the given test position, so it could not play full chess.

If you are talking about Botvinik's program I have had many discussions with top chess program authors and so far not one of them thinks this was legitimate.

What he wrote on this was highly abstract to the point of absurdity. It was one of those things that appealed to the artistic side of the brain, but was pure double-talk or gibberish. This same observation is shared with many program authors.

Botvinnik never had an actual program. He wrote his algorithm in mathematical language adapted to chess. He then paper executed his algorithm on a select position or so to demonstrate how the algorithm could find deep winning tactics. To all but Botvinnik his mathematical rendition of the algorithm would look like utter gibberish. Then in the 80's some group of programmers tried to create a program based on Botvinnik's algorithm and failed. It was not known if Botvinnik had any meaningful interaction with the programmers.

The problem with Botvinnik's publication(s) on this algorithm is that they contain provably fabricated analysis. In light of no implementation, and fabricated "paper analysis" I don't see any way this would get any credibility.

I am interested in the underlying theme of his idea and how it can be applied in a modern alpha-beta searcher and not the character or lack of character that Botvinnik may have possessed. The idea can have credibility or a lack of credibility independent of the person that first proposed it based on a discussion of its possible merits in a forum such as this. I will try to show my adaptation of the underlying theme of Botvinnik's algorithm to modern computer chess by the use of symbols. First, I will say that the underlying theme seems to be a series of very specific type moves by one side while the other side plays null moves. So, now:

Let L = a single legal generated move
Let LLL = a list of legal generated moves
Let M = any legal move that meets the test for inclusion
Let MMM = the list of legal moves that are included
Let m = a legal move that that does not meet the test for inclusion
Let mmm = the list of legal moves that do not meet the test for inclusion
Let N = a null move

Gen LLL1
Get first LLL1->L1
L1 becomes M1->MMM1 or m1->mmm1 based on single N test, get next LLL1
Get first m1 make N, Gen LLL2
Get first LLL2->L2, if L2 is a member of MMM1 then Get next LLL2->L2
if m1 + N + L2 + N + search is > alpha (- margin) then mmm1->m1->M1->MMM1, Get next m1
Get next LLL2
For all remaining mmm1 do similar to above=> (*)
m1 + N + L2 + N + L3 + N + search, if search > alpha then mmm1->m1->M1->MMM1
* check L2, L3 not in MMM1

Is there any merit to this?

Who can tell? inclusion/exclusion criteria are unspecified, which is a small problem for implementation.

[smcracraft]

Unfortunately only brute force has been proven to work with a nod to a smart-search, but no where near as powerful as BF plus a minor SS.

Sorry, the truth must be told.

When quantum computers some day come out, the game will entirely
change....

[Don]

Is there any merit to this?

There is no merit to this. When Botvinnik came up with this stuff there were no PC's that were capable of anything more than 2 or 3 ply searches, perhaps 4. It was "obvious" to everyone that computers would never be master level using alpha/beta "brute force" search and the big glaring weakness of computers was tactics. (How things have changed.)

It was natural to consider how humans play chess to find some way to improve.

These idea are naive because the basic premise is that what humans do is computationally trivial - as if all we have to do is copy the way humans do it and suddenly the computers think just like humans. Most people seem to believe that the human brain can be exceeded with computer hardware that is 30 years old or older.

This is not to say that we cannot learn from copying some things about how humans play the game, we already have done that in many ways.

To me, if you want a unique approach that really emulates how a human plays the game (and don't mind if it's hundreds of ELO weaker) you have to figure out how to do pattern recognition - not naive matching but a system with a powerful generalization system that can guide the search. And yes, there has to be a search as much as people like to imagine that humans don't do a search and only look at the best move that is total nonsense. What we do is a highly selective search but one that can be modified on the fly as we notice things. We can stop suddenly based on an insight and start over in some cases.

As soon as you start thinking in terms of chess concepts and makes lists of them, you are missing the point. The chess concepts came out of the thinking process that humans do, not the other way around.

[Antonio Torrecillas]

here my two cents.
first consider the problematic: move + nullmove + search
There are two special cases to consider:

check+null_move+search = mate in one. (include all checks?) Null move while in check don't give any usefull information.

capture+null_move+search probably > alpha (include all captures?) this is Hit and run (Berliner term). The offending piece takes the extra movement to escape.

These are common issues in B*.
Applying to the proposed _second_order_ nullmove:move+null+move+null+search

second order check : useless_move + null + check + null + search = mate in one.
second order hit and run : useless_move + null + capture + null + search

We need some additional heuristic to handle these situations as we want to be selective.
Looks like a hard job.

[Don]

here my two cents.
first consider the problematic: move + nullmove + search
There are two special cases to consider:

check+null_move+search = mate in one. (include all checks?) Null move while in check don't give any usefull information.

null move is an algorithm that works well in practice, but in some ways is badly broken. multi-cut is a more correct way to do it that is very null-move-like, but we have not been able to prove works better in actual practice. If I could get away with it I would be using multi-cut as I believe it's ultimately more scalable - but null move works better right now so I have to use it.

capture+null_move+search probably > alpha (include all captures?) this is Hit and run (Berliner term). The offending piece takes the extra movement to escape.

These are common issues in B*.
Applying to the proposed _second_order_ nullmove:move+null+move+null+search

second order check : useless_move + null + check + null + search = mate in one.
second order hit and run : useless_move + null + capture + null + search

We need some additional heuristic to handle these situations as we want to be selective.
Looks like a hard job.

multi-cut is zugzwang-proof and side effect proof as you only use real moves. Both are subject to horizon issues but I don't view that as a flaw, humans have the same flaw, brute force (no pruning of any kind) has the same flaw etc. I'ts 100% scalable. Null move is not perfectly scalable.

If you are looking for an algorithm that can see the future without building a tree, then you are looking in vain unless you simply just work hard on improving the evaluation function - that is the only thing that let's you substitute a little knowledge (sometimes) for several ply of search.

I get annoyed when these discussion of selectivity come up because the critics (I'm not saying you are doing this) never actually have any useful ideas to contribute. They just like to sound like they know a better way and have more imagination than us stupid people who are doing it all wrong.

I'm not the least bit interesting in new and better ideas, I want to see actual new and better implementations. Don't tell me, show me. To me what is being said is equivalent to saying, "the solution to the high murder rate in this country is for people to stop killing each other." Where is the insight in this?

For example Botvinniks paper is many decades old - so how come no one has implemented these supposedly superior ideas in an actual chess program that is superior to anything else? The information is freely available on how to do it.

[Aleks Peshkov]

I have read about very selective tactical program in mid 1980's that could find deep combinations using very narrow search tree. The problem that it does not return any move when there are no tactical solution in the given test position, so it could not play full chess.

Botvinnik's algorithm does exactly as you describe. The algorithm that I described earlier is based on his algorithm, but includes all chess positions as it measures the eval and not just material. Although, I think that Botvinnik's tactical algorithm can be used in one of two ways within a modern alpha-beta searcher--as a presearch to find deep tactics or as an extension mechanism.

I did not mean Botwinnik's studies.

I have a russian edition of Intelligence artificielle: résolution de problèmes par l'homme et la machine, Jean Louis Laurière, 1987 The book mentions the program ROBIN by J. Pitrat. A short article describes the program and gives some practical ideas about goal oriented selectivity in chess.

Pitrat, J. 1977 "A chess combination program which uses plans" A.I., 8, 275-321

[Antonio Torrecillas]

I feel that my words were misinterpreted.
I think the problems identified are the main issues in the proposals of Michael Sherwin. I must admit that I does not provide any possible solution/idea/improvement, but who has?

Finally, I know (in first person) how much effort is requiered for taking an old paper and reconstruct the algorithm and then make with it a chess playing program.
I've done this with the Berliner/MacDonnell paper. The program is Rocinante and sorry it's not a top program. I'm not that talented.