View Item 

Show simple item record

PERFECT RECALL AND PRUNING IN GAMES WITH IMPERFECT INFORMATION 1
dc.contributor.authorBlair, Jean R. S.en_US
dc.contributor.authorMutchler, Daviden_US
dc.contributor.authorLent, Michaelen_US
dc.date.accessioned2010-06-01T19:51:16Z
dc.date.available2010-06-01T19:51:16Z
dc.date.issued1996-02en_US
dc.identifier.citationBlair, Jean R. S.; Mutchler, David; Lent, Michael (1996). "PERFECT RECALL AND PRUNING IN GAMES WITH IMPERFECT INFORMATION 1 ." Computational Intelligence 12(1): 131-154. <http://hdl.handle.net/2027.42/72986>en_US
dc.identifier.issn0824-7935en_US
dc.identifier.issn1467-8640en_US
dc.identifier.urihttps://hdl.handle.net/2027.42/72986
dc.format.extent1604704 bytes
dc.format.extent3109 bytes
dc.format.mimetypeapplication/pdf
dc.format.mimetypetext/plain
dc.publisherBlackwell Publishing Ltden_US
dc.rights1996 Blackwell Publishing Ltden_US
dc.subject.otherGame Treeen_US
dc.subject.otherImperfect Informationen_US
dc.subject.otherPerfect Recallen_US
dc.subject.otherHeuristic Searchen_US
dc.subject.otherPruningen_US
dc.subject.otherAlpha-betaen_US
dc.subject.otherIMP-minimaxen_US
dc.subject.otherIMP-alpha-Betaen_US
dc.subject.otherNP -Harden_US
dc.subject.otherNP -Completeen_US
dc.titlePERFECT RECALL AND PRUNING IN GAMES WITH IMPERFECT INFORMATION 1en_US
dc.typeArticleen_US
dc.subject.hlbsecondlevelComputer Scienceen_US
dc.subject.hlbtoplevelEngineeringen_US
dc.description.peerreviewedPeer Revieweden_US
dc.contributor.affiliationumDepartment of Electrical Engineering and Computer Science, University of Michigan, Ann Arbor, MI 48109 vanlent@eecs.umich.eduen_US
dc.contributor.affiliationotherDepartment of Electrical Engineering and Computer Science, United States Military Academy, West Point, NY 10996 blair@eecsl.eecs.usma.eduen_US
dc.contributor.affiliationotherDepartment of Computer Science, Rose-Hulman Institute of Technology, 5500 Wabash Avenue, Terre Haute, IN 47803-3999 mutchler@cs.rose-hulman.eduen_US
dc.description.bitstreamurlhttp://deepblue.lib.umich.edu/bitstream/2027.42/72986/1/j.1467-8640.1996.tb00256.x.pdf
dc.identifier.doi10.1111/j.1467-8640.1996.tb00256.xen_US
dc.identifier.sourceComputational Intelligenceen_US
dc.identifier.citedreferenceAho, A. V., J. E. Hopcroft, and J. D. Ullman. 1983. Data structures and algorithms. Addison-Wesley, Reading, MA.en_US
dc.identifier.citedreferenceAnantharaman, T., M. S. Campbell, and F. Hsu. 1990. Singular extensions: adding selectivity to brute-force searching. Artificial Intelligence, 43 ( 1 ): 99 – 109.en_US
dc.identifier.citedreferenceBallard, B. W. 1983. The *-minimax search procedure for trees containing chance nodes. Artificial Intelligence, 21 ( 1,2 ): 327 – 350.en_US
dc.identifier.citedreferenceBampton, H. 1994. Solving imperfect information games using the Monte Carlo heuristic. Master's thesis, University of Tennessee.en_US
dc.identifier.citedreferenceBarr, D. 1992. Experiments in heuristic search utilizing sampling and precomputation. Master's thesis, University of Tennessee.en_US
dc.identifier.citedreferenceBerliner, H. J. 1980. Backgammon computer program beats world champion. Artificial Intelligence, 14 ( 2 ): 205 – 220. Reprinted in Computer Games I. Edited byD. N. L. Levy. Springer-Verlag, New York, 1988.en_US
dc.identifier.citedreferenceBlair, J. R. S. and D. Mutchler. 1995. Pure-strategy equilibria in the presence of imperfect information– NP-hard problems. Technical Report 95-02, Department of Computer Science, Rose-Hulman Institute of Technology.en_US
dc.identifier.citedreferenceBlair, J. R. S., D. Mutchler, and C. Liu. 1992. Heuristic search in one-player games with hidden information. Technical Report CS-92-162, Department of Computer Science, University of Tennessee.en_US
dc.identifier.citedreferenceFindler, N. V. 1977. Studies in machine cognition using the game of poker. Communications of the ACM, 20 ( 4 ): 230 – 245.en_US
dc.identifier.citedreferenceGamback, B., M. Rayner, and B. Pell. 1991. An architecture for a sophisticated mechanical bridge player. In Heuristic programming in artificial intelligence–the second computer olympiad. Edited by D. N. L. Levy and D. F. Beal. Ellis Horwood Limited, Chichester, England, pp. 87 – 107.en_US
dc.identifier.citedreferenceGambÄck, B., M. Rayner, and B. Pell. 1993. Pragmatic reasoning in bridge. Technical Report 299, Computer Laboratory, University of Cambridge.en_US
dc.identifier.citedreferenceGarey, M. R. and D. S. Johnson. 1979. Computers and intractability: a guide to the theory of NP-completeness. W. H. Freeman, San Francisco.en_US
dc.identifier.citedreferenceGordon, S. 1993. A comparison between probabilistic search and weighted heuristics in a game with incomplete information. In Games: planning and learning, papers from the 1993 Fall Symposium, Raleigh, NC, pp. 77- 83. AAAI Press Technical Report FS-93-02, Menlo Park, CA.en_US
dc.identifier.citedreferenceKnuth, D. E. and R. W. Moore. 1975. An analysis of alpha-beta pruning. Artificial Intelligence, 6 ( 4 ): 293 – 326.en_US
dc.identifier.citedreferenceRoller, D. and N. Megiddo. 1992. The complexity of two-person zero-sum games in extensive form. Games and Economic Behavior, 4 ( 4 ): 528 – 552.en_US
dc.identifier.citedreferenceRoller, D., N. Megiddo, and B. von Stengel. 1994. Fast algorithms for finding randomized strategies in game trees. In Proceedings 26th Annual ACM Symposium on Theory of Computing, pp. 750 – 759.en_US
dc.identifier.citedreferenceRopec, D., M. Newborn, and M. Valvo. 1992. The 22nd annual ACM international chess championship. Communications of the ACM, 35 ( 11 ): 100 – 110.en_US
dc.identifier.citedreferenceRorf, R. E. 1991. Multi-player alpha-beta pruning. Artificial Intelligence, 48 ( 1 ): 99 – 111.en_US
dc.identifier.citedreferenceRuhn, H. W. 1953. Extensive games and the problem of information. In Contributions to the theory of games. Edited by H. W. Ruhn, and A. W. Tucker. Princeton University Press, Princeton, NJ, vol. II, pp. 193 – 216.en_US
dc.identifier.citedreferenceLee, R.-F., and S. Mahajan. 1990. The development of a world class Othello program. Artificial Intelligence, 43 ( 1 ): 21 – 36.en_US
dc.identifier.citedreferenceLevy, D. 1989. The million pound bridge program. In Heuristic programming in artificial intelligence. Edited by D. N. L. Levy and D. F. Beal. Ellis Horwood Limited, Chichester, England, pp. 95 – 103.en_US
dc.identifier.citedreferenceLuce, R. D., and H. Raiffa. 1957. Games and decisions. John Wiley and Sons, New York.en_US
dc.identifier.citedreferenceLuckhardt, C. A., and R. B. Irani. 1986. An algorithmic solution of n-person games. In Proceedings of the Fifth National Conference on Artificial Intelligence (AAAI-86). Morgan Raufmann Publishers, Los Altos, CA, pp. 158 – 162.en_US
dc.identifier.citedreferenceMcAllester, D. A. 1988. Conspiracy numbers formin-max search. Artificial Intelligence, 35 ( 3 ): 287 – 310.en_US
dc.identifier.citedreferenceMutchler, D., and M. van Lent. 1995. A pruning algorithm for imperfect information games. Technical Report 95-01, Department of Computer Science, Rose-Hulman Institute of Technology.en_US
dc.identifier.citedreferenceNash, J. F. 1951. Non-cooperative games. Annals of Mathematics, 54 ( 2 ): 286 – 295.en_US
dc.identifier.citedreferenceQuinlan, J. R. 1979. A knowledge-based system for locating missing high cards in bridge. In Proceedings of the 6th International Joint Conference on Artificial Intelligence (IJCAI-79), pp. 705 – 707.en_US
dc.identifier.citedreferenceRasmusen, E. 1989. Games and information–an introduction to game theory. Blackwell Publishers, Oxford.en_US
dc.identifier.citedreferenceSchaeffer, J. 1990. Conspiracy numbers. Artificial Intelligence, 43 ( 1 ): 67 – 84.en_US
dc.identifier.citedreferenceSchaeffer, J., N. Treloar, P. Lu and R. Lake. 1993. Man versus machine for the. world checkers championship. AI Magazine, 14 ( 2 ): 28 – 35.en_US
dc.identifier.citedreferenceShannon, C. E. 1950. Programming a computer for playing chess. Philosophical Magazine, seventh series, 41 ( 314 ): 256 – 275. Reprinted in Compendium of computer chess. D. N. L. Levy, Batsford, London, 1988.en_US
dc.identifier.citedreferenceShubik, M. 1982. Game theory in the social sciences. MIT Press, Cambridge, MA.en_US
dc.identifier.citedreferenceSlagle, J. R., and J. R. Dixon. 1969. Experiments with some programs that search game trees. Journal of the ACM, 16 ( 2 ): 189 – 207.en_US
dc.identifier.citedreferenceSmith, S. J. J., and D. S. Nau. 1993. Strategic planning for imperfect information games. In Games: planning and learning, papers from the 1993 Fall Symposium, AAAI Press Technical Report FS-93-02, Menlo Park, CA, pp. 84 – 91.en_US
dc.identifier.citedreferenceThompson, G. L. 1953. Signaling strategies in n-person games. In Contributions to the theory of games. Edited by H. W. Kuhn and A. W. Tucker. Princeton University Press, Princeton, N. J., vol. II, pp. 267 – 277.en_US
dc.identifier.citedreferencevan Lent, M. 1993. A pruning algorithm for one player games with hidden information. Master's thesis, University of Tennessee.en_US
dc.identifier.citedreferencevon Neumann, J. 1928. Zur theorie der Gesellschaftespiele. Mathematische Annalen, 100: 295 – 320.en_US
dc.identifier.citedreferenceWilson, R. 1972. Computing equilibria of two-person games from the extensive form. Management Science, 18 ( 7 ): 448 – 460.en_US
dc.identifier.citedreferenceZermelo, E. 1913. Uber eine Anwendung der Mengenlehre auf die Theorie des Schachspiels. In Proceedings of the Fifth International Congress of Mathematicians, Cambridge, vol. 2, pp. 501 – 504.en_US
dc.owningcollnameInterdisciplinary and Peer-Reviewed


Files in this item

Name:
j.1467-8640.1996.tb00256.x.pdf
Size:
1.530MB
Format:
PDF
View/Open

Show simple item record

Remediation of Harmful Language

The University of Michigan Library aims to describe library materials in a way that respects the people and communities who create, use, and are represented in our collections. Report harmful or offensive language in catalog records, finding aids, or elsewhere in our collections anonymously through our metadata feedback form. More information at Remediation of Harmful Language.

Accessibility

If you are unable to use this file in its current format, please select the Contact Us link and we can modify it to make it more accessible to you.