Gamebit is a chess program that does not limit the search depth a priori. Some of its concepts could be reused for other games using search trees such as Backgammon, Go, etc. The name Gamebit comes from "game", "bit", and "gambit", which means temporary sacrifice.
We know that the number of positions of sequential games grows exponentially and cannot be analyzed thoroughly unless the search depth is limited. However, it is not a good idea to do that, because sooner or later, the chess program could miss some important moves ahead. Since it is impossible to go deep forever, the problem we face up to is "when is it important to go deeper?", or similarly "when is it safe to stop the exploration"?.
Most chess programs would simply perform a uniform exhaustive search to avoid having to deal with heuristic criterion. In this respect, they cannot tell the difference between a direct error losing precious material, and a subtle sacrifice that would pay off a few moves later. The only way to be sure is to analyze deeply all non-promising moves just in case they would unexpectedly lead to a winning situation. In other words, 99.99% of the chess position evaluations are completely irrelevant as if they were randomly played, but unlike humans, most computer programs are forced either to go uselessly deeper, or to take a chance by cutting the search tree resulting from recursive analysis.
Gamebit is meant to mimic the way humans think, and its heuristic stopping the analysis is extremely reliable.
Of course, it can still make mistakes, but it doesn't take any chance, and shall continue the analysis as long as there is doubt no matter the search depth and the position value. Even if it doesn't have any a-priori depth limit or value clamping, Gamebit is still able to tell the difference between a direct error and a subtle sacrifice. But what a sacrifice is exactly? A sacrifice is a move with a negative value, but that puts the board in a state of uncertainty. It means that it looks like a lost at first, but since the board is not stable, one doesn't know all the impacts of all the moves and some more exploration is necessary. A direct error, on the other hand, is a move with a negative value, but that keeps the board stable, and we conclude quickly the move is not worth further analysis. It leaves us with the question: "how can we evaluate the stability of a chess position?", and this is exactly what Gamebit is meant to address.
A chess program can beat amateurs quite easily because it won't make obvious mistakes like humans. A computer program is like a calculator, it cannot fail if you ask for the square root of 2. But at the same time, it will always fail to give you the exact answer because the square root of 2 has infinitely many digits. However, humans are smart and can see on the long run what a computer can not.
We compared Gamebit with the very mature GNU chess. Of course, Gamebit used to lose almost all the time for many reasons. Since the GNU chess is highly optimized, it runs 1000 times faster. But even in this case, Gamebit is a serious challenger. Why? Because the GNU chess has to analyze 1000 more positions uselessly. And this is the key.
We think Gamebit sooner or later will analyze millions of times less random positions than most other programs. As a result, it could beat any other programs, because its core concept is different and can still be optimized as much as the other programs, when running on the same CPU. Even if it is quite slow (Java), Gamebit did beat the very powerful GNU chess once, sure only once, but still once. What does that mean?
It shows the reliability of the Gamebit pruning mechanism as it found a winning move that the GNU chess just missed. Even though Gamebit runs 1000 times slower and visited 1000 times less positions, it explored even MORE promising combinations because it found a winning path without missing ANY possible counter attack from the much more powerful GNU chess program!
We hope that the community of Noa will help for Gamebit to compare with most chess programs regularly, instead of winning only once in a while thanks to lucky situations. The algorithm behind Gamebit is quite simple and easy to understand. It could open some doors in chess theory, because it is about something that no human nor computer has ever done before: IN-DEEP SACRIFICE EXPLORATION! It could result in extremely exciting games where players are willing to lose a great deal of material in exchange of positional advantages that would inevitably pay off 10-20 moves later!
You can download the program and try it!
Example of a debugging mode showing the safe squares of all pieces.