The chessmaps heuristic is a pattern-oriented approach to ordering moves for the game of chess. It uses a neural network to learn a relation between the control of the squares and the influence of a ...move. Depending on what squares a player controls, the chessmaps heuristic tries to determine where the important areas of the chessboard are. Moves that influence these important areas are then ordered first. The heuristic has been incorporated into a move-ordering algorithm that also takes account of immediate tactical threats. Human players also rely strongly on patterns when selecting moves, but would also consider immediate tactical threats, so this move-ordering algorithm is an attempt to mimic something of the human thought process when selecting a move. This paper presents a new definition for the influence of a move, which improves the performance of the heuristic. It also presents a new experience-based approach to determining what areas of the chessboard are important, which may actually be preferred to the chessmaps heuristic. The results from game-tree searches suggest that the move-ordering algorithm could compete with the current best alternative of using the history heuristic with capture moves in a brute-force search.
The point of game tree search is to insulate oneself from errors in the evaluation function. The standard approach is to grow a full width tree as deep as time allows, and then value the tree as if ...the leaf evaluations were exact. The alpha-beta algorithm implements this with great computational efficiency. This approach has been effective in many games. Our approach is to form a Bayesian model of our uncertainty. We adopt an evaluation function that returns a probability distribution estimating the probability of various errors in valuing each position. These estimates are obtained by training from data. We thus use additional information at each leaf not available to the standard approach. We utilize this information in three ways: to evaluate which move is best after we are done expanding, to allocate additional thinking time to moves where additional time is most relevant to game outcome, and, perhaps most importantly, to expand the tree along the most relevant lines. Our measure of the relevance of expanding a given leaf provably approximates a measure of the impact of expanding the leaf on expected payoff, including the impact of the outcome of the leaf expansion on later expansion decisions. Our algorithms run (under reasonable assumptions) in time linear in the size of the final tree and hence except for a small constant factor, are as time efficient as alpha-beta. Our algorithm focuses on relevant lines, on which it can in principle grow a tree several times as deep as alpha-beta in a given amount of time.
We have tested our approach on a variety of games, including Othello, Kalah, Warri, and others. Our probability independence approximations are seen to be significantly violated, but nonetheless our tree valuation scheme was found to play significantly better than minimax or the Probability Product rule when both competitors search the same tree. Our full search algorithm was found to outplay a highly ranked, directly comparable alpha-beta Othello program even when the alpha-beta program was given sizeable time odds, and also performed well against the three top Othello programs on the Internet Othello Server.
This paper presents details of the chess mate solver application, which is a part of the author?s Geniss general chess application. The problem chess is an important domain connected with solving of ...the chess problems. The Geniss Mate Solver (G.M.S.) application solves Mate-in-N-move problems. Main techniques used for the implementation of the application are full-width searching with Alpha-Beta pruning technique and zero evaluation function. The application is written in Delphi for Windows programming environment and the searching engine is completely coded in assembly language (about 10000 lines). This hybrid software structure enables efficient program development by using high-level programming environment and the realization of a very fast searching engine at the same time. The machine code is manually coded and could achieve above 7 million generated positions per second on the 1Ghz Celeron PC.
Siguo game is an interesting test-bed for artificial intelligent research. It is a game of imperfect information, where completing players must deal with possible knowledge, risk assessment, and ...possible deception and leaguing players have to deal with cooperation and information signal transmission. Since Siguo game is imperfect information game that the player doesn’t know the type of piece and strategy that opponent moves, to exactly guess type of opponent’ piece is a very important parameter to evaluate the capability of Siguo game program. In this paper, we first construct a fuzzy type table by analyzing more than one thousand different embattle lineups (i.e. chess manuals) of Siguo game, and then we present a algorithm that updates type table by using information from opponent during playing game. The updating type of pieces algorithm is designed by considering the two strategies, i.e. optimism and pessimism based on the fuzzy notion. At last we give a method to guess the type of piece by using fuzzy type proximity relation between two neighboring pieces.
The performance of consultation methods, i.e., majority voting, the optimistic selection rule, and the pseudo-random number (PRN) ensemble method, are examined in computer chess using 2180 chess ...problems. Here, the optimistic selection rule selects a program that returns the highest search value, and the PRN ensemble consists of multiple individual copies of one base program, and each copy is diversified by adding random numbers to the evaluation function of the base program. We carried out empirical experiments by using state-of-the-art chess-program Crafty as the base program. We found that the percentage of correct answers increased from 55.6 to 57.1% using optimistic selection from the PRN ensemble. The experimental results indicated that the consultation methods allowed simple yet effective distributed computing in chess.
This paper presents the Candidate Moves Method for parallelization of the MiniMax search procedure. As the framework for this new method the basic MiniMax procedure is defined. The original ...modification of the classic MiniMax procedure is presented in detail. All of these theoretical results and novelties are successfully implemented and verified in authors' chess application Achilles, which is the cluster version of the Axon chess engine.
Humanity 2, Computers 0 Waldrop, M. Mitchell
Science (American Association for the Advancement of Science),
11/1989, Letnik:
246, Številka:
4930
Journal Article
B ∗ probability based search Berliner, Hans J.; McConnell, Chris
Artificial intelligence,
09/1996, Letnik:
86, Številka:
1
Journal Article
Recenzirano
Odprti dostop
We describe a search algorithm for two-player games that relies on selectivity rather than brute-force to achieve success. The key ideas behind the algorithm are:
1.
(1) stopping when one alternative ...is clearly better than all the others, and
2.
(2) focusing the search on the place where the most progress can likely be made toward stopping.
Critical to this process is identifying uncertainty about the ultimate value of any move. The lower bound on uncertainty is the best estimate of the real value of a move. The upper bound is its optimistic value, based on some measure of unexplored potential. This provides an
I-have-optimism-that-needs-to-be-investigated attitude that is an excellent guiding force. Uncertainty is represented by probability distributions. The search develops those parts of the tree where moving existing bounds would be most likely to succeed and would make the most progress toward terminating the search. Termination is achieved when the established real value of the best move is so good that the likelihood of this being achieved by any other alternative is minimal.
The B
∗ probability based search algorithm has been implemented on the chess machine Hitech.
En route we have developed effective techniques for:
•
• producing viable optimistic estimates to guide the search,
•
• producing cheap probability distribution estimates to measure goodness,
•
• dealing with independence of alternative moves, and
•
• dealing with the graph history interaction problem.
The report describes the implementation, and the results of tests including games played against brute-force programs. Test data indicate that B
∗ Hitech is better than any searcher that expands its whole tree based on selectivity. Further, analysis of the data indicates that should additional power become available, the B
∗ technique will scale up considerably better than brute-force techniques.
PDF
