New Search Method(s)

[Bo Persson]

It's time to head in another direction for search methods. Alpha/Beta has been milked dry. The human mind is the most powerful "computer"... why not try to be like it with computer chess?

When asked how many moves ahead Kasparov can think, he replied that it depended on the positions of the pieces. "Normally, I would calculate three to five moves," he said. "You don't need more.... But I can go much deeper if it is required." For example, in a position involving forced moves, it's possible to look ahead as many as 12 or 14 moves, he noted.

The normal GM searches a few moves per second, while a chess engine searches millions per second. See the difference?

There are tons of differences. Humans run on coffee and hamburgers, computers on electricity.

Humans still enjoy competing running marathons, even though I could beat them on my bike. Why?


If you really want the computer to play like a human, you should create a patterns matching, self learning program, and let it practice for 20 years. That's how the human did it!

[bob]

Easy question to answer: Because we don't have a clue about _how_ the human mind makes chess decisions. This has been repeatedly studied, best known example was De Groot's "Thought and choice in chess" book. Until we know how a human chooses a move, emulating that process is going to be a bit on the difficult side. It appears to me that alpha/beta is doing just fine, however, since humans can not keep up.

As a chess player, those are somethings I look for (e.g.).

Go to a chess board right now.

Look at the starting setup....

What is your plan?
----------------------------------------------------------------
Opening:

How shall I start my conquest?
What square / piece / move am I describing?

I am playing white.
I like to take center control with pawns early.
I like to develop my queen side first 60% of the time.
I do not like to move my a || b || f || g || h pawns early.
I lost my last game against this opponent playing white & with a variation of the English Opening, try something new.
I don't like the King Pawn Openings very well unless I am playing black.

----------------------------------------------------------------
Middle game:

Are any of my pieces being attacked?
Can I move away, block, or capture an attacker?
Am I able to defend or support an attack(er)?
Am I able to chase away an opposing piece?
Do I want to exchange pieces?
Should I sacrifice 1 rook for a bishop && knight?
Can I pin, skewer, or fork my opponent?
Are any of my pieces pinned, skewered, forked?
Is there discovery check or attack?
Can I make a discovery attack?
Do I have any weak pieces?
Can I improve my weak piece?
Did my opponent castle?
Can my opponent castle?
Can I stop my opponent from castling?
How safe is my king?
What side is the opponent's king on?
Why am I making this move?
Can my opponent exploit this move?
What do you think the opponent will respond with?
-----------------------------------------------------------------
End game:

Is my king safe?
Do I have any advanced pawns
Can I promote?
What should I promote too?
Can my opponent stop promotion?
Is there a Zugzwang?
Can I draw?
Can I checkmate?
----------------------------------------------------------------
Develop functions to answer/know what all these questions/ statements are.
----------------------------------------------------------------

Or just settle with Alpha-Beta??!

Indeed, A. De Groot was famous for some thesis/ studies.

The 4 Phases of chess amateurs to masters:

1) Orientation: assessing the situation, and determine a very general idea of what to next.
2) Exploration: looking at some branches of the game tree.
3) Investigation: choose a probable best move.
4) Proof: confirming the results of the investigation were valid.

"De Groot found that much of what is important in choosing a move occurs during the first few seconds of exposure to a new position. (Wiki)"

If everyone stuck with DOS, where would Windows 7 or Linux be?

That is all _very_ simplistic, and unfortunately no one has yet come even close to figuring out how a human does much of what you suggest. Much more important is "how do you narrow the list of moves you consider down to 2 or 3 at the most? That will take a lifetime to answer. And that is just one question out of many that we (as humans) can answer quickly, without knowing _how_ we answer it quickly. Until we do, implementation in a chess engine is impossible.

[Don]

Joshua,

Alpha/beta is the primary tool HUMANS use to reason on chess positions, I think your idea that it has outlived its usefulness is very wrong.

Not only that, but computers have gotten much closer to how humans think over time, not farther away. Todays program are far more selective than they ever were.

I don't think you can criticize the fact that it is possible for computers to calculate variations far faster than humans - that should not be viewed as a weakness.

It's not clear to me that the way humans do things is always the best way in the universe to do all things for all entities. In fact the way one human does something may be best for him, but not for you.

Trying to make the computer in our image even though it has totally different characteristics can only be taken so far. When you consider that computers are now better than US at chess, do you think it's logical that we should abandon how we play chess and try to learn to imitate the computers way? Why should the superior player try to imitate the inferior player?

It's time to head in another direction for search methods. Alpha/Beta has been milked dry. The human mind is the most powerful "computer"... why not try to be like it with computer chess?

When asked how many moves ahead Kasparov can think, he replied that it depended on the positions of the pieces. "Normally, I would calculate three to five moves," he said. "You don't need more.... But I can go much deeper if it is required." For example, in a position involving forced moves, it's possible to look ahead as many as 12 or 14 moves, he noted.

The normal GM searches a few moves per second, while a chess engine searches millions per second. See the difference?

Search()->

30+ conditions for root.

Conditions:

What type of move are you?

