Searching for Compound Goals Using Relevancy Zones in the Game of Go | SpringerLink
Skip to main content
Springer Nature Link
Log in

Searching for Compound Goals Using Relevancy Zones in the Game of Go

  • Conference paper
Computers and Games (CG 2004)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 3846))

Included in the following conference series:

  • 857 Accesses

Abstract

In complex games with a high branching factor, global alpha-beta search is computationally infeasible. One way to overcome this problem is by using selective goal-directed search algorithms. These goal-directed searches can use relevancy zones to determine which part of the board influences the goal. In this paper, we propose a general method that uses these relevancy zones for searching for compound goals. A compound goal is constructed from less complex atomic goals, using the standard connectives. In contrast to other approaches that treat goals separately in the search phase, compound goal search obtains exact results.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Cazenave, T.: Abstract proof search. In: Marsland, T., Frank, I. (eds.) CG 2001. LNCS, vol. 2063, pp. 39–54. Springer, Heidelberg (2002)

    Chapter  Google Scholar 

  2. Cazenave, T.: Iterative widening. In: Proceedings of the 17th International Joint Conference on Artificial Intelligence, vol. 1, pp. 523–528 (2001)

    Google Scholar 

  3. Cazenave, T.: A generalized threats search algorithm. In: Schaeffer, J., Müller, M., Björnsson, Y. (eds.) CG 2002. LNCS, vol. 2883, pp. 75–87. Springer, Heidelberg (2003)

    Chapter  Google Scholar 

  4. Cazenave, T., Helmstetter, B.: Search for transitive connections. Information Sciences 175, 284–295 (2005)

    Article  Google Scholar 

  5. Müller, M.: Decomposition search: A combinatorial games approach to game tree search, with applications to solving go endgames. In: Proceedings of the International Joined Conference on Artificial Intelligence, vol. 1, pp. 578–583 (1999)

    Google Scholar 

  6. Thomsen, T.: Lambda search in game trees with applications to Go. In: Marsland, T., Frank, I. (eds.) CG 2001. LNCS, vol. 2063, pp. 57–80. Springer, Heidelberg (2002)

    Google Scholar 

  7. Willmott, S., Bundy, A., Levine, J., Richardson, J.: An adversarial planning approach to Go. In: van den Herik, H.J., Iida, H. (eds.) CG 1998. LNCS, vol. 1558, pp. 93–112. Springer, Heidelberg (1999)

    Chapter  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, Katholieke Universiteit Leuven, Leuven, Belgium

    Jan Ramon & Tom Croonenborghs

Authors
  1. Jan Ramon
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Tom Croonenborghs
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Games and AI Group, MICC, Faculty of Humanities and Sciences, Universiteit Maastricht, Maastricht, The Netherlands

    H. Jaap van den Herik

  2. School of Computer Science, Reykjavík University, Reykjavík, Iceland

    Yngvi Björnsson

  3. Center for Automation Research, University of Maryland, College Park, MD 20742, USA

    Nathan S. Netanyahu

Rights and permissions

Reprints and permissions

Copyright information

© 2006 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Ramon, J., Croonenborghs, T. (2006). Searching for Compound Goals Using Relevancy Zones in the Game of Go. In: van den Herik, H.J., Björnsson, Y., Netanyahu, N.S. (eds) Computers and Games. CG 2004. Lecture Notes in Computer Science, vol 3846. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11674399_8

Download citation

  • DOI: https://doi.org/10.1007/11674399_8

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-32488-1

  • Online ISBN: 978-3-540-32489-8

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics