ISSN:0824-7935    

DOI:10.1111/j.1467-8640.1996.tb00249.x

出版商:Blackwell Publishing Ltd    

年代:1996

数据来源: WILEY

摘要:

Many decades ago, Japanese professional Go‐Moku players stated that Go‐Moku (five‐in‐a‐row on a horizontally placed 15×15 board) is a won game for the player to move first. So far, this claim has never been substantiated by (a tree of) variations or by a computer program. Meanwhile, many variants of Go‐Moku with slightly different rules have been developed. This paper shows that for two common variants, the game‐theoretical value has been established.Moreover, the Go‐Moku program Victoria is described. It uses two new search techniques: threat‐space search and proof‐number search. One of the results is that Victoria is bound to win against any (optimal) counterplay if it moves first. Furthermore, it achieves good results as a defender against nonoptimally playing opponents. In this contribution we focus on threat‐space search and its advantages compared to conventi

ISSN:0824-7935    

DOI:10.1111/j.1467-8640.1996.tb00250.x

出版商:Blackwell Publishing Ltd    

年代:1996

数据来源: WILEY

摘要:

The game of Nine Men's Morris is a draw. We obtained this result using a combination of endgame databases (1010states) and search. Our improved algorithm for computing endgame databases allowed the game to be solved on a personal computer. Other games have been solved using knowledge‐based methods to dramatically prune the search tree. Nine Men's Morris does not seem to profit from such methods, making it the first nontrivial game solved in which almost the entire state space has to be considere

ISSN:0824-7935    

DOI:10.1111/j.1467-8640.1996.tb00251.x

出版商:Blackwell Publishing Ltd    

年代:1996

数据来源: WILEY

摘要:

Since Samuel's work on checkers over thirty years ago, much effort has been devoted to learning evaluation functions. However, all such methods are sensitive to the feature set chosen to represent the examples. If the features do not capture aspects of the examples significant for problem solving, the learned evaluation function may be inaccurate or inconsistent. Typically, good feature sets are carefully handcrafted and a great deal of time and effort goes into refining and tuning them. This paper presents an automatic knowledge‐based method for generating features for evaluation functions. The feature set is developed iteratively: features are generated, then evaluated, and this information is used to develop new features in turn. Both the contribution of a feature and its computational expense are considered in determining whether and how to develop it further.This method has been applied to two problem‐solving domains: the Othello board game and the domain of telecommunications network management. Empirical results show that the method is able to generate many known features and several novel features and to improve concept accuracy in both doma

ISSN:0824-7935    

DOI:10.1111/j.1467-8640.1996.tb00252.x

出版商:Blackwell Publishing Ltd    

年代:1996

数据来源: WILEY

摘要:

It is believed that chess masters use pattern‐based knowledge to analyze a position, followed by a pattern‐based controlled search to verify or correct the analysis. This paper describes a first‐order system called PAL that can learn patterns in the form of Horn clauses from simple example descriptions and general purpose knowledge. It is shown how PAL can leam chess patterns that are beyond the learning capabilities of current inductive systems. The patterns learned by PAL can be used for analysis of positions and for the construction of playing strategies. By taking the learned patterns as attributes for describing examples, a set of rules which decide whether a Pawn can safely be promoted without moving the King in a King and Pawn vs King endgame, is automatically constructed with a similarity‐based learning algorithm. Similarly, a playing strategy for the King and Rook vs King endgame is automatically constructed with a simple learning algorithm by following traces of games and using the patterns learned by PAL. Limitations of first‐order systems, PAL imparticularly, are exposed in domains where a large number of background definitions may be required for induction. Conclusions and future research directions

ISSN:0824-7935    

DOI:10.1111/j.1467-8640.1996.tb00253.x

出版商:Blackwell Publishing Ltd    

年代:1996

数据来源: WILEY

摘要:

Human chess players exhibit a large variation in the amount of time they allocate for each move. Yet, the problem of devising resource allocation strategies for game playing has not received enough attention. In this paper we present a framework for studying resource allocation strategies. We define allocation strategy and identify three major types of strategies: static, semi‐dynamic, and dynamic. We then describe a method for learning semi‐dynamic strategies from self‐generated examples. We present an algorithm for assigning classes to the examples based on the utility of investing extra resources. The method was implemented in the domain of checkers, and experimental results show that it is able to learn strategies that improve game‐playing perf

ISSN:0824-7935    

DOI:10.1111/j.1467-8640.1996.tb00254.x

出版商:Blackwell Publishing Ltd    

年代:1996

数据来源: WILEY

摘要:

