New Search Method(s)

[Don]

As we all know, alpha-beta with null-move, LMR and quiescence (etc etc) is far from being a brute-force method.

I don't agree. "Brute force" is a very fair description of alpha-beta with null move, LMR and quiescence, IMHO. These are all very crude and simple techniques.

Brute force works very well for chess, because in a way, chess is a rather simple game. In general, the player with more material wins, and material is easy to count. All a program has to do to beat humans is to avoid giving away material, ruthlessly capture material whenever it has the chance, and not creating too many obvious positional weaknesses. It doesn't even matter if the humans play stronger moves on average (which I actually think is still true for the top human players), because even the best humans make too many serious tactical mistakes.

It would be interesting to see more research in chess programs using entirely different techniques -- even if these programs weren't quite as strong -- but because most programmers find it more attractive to follow an easy road to write a super strong program than to follow a very hard road to create a program that will perhaps not play very well at all, such programs are not very likely to appear. Less concrete and materialistic games (like go and shogi) are more interesting from this perspective.

I completely agree. The alternative to "brute force" is "selective search". And while one could argue that we do a tiny bit of forward pruning in the last 4 plies (or so) of the tree, and that reductions are a more restrictive form of selectivity, we do anything but a real selective search. The real underlying idea in selective search is that you apply some sort of selection criteria, and exclude moves at various points in the tree, and they are excluded, period. Not searched to reduced depth. Not subject to "coming back" if something better is not found. We don't do that. We did in the early 70's, but it is beyond problematic and brute forced kicked selective search right in the teeth and put it down for the count.

The real underlying idea in selective search is that you apply some sort of selection criteria, and exclude moves at various points in the tree, and they are excluded, period. I think this is exactly correct, but I think you believe that the selection criteria cannot in any way involve search. This is a very limited definition of selective search and if that is how you define it, then it's a useless concept for chess.

A much more useful and far less limited definition of the "selection criteria" is to not read anything additional into the term "selection criteria", it is a black box that discards moves with significantly less work that would normally be done. It has a lot more to do with "what" you do, not "how" you do it.

[Don]

As we all know, alpha-beta with null-move, LMR and quiescence (etc etc) is far from being a brute-force method.

I don't agree. "Brute force" is a very fair description of alpha-beta with null move, LMR and quiescence, IMHO. These are all very crude and simple techniques.

Brute force works very well for chess, because in a way, chess is a rather simple game. In general, the player with more material wins, and material is easy to count. All a program has to do to beat humans is to avoid giving away material, ruthlessly capture material whenever it has the chance, and not creating too many obvious positional weaknesses. It doesn't even matter if the humans play stronger moves on average (which I actually think is still true for the top human players), because even the best humans make too many serious tactical mistakes.

It would be interesting to see more research in chess programs using entirely different techniques -- even if these programs weren't quite as strong -- but because most programmers find it more attractive to follow an easy road to write a super strong program than to follow a very hard road to create a program that will perhaps not play very well at all, such programs are not very likely to appear. Less concrete and materialistic games (like go and shogi) are more interesting from this perspective.

From what I read, the best programs have an effective branching factor of 2.0 for each ply. That's far below the number of moves per ply, which tells me that there is so much pruning that I can't call it brute-force (which is a well defined term meaning blindly exploring every possibility in a search space).

Programs may have an "effective branching factor" of 2.0 or less, but not a real branching factor. Unless you do forward pruning, and nobody does that very close to the root, you will have a branching factor of about 38 if you average over the entire game...

I do not believe that anybody would say that plain alpha/beta is not brute force, and yet it has an effective branching factor of sqrt(38) to 2*sqrt(38) with no reductions or futility pruning. Brute force simply implies that all moves are searched, whether they are reduced or extended is irrelevant.

This is the point we disagree on. Even by your own definition if I have 38 moves and reject 36 of them, I still had to do SOMETHING to reject them, even if it is to apply a swap off or static analysis of some kind - which is in fact a 1 ply search. It's very arbitrary to make an issue out of how that selection criteria "HAS" to work in order to be called selective.

Near the tips we certainly forward prune, and in the q-search we forward prune everything but captures, promotions and maybe a few checks. But that is out on the horizon, not near the root...

[bob]

As we all know, alpha-beta with null-move, LMR and quiescence (etc etc) is far from being a brute-force method.

I don't agree. "Brute force" is a very fair description of alpha-beta with null move, LMR and quiescence, IMHO. These are all very crude and simple techniques.

Brute force works very well for chess, because in a way, chess is a rather simple game. In general, the player with more material wins, and material is easy to count. All a program has to do to beat humans is to avoid giving away material, ruthlessly capture material whenever it has the chance, and not creating too many obvious positional weaknesses. It doesn't even matter if the humans play stronger moves on average (which I actually think is still true for the top human players), because even the best humans make too many serious tactical mistakes.

It would be interesting to see more research in chess programs using entirely different techniques -- even if these programs weren't quite as strong -- but because most programmers find it more attractive to follow an easy road to write a super strong program than to follow a very hard road to create a program that will perhaps not play very well at all, such programs are not very likely to appear. Less concrete and materialistic games (like go and shogi) are more interesting from this perspective.

I completely agree. The alternative to "brute force" is "selective search". And while one could argue that we do a tiny bit of forward pruning in the last 4 plies (or so) of the tree, and that reductions are a more restrictive form of selectivity, we do anything but a real selective search. The real underlying idea in selective search is that you apply some sort of selection criteria, and exclude moves at various points in the tree, and they are excluded, period. Not searched to reduced depth. Not subject to "coming back" if something better is not found. We don't do that. We did in the early 70's, but it is beyond problematic and brute forced kicked selective search right in the teeth and put it down for the count.

The real underlying idea in selective search is that you apply some sort of selection criteria, and exclude moves at various points in the tree, and they are excluded, period. I think this is exactly correct, but I think you believe that the selection criteria cannot in any way involve search. This is a very limited definition of selective search and if that is how you define it, then it's a useless concept for chess.

A much more useful and far less limited definition of the "selection criteria" is to not read anything additional into the term "selection criteria", it is a black box that discards moves with significantly less work that would normally be done. It has a lot more to do with "what" you do, not "how" you do it.

You can certainly use search to make inclusion/exclusion rules. No problem with that. But as a simple example, at the root, I will search every last move, with no exception. Beyond that, backward-pruning (alpha/beta) can cut off branches by proving them inferior. But forward-pruning cuts off in the other way, and once cut off, they are not considered, period. That is the classic definition of selective search. Where you use some sort of information to make the inclusion/exclusion decision and this "information" is not based on a search to full depth, otherwise you are not excluding anything.

Certainly reductions are a tenuous form of this, since we reduce the depth of a branch significantly. But it is done pretty ad-hoc, based on a move's position in the list (or on some other static criteria). The idea of selective search was to use some sort of intelligent "oracle" to exclude worthless moves, as a human does when playing the game. We are _nowhere_ near what a human does. We replace quality with tons of quantity, which is not the same thing. The alpha/beta algorithm is neither selective nor brute-force, since I used alpha/beta in a _very_ selective program in the early 70's.

If you take a brute-force alpha/beta searcher, and add check extensions, is it then a "selective" program? Perhaps in a way of thinking, since some branches are searched more deeply than others. Or you can do full-width but just toss out some moves near the tips, which lops some branches off quicker than others. Also a way of thinking about selective search. But in most AI references, there is some sort of "intelligent decision-making" that is applied to decide what moves are kept and which are tossed out forever. I find it hard to align what we are doing with extensions, reductions, and pruning at last 3-4 plies with that particular idea...

But a case can be made for either perspective...

[Don]

You can certainly use search to make inclusion/exclusion rules. No problem with that. But as a simple example, at the root, I will search every last move, with no exception. Beyond that, backward-pruning (alpha/beta) can cut off branches by proving them inferior. But forward-pruning cuts off in the other way, and once cut off, they are not considered, period. That is the classic definition of selective search. Where you use some sort of information to make the inclusion/exclusion decision and this "information" is not based on a search to full depth, otherwise you are not excluding anything.

I fully understand your point. The classic idea is that you reject a bunch of moves without doing hardly any work and proclaim the search highly selective and human-like.

I just don't believe that is a very useful definition of "selective search." The notion that it's forbidden to do certain types of analysis but not other types of analysis is not interesting when it comes to a discussion of "rejecting alpha/beta" to find something more like humans play. That is really what I'm reacting against.

I've always been a bit annoyed to see "brute force" get redefined every year to always mean whatever we are currently doing.

Certainly reductions are a tenuous form of this, since we reduce the depth of a branch significantly. But it is done pretty ad-hoc, based on a move's position in the list (or on some other static criteria). The idea of selective search was to use some sort of intelligent "oracle" to exclude worthless moves, as a human does when playing the game. We are _nowhere_ near what a human does. We replace quality with tons of quantity, which is not the same thing. The alpha/beta algorithm is neither selective nor brute-force, since I used alpha/beta in a _very_ selective program in the early 70's.

