New Search Method(s)

[bhlangonijr]

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 completely agree.

Regardless of branching factor we are still relying on traverse and evaluate all leaf nodes in a search tree.
IMO it can be fairly entitled brute-force technique as we are generating and testing almost all possibilities from the root node perspective.

Human beings are able to recognize whole themes in many chess positions and accordingly to Kasparov they can use something similar to alpha-beta, but only in a few situations to calculate variations in a very narrow part of the game "subtree". It is amazing how they can play well using such a slow "hardware" compared to actual computers. Although it can sometimes lead them to take odd decisions like in the "blunder of the century" in which Kramnik missed a mate in one against Fritz.

I think if we were capable of implement something hybrid using the state-of-art of alpha beta and the human positional/strategic evaluation it would be hard to beat.

[rbarreira]

Again, brute-force means exploring every possibility in the search space. Minimax is brute-force, the current chess searchers are very far from brute-force. That is not up for discussion unless you believe you can redefine terms to suit the purposes of a discussion.

Semantics aside, recently there was a thread where it was proven that software improvements in the last 15 years have added many hundreds of elo points to chess engines. That is the same difference between an Expert player and a Grandmaster. Clearly these improvements are not from better evaluation only, which means that chess engines are getting farther and farther from using brute-force.

[Don]

[...]

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

I remember reading years ago in some magazine that humans were the fastest non-flying creatures on the planet - when considering long distances. I'm not sure I buy that, but the argument had to do with the idea that we could shed heat better than animals. Dogs have to lose heat mostly through their tongues for instance.

In my marathon running days I took my dog (a boxer) on a 15 mile run with me and I ran at good pace, faster than 8 minute miles. I ran on a country road back then. I was prepared to bring the dog home if necessary. However, the dog literally ran circles around me, it was exploring ahead, behind and sideways the whole time always keeping up and sometimes ahead of me. If I ran 15 miles the dog must have run 45 and she still still wanted more. So I'm not sure I believe the articile but it was interesting.

A well conditioned human can travel all day long at walking speeds and cover a lot of ground. I once covered 35 miles on a long hike in less than 16 hours and there are athletes that run in double marathons, 52 miles. I think this dog could have gone 52 miles easily.

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.

In some ways what a computer does is superior to how a human does it. The iterative deepening part means we come back to reconsider our previous "tentative choices." And it's very orderly, computers do this in a nicely controlled fashion. The reduced depth search and null move pruning is a wonderful tool for controlling the quality of the "selection critieria" of the selective search.

Humans have some amazing strengths too and some of them are far superior to us humans, but I think there is no doubt that computers can do some things much better too such as the bookkeeping involved in doing a recursive iterative deepening search.

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,

I'm not so sure of that. We are not really aware of how we do search. When I'm playing chess I reject most of the moves I know are no good, but I am clearly aware of them. I know that stupid moves are available but SOMETHING must be going on that tells me that it's ok to reject it.

Someone posted a position here once where it was obvious there was an unstoppable passed pawn and in the first 2 or 3 seconds digesting the position I noticed that my brain very quickly eliminated most of the moves from consideration, but SOMETHING was happening. One I felt familiar with the position I gave those other moves no though and it felt almost like they deserved no consideration but I think they DID get consideration - almost at a subconscious level and very quickly.

But that is pretty much like computers do too. If you look at the branching factor of the root moves you will notice that the first move takes a long time, but the rest fly by. I don't think the differences here are as obvious as we think.

But I admit we do take some shortcuts based on patterns. 3 pawns vs 2 on one wing of the board humans know right away that you try to advance the unopposed pawn if you can. But even this is not automatic as there could be tactics that prevent this.

There is also the factor that we are extremely familiar with positions near the opening - positions we have played so many times. It feels like we are being highly selective when all we are doing is realizing that "in this type of position" the only moves that ever work is a, b and c. We have a kind of built in hash table or memory that allows us to take many shortcuts - such as not trying to defend the pawn in the queens gambit. It's not like we figured that out on our own for each and every game. We can even program those things but computers still cannot generalize the lessons learned nearly as well as humans unless we make a general rule and add it to the evaluation function.

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.

Thank you for saying that. For some reason the phrase "brute force" has become a dirty word, a way to put down computer chess techniques. And people try to pretend they are above it by suggesting that it's not intelligent. But on this forum we discussed how much progress software has made over the years and we have not stood still by any stretch of the imagination.

[Don]

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

Here is a quote from that article:

Aside from being an unusual spectacle, what this race shows is that humans really are excellent distance runners when compared to almost any other animal on the planet. Although we've only won twice, that fact that we can compete foot to hoof with an animal that is more often used to transport our bodies over long distances lends further evidence to the phrase that we were "Born to Run."

Of course I was primarily talking about very short distances with my analogy. I could have used the Cheeta as an analogy too, we can clearly outrun Cheeta's at long distances but not in a 100 meter run.