Although game‐tree search works well in perfect‐information games, it is less suitable for imperfect‐information games such as contract bridge. The lack of knowledge about the opponents’ possible moves gives the game tree a very large branching factor, making it impossible to search a significant portion of this tree in a reasonable amount of time.This paper describes our approach for overcoming this problem. We represent information about bridge in a task network extended to represent multi‐agency and uncertainty. Our game‐playing procedure uses this task network to generate game trees in which the set of alternative choices is determined not by the set of possible actions, but by the set of available tactical and strategic schemes.We have tested this approach on declarer play in the game of bridge, in an implementation calledTignum 2.On 5000 randomly generated notrump deals, Tignum 2 beat the strongest commercially available program by 1394 to 1302, with 2304 ties. These results are statistically significant at the α= 0.05 level. Tignum 2 searched an average of only 8745.6 moves per deal in an average time of only 27.5 seconds per deal on a Sun SPARCstation 10. Further enhancements to Tignum 2 are curren

ISSN:0824-7935    

DOI:10.1111/j.1467-8640.1996.tb00255.x

出版商:Blackwell Publishing Ltd    

年代:1996

数据来源: WILEY

摘要:

Games withimperfect information arean interesting and important class of games. They include most card games (e.g., bridge and poker) as well as many economic and political models. Here we investigate algorithms for findi ng the simplest form of a solution (a pure‐strategy equilibrium point) to imperfect information games expressed in their extensive (game tree) form. We introduce to the artificial intelligence community a classic algorithm, due to Wilson, that solves one‐player games with perfect recall. Wilson's algorithm, which we call iMP‐minimax, runs in time linear in the size of the game‐tree searched. In contrast to Wilson's result, Koller and Meggido have shown that finding a pure‐strategy equilibrium point in one‐player gameswithoutperfect recall isNP‐hard. Here, we provide another contrast to Wilson's result–we show that in gameswithperfect recall but more than one player, finding a pure‐strategy equilibrium point, given that such an equilibrium point exists, isNP‐hard.Our second contribution is to present a pruning technique for Wilson's IMP‐minimax algorithm to make the latter more tractable. We call this new algorithm IMP‐alpha‐beta. We provide a theoretical framework (model) and analyze IMP‐alpha‐beta in that model. IMP‐alpha‐beta is of direct value for one‐player, perfect‐recall games. It also has strong potential for other imperfect information games, as it is a natural (but as y

ISSN:0824-7935    

DOI:10.1111/j.1467-8640.1996.tb00256.x

出版商:Blackwell Publishing Ltd    

年代:1996

数据来源: WILEY

摘要:

This paper provides a blueprint for the development of a fully domain‐independent single‐agent and multiagent heuristic search system. It gives a graph‐theoretic representation of search problems based on conceptual graphs and outlines two different learning systems. One, an “informed learner”, makes use of the graph‐theoretic definition of a search problem or game in playing and adapting to a game in the given environment. The other, a “blind learner”, is not given access to the rules of a domain but must discover and then exploit the underlying mathematical structure of a given domain. Relevant work of others is referenced within the context of the blueprint.To illustrate further how one might go about creating general game‐playing agents, we show how we can generalize the understanding obtained with the Morph chess system to all games involving the interactions of abstract mathematical relations. A monitor for such domains has been developed, along with an implementation of a blind and informed learning system known as Morphll. Performance results with MorphK are preliminary but encouraging and provide a few more data points with which to understand and evalu

ISSN:0824-7935    

DOI:10.1111/j.1467-8640.1996.tb00257.x

出版商:Blackwell Publishing Ltd    

年代:1996

数据来源: WILEY

摘要:

This paper introduces METAGAMER, the first program designed within the paradigm of Metagame‐playing (Metagame). This program plays games in the class of symmetric chess‐like games, which includes chess, Chinese chess, checkers, draughts, and Shogi. METAGAMER takes as input therulesof a specific game and analyzes those rules to construct an efficient representation and an evaluation function for that game; they are used by a generic search engine. The strategic analysis performed by METAGAMER relates a set of general knowledge sources to the details of the particular game. Among other properties, this analysis determines the relative value of the different pieces in a given game. Although METAGAMER does not learn from experience, the values resulting from its analysis are qualitatively similar to values used by experts on known games and are sufficient to produce competitive performance the first time METAGAMER plays a new game. Besides being the first Metagame‐playing program, this is the first program to have derived useful piece values directly from analysis of the rules of different games. This paper describes the knowledge implemented in METAGAMER, illustrates the piece values METAGAMER derives for chess and checkers, and discusses experiments with METAGAMER on both existing and newly generated

ISSN:0824-7935    

DOI:10.1111/j.1467-8640.1996.tb00258.x

出版商:Blackwell Publishing Ltd    

年代:1996

数据来源: WILEY