If you take a brute-force alpha/beta searcher, and add check extensions, is it then a "selective" program? Perhaps in a way of thinking, since some branches are searched more deeply than others. Or you can do full-width but just toss out some moves near the tips, which lops some branches off quicker than others. Also a way of thinking about selective search. But in most AI references, there is some sort of "intelligent decision-making" that is applied to decide what moves are kept and which are tossed out forever. I find it hard to align what we are doing with extensions, reductions, and pruning at last 3-4 plies with that particular idea...

But a case can be made for either perspective...

[bob]

As we all know, alpha-beta with null-move, LMR and quiescence (etc etc) is far from being a brute-force method.

I don't agree. "Brute force" is a very fair description of alpha-beta with null move, LMR and quiescence, IMHO. These are all very crude and simple techniques.

Brute force works very well for chess, because in a way, chess is a rather simple game. In general, the player with more material wins, and material is easy to count. All a program has to do to beat humans is to avoid giving away material, ruthlessly capture material whenever it has the chance, and not creating too many obvious positional weaknesses. It doesn't even matter if the humans play stronger moves on average (which I actually think is still true for the top human players), because even the best humans make too many serious tactical mistakes.

It would be interesting to see more research in chess programs using entirely different techniques -- even if these programs weren't quite as strong -- but because most programmers find it more attractive to follow an easy road to write a super strong program than to follow a very hard road to create a program that will perhaps not play very well at all, such programs are not very likely to appear. Less concrete and materialistic games (like go and shogi) are more interesting from this perspective.

From what I read, the best programs have an effective branching factor of 2.0 for each ply. That's far below the number of moves per ply, which tells me that there is so much pruning that I can't call it brute-force (which is a well defined term meaning blindly exploring every possibility in a search space).

Programs may have an "effective branching factor" of 2.0 or less, but not a real branching factor. Unless you do forward pruning, and nobody does that very close to the root, you will have a branching factor of about 38 if you average over the entire game...

I do not believe that anybody would say that plain alpha/beta is not brute force, and yet it has an effective branching factor of sqrt(38) to 2*sqrt(38) with no reductions or futility pruning. Brute force simply implies that all moves are searched, whether they are reduced or extended is irrelevant.

This is the point we disagree on. Even by your own definition if I have 38 moves and reject 36 of them, I still had to do SOMETHING to reject them, even if it is to apply a swap off or static analysis of some kind - which is in fact a 1 ply search. It's very arbitrary to make an issue out of how that selection criteria "HAS" to work in order to be called selective.

As I said in my other post, this is certainly a valid point for debate, and one could take either side of the issue and have plenty of points for arguing.

However, the "L" in LMR is not a very intelligent approach to selectivity. At least with null-move, we try a reduced-depth search and the null-move observation is a valid idea. But with LMR we just reduce the crap out of moves based on their order in the move list, where not a lot of effort goes into that ordering. In the early to middle 70's, I did the usual shannon-B program, where we had a max number of moves to search at each depth, usually tapered as you get farther from the root. But these selections/exclusions are not based on much in the way of intelligence or trying to emulate human chess playing. A human is _clearly_ a selective searcher, looking at a hundred (or two) positions to choose a single move to play in the game. That is selective. And includes lots of room for error. And we use a lot of unknown skills to produce that selectivity, unknown because no one has a clue about what goes on inside the mind during that process.

Computers do everything quickly. And clearly even with reductions, the first N plies of the search are certainly full-width. Just that for a 24 ply search, you might only go 6-8 moves deep along all branches and then search others deeper or not depending on some very simplistic rules. Might be interesting to measure this effect. For every call to Quiesce, record the number of plies from the root in one counter, and the actual iteration depth in another. Then average both over a game to see how deep an N ply search actually goes full-width...

Near the tips we certainly forward prune, and in the q-search we forward prune everything but captures, promotions and maybe a few checks. But that is out on the horizon, not near the root...

[Don]

As we all know, alpha-beta with null-move, LMR and quiescence (etc etc) is far from being a brute-force method.

I don't agree. "Brute force" is a very fair description of alpha-beta with null move, LMR and quiescence, IMHO. These are all very crude and simple techniques.