[Rein Halbersma]

I remember reading years ago in some magazine that humans were the fastest non-flying creatures on the planet - when considering long distances. I'm not sure I buy that, but the argument had to do with the idea that we could shed heat better than animals. Dogs have to lose heat mostly through their tongues for instance.

See e.g. this survey paper by Lieberman & Bramble
http://dash.harvard.edu/bitstream/handl ... sequence=3

"human endurance-running speeds, which typically exceed 4 m/s and can reach 6.5 m/s in elite athletes, exceed the trot-gallop transition speed of all other mammals, regardless of size. This difference is significant because trotting is the quadrupedal endurance gait. Most quadrupedal cursors, such as dogs, can run long distances at a trot, but quickly overheat and fatigue when galloping"

[AlvaroBegue]

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

Here is a quote from that article:

Aside from being an unusual spectacle, what this race shows is that humans really are excellent distance runners when compared to almost any other animal on the planet. Although we've only won twice, that fact that we can compete foot to hoof with an animal that is more often used to transport our bodies over long distances lends further evidence to the phrase that we were "Born to Run."

Of course I was primarily talking about very short distances with my analogy. I could have used the Cheeta as an analogy too, we can clearly outrun Cheeta's at long distances but not in a 100 meter run.

Of course, your analogy is valid. I just thought people here might find the human-horse races interesting. I heard a talk by Dr. Lieberman a couple of months ago (where he explained the importance of the trot-gallop transition) and I found it really amusing.

[Don]

I remember reading years ago in some magazine that humans were the fastest non-flying creatures on the planet - when considering long distances. I'm not sure I buy that, but the argument had to do with the idea that we could shed heat better than animals. Dogs have to lose heat mostly through their tongues for instance.

See e.g. this survey paper by Lieberman & Bramble
http://dash.harvard.edu/bitstream/handl ... sequence=3

"human endurance-running speeds, which typically exceed 4 m/s and can reach 6.5 m/s in elite athletes, exceed the trot-gallop transition speed of all other mammals, regardless of size. This difference is significant because trotting is the quadrupedal endurance gait. Most quadrupedal cursors, such as dogs, can run long distances at a trot, but quickly overheat and fatigue when galloping"

Interesting article. So it seems humans really are the fastest when distance is concerned, especially in hot weather, but for many reasons other than just our ability to handle heat.

[Don]

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

Here is a quote from that article:

Aside from being an unusual spectacle, what this race shows is that humans really are excellent distance runners when compared to almost any other animal on the planet. Although we've only won twice, that fact that we can compete foot to hoof with an animal that is more often used to transport our bodies over long distances lends further evidence to the phrase that we were "Born to Run."

Of course I was primarily talking about very short distances with my analogy. I could have used the Cheeta as an analogy too, we can clearly outrun Cheeta's at long distances but not in a 100 meter run.

Of course, your analogy is valid. I just thought people here might find the human-horse races interesting. I heard a talk by Dr. Lieberman a couple of months ago (where he explained the importance of the trot-gallop transition) and I found it really amusing.

I found it very interesting. My current dog "Odie" is a 15 pound Carin Terrier (like Toto on the wizard of oz) and although she is full of energy and loves to run, I noticed one day that I can out-sprint her. Of course small dogs cannot run very fast even though they look really fast. But it was interesting to me that one day a neighbor asked to take Odie on her walk, and she reported to us that she had to carry the dog home. At some point the dog stopped and refused to continue! When I take her on short walks she tries to take the lead, pulling me all the way - although I have been recently training her not to do that. It may be that pulling that hard constantly eventually tired her out and for such a small dog she can pull pretty hard.

[Milos]

Of course I was primarily talking about very short distances with my analogy. I could have used the Cheeta as an analogy too, we can clearly outrun Cheeta's at long distances but not in a 100 meter run.

Well it's only the matter of angle you look upon things.
If you change it a bit, then it's safe to claim that humans are the fastest existing creature on Earth at any distance longer than 200m. And it would be valid claim for using its own and only its own power to move.
Humans on race bikes are faster than cheetahs (fastest living creature on short tracks) on more than 200m track.

[Don]

Of course I was primarily talking about very short distances with my analogy. I could have used the Cheeta as an analogy too, we can clearly outrun Cheeta's at long distances but not in a 100 meter run.

Well it's only the matter of angle you look upon things.
If you change it a bit, then it's safe to claim that humans are the fastest existing creature on Earth at any distance longer than 200m. And it would be valid claim for using its own and only its own power to move.
Humans on race bikes are faster than cheetahs (fastest living creature on short tracks) on more than 200m track.

It may be that we, or some other animal, is the most energy efficient creature on the earth. I wonder if you compute how much food (calorie energy) is required per pound per mile, which creature is the most efficient?