1) Developing (including castling)
2) Exchange
3) Sacrafice
4) Fork
5) Pin
6) Discovery (check, attack)
7) Skewer
8) Tempo
9) Mate (Threat)
10) Draw (Repeat)
11) Mobility
12) Positional
13) Attacking
14) Defensive/Protective
15) Capture
16) Open rank
17) Open file
18) Open diagonal
19) Castled or Not Castled or Capable of Castling
20) Castling stopping
21) Controling squares
22) Attacking squares
23) Free squares
24) Occupied squares
25) King Safety
26) Safe/Retreat squares
27) Supporting
28) Attack Supporting
29) Capture Supporting
30) Pin Supporting
31) Center Control
32) Other

Order your root move based on the total count of conditions met, bonus, penalty, etc.

To be more successful at Chess, an engine or individual should take these conditions into consideration for a move. Planning is a key to winning. Design & develop a search for just the 3 basic attacks would be a good place to start (forks, pins, & skewers). This will lead to the removal of piece table scores, and if done correctly, alpha/beta. Also, more human-like play will occur.

This would be a step forward for chess.

[rbarreira]

Not only that, but computers have gotten much closer to how humans think over time, not farther away. Todays program are far more selective than they ever were.

I think a big part of the problem is that when man vs machine matches happen, the ever-present meme is that the machine is using "brute force" (cue the over-simplified explanation that the computer is looking at every move on the board, and then every answer to that move, etc etc.).

As we all know, alpha-beta with null-move, LMR and quiescence (etc etc) is far from being a brute-force method. I'm not insinuating that the thread creator doesn't know how it really works, but this wrong meme does have its impact even on people who know better.

[michiguel]

Joshua,

Alpha/beta is the primary tool HUMANS use to reason on chess positions, I think your idea that it has outlived its usefulness is very wrong.

That is what Kotov wanted us to believe in "Think like a Grandmaster", which was useful up to a point. However, that dogmatic concept was refuted by Nunn and Tisdall. The fact that we do not use alpha beta explain why at certain endgames we excelled while engines are still not that great. We use alpha beta some situations, though.

Miguel

Not only that, but computers have gotten much closer to how humans think over time, not farther away. Todays program are far more selective than they ever were.

I don't think you can criticize the fact that it is possible for computers to calculate variations far faster than humans - that should not be viewed as a weakness.

It's not clear to me that the way humans do things is always the best way in the universe to do all things for all entities. In fact the way one human does something may be best for him, but not for you.

Trying to make the computer in our image even though it has totally different characteristics can only be taken so far. When you consider that computers are now better than US at chess, do you think it's logical that we should abandon how we play chess and try to learn to imitate the computers way? Why should the superior player try to imitate the inferior player?

It's time to head in another direction for search methods. Alpha/Beta has been milked dry. The human mind is the most powerful "computer"... why not try to be like it with computer chess?

When asked how many moves ahead Kasparov can think, he replied that it depended on the positions of the pieces. "Normally, I would calculate three to five moves," he said. "You don't need more.... But I can go much deeper if it is required." For example, in a position involving forced moves, it's possible to look ahead as many as 12 or 14 moves, he noted.

The normal GM searches a few moves per second, while a chess engine searches millions per second. See the difference?

Search()->

30+ conditions for root.

Conditions:

What type of move are you?

1) Developing (including castling)
2) Exchange
3) Sacrafice
4) Fork
5) Pin
6) Discovery (check, attack)
7) Skewer
8) Tempo
9) Mate (Threat)
10) Draw (Repeat)
11) Mobility
12) Positional
13) Attacking
14) Defensive/Protective
15) Capture
16) Open rank
17) Open file
18) Open diagonal
19) Castled or Not Castled or Capable of Castling
20) Castling stopping
21) Controling squares
22) Attacking squares
23) Free squares
24) Occupied squares
25) King Safety
26) Safe/Retreat squares
27) Supporting
28) Attack Supporting
29) Capture Supporting
30) Pin Supporting
31) Center Control
32) Other

Order your root move based on the total count of conditions met, bonus, penalty, etc.

To be more successful at Chess, an engine or individual should take these conditions into consideration for a move. Planning is a key to winning. Design & develop a search for just the 3 basic attacks would be a good place to start (forks, pins, & skewers). This will lead to the removal of piece table scores, and if done correctly, alpha/beta. Also, more human-like play will occur.

This would be a step forward for chess.

[Tord Romstad]

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.

[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.

[rbarreira]

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).

[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 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.

The issue here is not forward pruning. If you are doing a 20 ply search but a significant part of the tree never gets past 5 ply, you have a highly selective program. If you do forward pruning, you have some criteria for doing so and it doesn't matter if it is a highly abbreviated search or a sophisticated static evaluation, the fact of the matter is that you are "selecting" which moves to focus on, hence "selective search."

I know that this is a matter of semantics, but if BF=2 is not selective, it's hard to imagine what is. The answer seems to be that whatever we are currently doing is brute force regardless of what it is. It's like a magic trick, once you know how it's done, it loses it's mystery. If it's not difficult to understand it must be "brute force."

Let me put it this way. Replace null move pruning and LMR with a "black box" function that determines whether you should look at a move or reject it. And this black box function is an order of magnitude faster than searching the position. Would this be a selective program or a brute force program?

[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. 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...