Brute force works very well for chess, because in a way, chess is a rather simple game. In general, the player with more material wins, and material is easy to count. All a program has to do to beat humans is to avoid giving away material, ruthlessly capture material whenever it has the chance, and not creating too many obvious positional weaknesses. It doesn't even matter if the humans play stronger moves on average (which I actually think is still true for the top human players), because even the best humans make too many serious tactical mistakes.

It would be interesting to see more research in chess programs using entirely different techniques -- even if these programs weren't quite as strong -- but because most programmers find it more attractive to follow an easy road to write a super strong program than to follow a very hard road to create a program that will perhaps not play very well at all, such programs are not very likely to appear. Less concrete and materialistic games (like go and shogi) are more interesting from this perspective.

From what I read, the best programs have an effective branching factor of 2.0 for each ply. That's far below the number of moves per ply, which tells me that there is so much pruning that I can't call it brute-force (which is a well defined term meaning blindly exploring every possibility in a search space).

Programs may have an "effective branching factor" of 2.0 or less, but not a real branching factor. Unless you do forward pruning, and nobody does that very close to the root, you will have a branching factor of about 38 if you average over the entire game...

I do not believe that anybody would say that plain alpha/beta is not brute force, and yet it has an effective branching factor of sqrt(38) to 2*sqrt(38) with no reductions or futility pruning. Brute force simply implies that all moves are searched, whether they are reduced or extended is irrelevant.

This is the point we disagree on. Even by your own definition if I have 38 moves and reject 36 of them, I still had to do SOMETHING to reject them, even if it is to apply a swap off or static analysis of some kind - which is in fact a 1 ply search. It's very arbitrary to make an issue out of how that selection criteria "HAS" to work in order to be called selective.

As I said in my other post, this is certainly a valid point for debate, and one could take either side of the issue and have plenty of points for arguing.

Yes, I agree. It comes down to semantics and how you define things and there is no point in us arguing that as long as we understand the issues.

However, the "L" in LMR is not a very intelligent approach to selectivity. At least with null-move, we try a reduced-depth search and the null-move observation is a valid idea. But with LMR we just reduce the crap out of moves based on their order in the move list, where not a lot of effort goes into that ordering.

It amazes me that it works so well. It's about 100 ELO for Komodo on shallow searches and probably goes up with depth.

However it's not surprising if you take measurements at all-nodes to see how often move 1 is best, then move 2, and so on. You will find that each move is best much more often than the next move in the list. At least it's this way for Komodo. I think the best move was in the first 2 or 3 something like 95% of the time or more. I don't remember the exact number, but what I saw made it obvious why LMR works so well.

To me this is like old fashioned selective search. It has all the elements, and it's just done more intelligently. Here is how it works:

1. Pick the best N moves and search them.

2. Discard the rest.

But step 2 is a bit more intelligent because it goes like this:

2.1 select the next candidate to be tossed.

2.2 perform a quick test to determine that you really want to toss it.

2.3 toss the move unless step 2.2 says otherwise.


Step 1 is to pick the best N moves, and it's natural to determine that by sorting the move list so that the best move is first, the second best is second, etc. Well isn't that what we are doing?

The quality of the moves is determined by some sort of heuristic - in my case a variant of the history heuristic combined with other criteria but nothing prevents anyone from doing something more clever.

You may balk at using the history heuristic, but it's way better than what the old fashioned "selective search" programs did - statistics are more reliable that the superficial things they tried to do. (Of course they were very crippled by hardware, we are not.)

To me, reducing a move, is virtually the same as deciding whether to toss it.

So from what I see there is no argument for saying what we are doing is nothing like selective search. It's hard to even imagine improving on this except by having a smarter evaluation function and a smarter "selection criteria" which is exactly what everyone is trying to do.

The observation is correct that we have to look at millions of nodes to play just as well as a human. This always seems to lead people to believe that we are doing it all wrong with computers. I don't feel that way, because I don't believe humans and computers are built with the same hardware and design.

That would be like saying that something is wrong with humans because they cannot run as fast as horses and trying to improve on this by imitating the horse. To imitate the superior horse we would have to run on our hands and feet - after all the horse is faster and that's how they do it. But we are not made the same as horses. We have to do what works best for us, horses have to do what works best for them, and we have to program computers to take advantage of what they do best and we don't.

