3

Are there chess engines that carry out brute force search, looking at all possible moves to each depth? An engine like this could be used to generate for solutions to tactical puzzles where the key move gets pruned by engines with selective search.

closed as unclear what you're asking by Salvador Dali, Rauan Sagit, Jonathan Garber, AlwaysLearningNewStuff, Lily Chung May 1 '14 at 4:44

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • You need to define your criteria better, if it also looks for material advantage then it's apparently doing a positional evaluation, and I wouldn't call that "pure brute force" anymore. There are also engines specializing in solving problems, but I don't know if they are "pure brute force". – RemcoGerlich Apr 14 '14 at 11:27
  • If it's looking for material advantage, it should only count the pieces on the board with their standard values. Not much calculations there. Basically, just to test if every possible outcome is good for one side. An "engine" that just checks for mate would meet the criteria as well. – chaosflaws Apr 14 '14 at 11:30
  • A pure brute force engine would not be very strong due to its inability to weed out unpromising lines, and therefore, would be lacking depth. However, I am sure that someone has a project on github, that does just that: brute force chess engine. – Akavall Apr 15 '14 at 0:52
  • On the other hand, pruning is not very helpful when you are trying to find out with absolute certainty that a certain position is won/lost. – chaosflaws Apr 15 '14 at 5:51
  • Answer: Rybka Winfinder and the Tactical mode of Houdini were designed for use in solving problems, and will examine a wider range of lines than most engines. – A passerby Sep 30 '15 at 12:45
1

The answer is yes and no.

http://www.gamedev.net/page/resources/_/technical/artificial-intelligence/chess-programming-part-iv-basic-search-r1171 Has a pretty good explanation on how chess engine works.

In Chess, for example, a typical branching factor in the middle game would be about 35 moves. That is, after every move, there will be around 35 possible valid moves.

Using a "smart brute force algorithm" (aka Min-Max search), the time complexity of the algorithm is O( B^n ). That is, you need around that B^n operations n-ply search.

An 8-ply search of a chess position would need to explore about 1.5 million possible paths! That is a LOT of work. Adding a ninth ply would make the tree balloon to about 50 million nodes, and a tenth, to an impossible 1.8 billion! A typical game has 30-40 moves, so you will need to search for 30^35 - 40^35 positions.

Assuming your CPU is running at 3GHz, and it takes only one clock cycle to analyze one position, it will take more than 1x10^42 years to complete the search. So short answer is no.

However, endgames with small number of pieces have been thoroughly analyzed, and can be determined if mate is possible. By August 2012, tablebases had solved chess for every position with up to seven pieces (According to wiki http://en.wikipedia.org/wiki/Endgame_tablebase)

Not the answer you're looking for? Browse other questions tagged or ask your own question.