In the early to middle 70's, I did the usual shannon-B program, where we had a max number of moves to search at each depth, usually tapered as you get farther from the root. But these selections/exclusions are not based on much in the way of intelligence or trying to emulate human chess playing. A human is _clearly_ a selective searcher, looking at a hundred (or two) positions to choose a single move to play in the game. That is selective. And includes lots of room for error. And we use a lot of unknown skills to produce that selectivity, unknown because no one has a clue about what goes on inside the mind during that process.

Computers do everything quickly. And clearly even with reductions, the first N plies of the search are certainly full-width. Just that for a 24 ply search, you might only go 6-8 moves deep along all branches and then search others deeper or not depending on some very simplistic rules. Might be interesting to measure this effect. For every call to Quiesce, record the number of plies from the root in one counter, and the actual iteration depth in another. Then average both over a game to see how deep an N ply search actually goes full-width...

Near the tips we certainly forward prune, and in the q-search we forward prune everything but captures, promotions and maybe a few checks. But that is out on the horizon, not near the root...

[AlvaroBegue]

[...]

That would be like saying that something is wrong with humans because they cannot run as fast as horses and trying to improve on this by imitating the horse. To imitate the superior horse we would have to run on our hands and feet - after all the horse is faster and that's how they do it. But we are not made the same as horses. We have to do what works best for us, horses have to do what works best for them, and we have to program computers to take advantage of what they do best and we don't.

It turns out it's not entirely clear that horses are better runners than humans: http://www.runblogger.com/2009/08/man-v ... athon.html

That was pretty out of topic, sorry.

Back on topic, I don't think selectivity (of the type where you never reconsider your decision of not exploring a move) is a good idea for either computers or humans. You may initially discard a move that makes you lose your queen, but if you never reconsider such moves, you will never find a queen sacrifice. Hard rules excluding certain moves are always brittle and it should be the case that if there is enough time for the search, you'll spend some time considering the move. Of course this doesn't apply to moves pruned by a beta cut, where the result of the search can't possibly affect the result at the root.

The debate of whether modern chess programs use "brute force" or not is pretty sterile. They do go through all sorts of crazy possibilities that a human wouldn't consider, but they certainly don't just do the most naive thing that comes to mind when you hear "brute force", and using that term belittles the contributions of many authors through the years.

[Michael Sherwin]

It turns out it's not entirely clear that horses are better runners than humans: http://www.runblogger.com/2009/08/man-v ... athon.html

That is a very unfair contest!

The horse had to carry a man.

So to be fair the man would haft to carry a horse.

[Tord Romstad]

I have to respectfully disagree. If you look at the branching factor of stockfish, it's clear that you are not doing brute force searching - even if you define what you are doing as "brute force" it's semantics.

It's interesting that over the years the definition of "brute force" has changed. It used to mean no pruning of any kind, fixed depth iterative deepening until quies and then captures only. Then when null move pruning came out those programs were considered highly selective programs. After everyone was doing null move pruning it was suddenly viewed as "brute force" and now that LMR is so common all programs are once again just "brute force" programs.

Yes, of course it depends on your definition of "brute force". Defining brute force as plain minimax is not very interesting today.

Chess programs are still brute force in the sense that most of them use hardly any knowledge in the search (apart from a few very basic observations like "zugzwang is unusual"), and that they try (and succeed) to compensate for the lack of knowledge by looking at an immense number of nodes.

[Uri Blass]

I have to respectfully disagree. If you look at the branching factor of stockfish, it's clear that you are not doing brute force searching - even if you define what you are doing as "brute force" it's semantics.

It's interesting that over the years the definition of "brute force" has changed. It used to mean no pruning of any kind, fixed depth iterative deepening until quies and then captures only. Then when null move pruning came out those programs were considered highly selective programs. After everyone was doing null move pruning it was suddenly viewed as "brute force" and now that LMR is so common all programs are once again just "brute force" programs.

Yes, of course it depends on your definition of "brute force". Defining brute force as plain minimax is not very interesting today.

Chess programs are still brute force in the sense that most of them use hardly any knowledge in the search (apart from a few very basic observations like "zugzwang is unusual"), and that they try (and succeed) to compensate for the lack of knowledge by looking at an immense number of nodes.

I do not agree that chess programs are still brute force and I guess that stockfish earns hundrends of elo relative to simple alpha beta with no pruning and no extensions including no check extension and no checks in the qsearch or even relative to simple alpha beta with only null move pruning.

I think that knowledge in the search that is worth more than 100 elo is not hardly any knowledge but a lot of knowledge.
I measure knowledge in terms of elo that the knowledge gives and not in terms of lines of code.