WWW.DISSERTATION.XLIBX.INFO
FREE ELECTRONIC LIBRARY - Dissertations, online materials
 
<< HOME
CONTACTS



Pages:   || 2 |

«1. Introduction A great deal of effort has been spent in the search for optimal and computationally feasible game strategies. In some cases (e.g., ...»

-- [ Page 1 ] --

GO is Polynominal-Space Hard

DAVID LICHTENSTEIN AND MICHAEL SIPSER

Umversayof Cahforma,Berkeley, Cahforma

ABSTRACT. It ~S shown that, given an arbitrary G O posmon o n an n x n board, the problem of determining the

winner is Pspace hard New techmques are exploited to overcome the dffficulues a n s m g from the planar nature

of board games In parucular, tt ts proved that G O ts Pspace hard by reducing a Pspace-complete set, TQBF, to

a game called generahzed geography, then to a planar version of that game, and finally to GO.

KEY WORDS AND PHRASES computattonal complexity, games, GO, planarlty, Pspac¢ hardness CR CATEGORIES 3 69, 5 25, 5 32

1. Introduction A great deal of effort has been spent in the search for optimal and computationally feasible game strategies. In some cases (e.g., Bridge-it, Nim) such strategies have been found, while in others the search has been unsuccessful. Recently it has become possible to provide compelling evidence that such strategies may not always exist. For example, Even and Tarjan [4] and Schaefer [10] have shown that determining which player has a winning strategy m certain combinatorial games is a polynomial-space-complete problem [9] (See also [l, 3].) Polynomial-space-complete (Pspace-complete) problems are generally thought to be computationally infeasible because they are, in a certain sense, the most difficult to solve of all problems in Pspace (the class of problems solvable with a polynomial amount of memory on a reasonable model of computer), including the well-known class of NP- complete problems [6].

We show that GO, a popular Oriental game with a long history, has a similar property.

That is, given an arbitrary G O position on an n x n board, the problem of determining the winner is Pspace hard. (Pspace-hard problems are at least as difficult as any problem in Pspace.) To our knowledge, this is the first such result for a board game. Board games are by their nature p l a n a r - - a property which frequently complicates completeness proofs. We exploit new techniques developed in [7, 8] to overcome this difficulty.

In practice G O is played on a 19 x 19 board. As such it is a finite game for which a large table containing a winning strategy could, in prinople, be given. Our generalization to an n × n board prevents such a solution while preserving the spirit of the game. We make no further modifications to the rules.

We claim only that G O is Pspace hard rather than Pspace complete because G O is not known to be in Pspace. If there were a polynomial bound on the length of G O games, then the completeness would follow trivially. Whde it happens that actual games seem never to Permissionto copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercialadvantage, the ACM copynght notice and the Utleof the pubhcationand its date appear, and notice is giventhat copyingis by permissionof the Associationfor ComputingMachinery To copy otherwise, or to republish,requires a fee and/or specificpermission.

The work of the first author was supportedby the National Soence Foundationunder Grant MCS 76-17605,the work of the second author was supported by the National ScienceFoundationunder Grant MCS 75-21760-A01 and by an IBM Graduate Fellowship Authors' present addresses D Llchtenstem,Computer ScienceDivision,Departmentof Elecmcal Engmeenng and Computer Science, Umversltyof Cahforma, Berkeley, CA 94720; M Sipser, IBM Research Laboratory, 5600 Cottle Road, San Jose, CA 95913 © 1980ACM 0004-5411/80/0400-0393$00 75

–  –  –

approach 192 moves, we are unable to argue this in general. Finally, we acknowledge that our result has no a priori relevance to the problem of determining an optimal strategy when play begins on an empty board.

2. Quantified Boolean Formulas We will prove that G O is Pspace hard by reducing a Pspace-complete set, TQBF, to the problem of deciding the winner in an arbitrary G O position. The reduction proceeds by a series of steps, first reducing TQBF to a game called generalized geography (Section 3), then to a planar version of that game (Section 4), and fmally to GO (Section 6) Definition 1. The set of quantified Boolean formulas QBF ffi {Q~v~Q2v2... Qnvn.

F(vl, v2..... vn) l Q, ~ {v, 3}, where the v, are Boolean variables and F i s a Boolean formula in conjunctive normal form}.

Definition 2. TQBF is the set o f true formulas in QBF.

TQBF is Pspace complete [9].

THEOREM 1.

3. Generalized Geography Definition 3. Generalized geography (GG) is a game played by two players on the nodes of a directed graph. Play begins when the first player puts a marker on a distinguished node. In subsequent turns, players alternately place a marker on any unmarked node q such that there is a directed arc from the last node played to q. The first player who cannot move loses.

This is a generalization of a commonly played game in which players must name a geographical location not yet mentioned in the game and whose first letter is the same as the last letter of the last place named. The first player to be stumped loses. This instance of geography would be modeled by a graph with as many nodes as there are places.

Directed arcs would go from a node u to all those nodes whose first letters are the same as u's last letter.





–  –  –

representing universally quantified variables), and the other player chooses which path to take through 3-diamonds. After all diamonds have been traversed, the V-player chooses a clause, and the 3-player then chooses a variable from that clause. 3 then wins immediately if the chosen variable satisfies the clause; otherwise, V wins on the next move. It follows easily that 3 wins if;' B is true, and we leave the details to the reader. []

4. Planar Generalized Geography THEOREM 3. Generahzed geography is Pspace complete, even when played on planar graphs.

PROOF. (This proof is due to T. Schaefer and an anonymous referee who simplified the original construction appearing in [8] ) Every G G graph constructed in the previous section can be transformed into an equivalent planar G G graph as follows: Draw the graph in the

plane, allowing arcs to cross. Pick a point in the graph where two arcs cross:

–  –  –

0 [] PROPOSITION h 3 has a win in the new graph with the indicated replacement i f f 3 has a win m the original graph.

This proposition can be proved with a simple case analysis, which we omit.

To make the proof of Theorem 3 rigorous, the method of drawing a G G graph in the plane should be specified, and we refer the reader to [7, 8] for an analogous proof.

COROLLARY. GG ts Pspace complete even when played on planar bipartite graphs with maximum degree 3.

PROOF. The proof of this can~accomplished by making trivial modifications to the structures described above. The diamonds representing existential variables are enlarged

to become:

–  –  –

The back arcs representing clauses are then attached at v,,2 or ~,,2 (instead of v,,1 or ~,1), allowing the graph to remain bipartite. Nodes of indegree greater than 2 are replaced by

chains, as below:

/ / 7 /

–  –  –

5. The Rules of GO GO is played on a board which is a grid of 19 x 19 locations caUedpomts. There are two players, Black and White, for whom the rules are symmetric except that Black moves first.

A player moves by placing a stone of his own color on a vacant point. The moves alternate between players, except that any player may pass at any time. The game terminates when both players pass.

As the game progresses, the stones form clusters called groups. A group is a maximal, uniformly colored set of stones which occupy a connected region of the board A group of stones becomes surrounded if none of them is adjacent to a vacant point. After each black (white) move, all surrounded white (black) groups are removed, followed by all surrounded black (white) groups.

SCORING. At the end of the game all dead stones are removed from the board. A stone is dead if it ultimately can be surrounded, despite any attempts to save it. A vacant point is said to be white territory if it is surrounded on all sides by either white stones or the edge of the board. Black territory is similarly designated. The final score for White is the count of all the white territory minus the number of white stones which have been captured (removed at any time). The black score is slmdarly calculated and the highest scorer wins.

These rules are a subset of the actual rules of GO, though they are adequate for our purposes. The major omission concerns the situauon of KO which has a special rule designed to prevent infinite repetitions of the same position. A complete, concise treatment of all the rules is given in [2].

EYES. An important consequence of the GO rules is that certain configurations of stones cannot be captured. If a configuration surrounds two separated, vacant points, it is said to have two eyes. It then cannot be surrounded because it is impossible for the opponent to fill both eyes simultaneously (see Figure 2).

Frequently, in the course of actual games, a player may have a nearly surrounded group of stones which he is desperately trying to connect to a group having two eyes. At the same time his opponent is trying to cut him off. We exploit such a situation later m our proof.

6. Construction of the GO Position We now encode the constructed planar generalized geography game as a GO position. We refer to the GO players as Black and White and the geography players as the 3-player and the V-player. The GO position to be constructed will have the property that Black has a winning strategy iff the 3-player has a winning strategy.

The overall plan behind the construction is to have a large region of guaranteed whtte territory, together with an even larger white group of stones which is nearly surrounded (see F~gure 3). It is so large that the outcome of the game hinges on its survival; that is, Black will wm lff he can capture it. Whlte's only hope is first to escape through the small breach in the surrounding black stones and then ultimately connect to a group with two eyes This breach, however, leads to a structure which is patterned after the given geography graph. White and Black are then, in effect, forced to play the geography game with each other. (The rows of black stones extending from the left into the white group ensure that White would have no hope of recapturing any of that territory.) Each arc and vertex m the geography graph is represented by a corresponding pipe and junctton in the GO position (see Figure 4). There are essenUally five types of vertices which anse in our geography graphs (see Figure 5). We gwe the corresponding G O junctions for these vertices. Note that in the generalized geography graphs which we construct, the position of a choice vertex 0.e., a vertex with outdegree 1) determines which player

D. LICHTENSTEIN AND M. SIPSER

398 \ /

–  –  –

makes the choice. This necessitates the occasional use of trivial vertices to switch the initiative. In the G O construction the nature of the junction determines which player makes the choice. Thus the trivial vertices become unnecessary and are treated as arcs.

The test vertices are distinguished from the join vertices in that they occur only along the sides of the subgraphs representing variables and in the crossover boxes (see Figure 6).

GO is Polynominal-Space Hard 399

–  –  –

The desired G O position is obtained by joining the appropriate pipes and junctions in a way which embeds the geography graph. The pipe entering the first choice junction (the first diamond) is connected to the breach m Black's wall around the large white group.

White moves first.

400 D. LICHTENSTEIN AND M. SIPSER We now argue that if the players play "correctly," then the ensuing game will mimic a geography game in that the course of play will travel through a sequence of pipes corresponding to a valid sequence of geography arcs. Furthermore, if any player does not play correctly, his opponent will be able to win within a few moves.

Upon entering or leaving any junction it will be White's turn. Inductively, we assume that the large white group is completely surrounded except for the tip of the pipe entering the current juncuon. Let us consider the case where the play is about to enter an (a) junction, corresponding to a choice by the V-player. We assume wlog that he wishes to go left.

PROPOSITION 2. I f White"s first move is not at either point 1 or point 2, then Black can win in two moves.

PROOF. Assume that White does not play at either 1 or 2. Further assume that White does not play at 3. In that case Black plays at 2, forcing White to respond at 1, whereby Black wins at 3. If White had played at 3 initially, then by symmetry Black again has a win. [] PROPOSITION 3. I f Black does not respond at point 2, then White can win in two moves.

PROOF. Suppose White played at 1 and Black failed to play at 2. Then White plays at 2, capturing three black stones. Black cannot now prevent White from connecting to the White group with two eyes, and thus White wins. [] PROPOSITION 4. White must now continue at point 3 or else lose immediately.

PROOF. Clear. [] PROPOSITION 5. Black must respond at point 4 or lose immediately.

PROOF. Clear, using the white group which has two eyes and which is directly above 4. [] Thus if White chooses the left-hand pipe and both players play correctly, the sequence of moves would be: White--l; Black--2; White--3; Black--4. The play now continues as before, down the left-hand pipe. The large white group is again completely surrounded, except for the tip of the left-hand pipe, and it is Whlte's turn to move, fulfilling the induction assumptions. Both the (b) and the (c) junctions can be argued similarly. The (d) junction, corresponding to a selection of a variable to test by Black, is somewhat different and we analyze it here. We show that if the play enters through the right-hand pipe, then Black wins lff the play had previously passed down through the verucal pipe.



Pages:   || 2 |


Similar works:

«2 Safety Aspect in Soybean Food and Feed Chains: Fungal and Mycotoxins Contamination Germán G. Barros, María S. Oviedo, María L. Ramirez and Sofia N. Chulze Section Mycology, Department of Microbiology and Immunology, National University of Rio Cuarto. Ruta 36 km. 601 (5800) Río Cuarto, Córdoba, Argentina 1. Introduction Soybean (Glycine max L. Merr.) is an Asiatic leguminous plant cultivated in many parts of the world for its oil and proteins, which are extensively used in the manufacture...»

«1 Alain Fabre 2005Diccionario etnolingüístico y guía bibliográfica de los pueblos indígenas sudamericanos.VILELA [Última modificación: 15/04/16] VILELA y LULE Con el avance de las investigaciones actuales, resulta muy probable que el vilela deba considerarse, junto con variedades afines bastantes cercanas, como una lengua aislada. Según algunos autores, existiría una familia lingüística llamada lule-vilela, formada de dos lenguas, el ya extinto lule y el vilela. La famila ha sido...»

«Scanned by the GH Sun Master In Association With the Overpriced and Overrated Book Company. In LVX LLEWELLYN'S GOLDEN DAWN SERIES fJ1ie 'Equinox & Solstice Ceremonies ofthe (jo{den 'Dawn by Pat & Chris ZaCews/(j 1992 Llewellyn Publications St. Paul, Minnesota 55164-0383, U.S.A. Contents ix Foreword, by Frater N. U. and Soror MA.A.E.M.. I ntrod uctioti XlII The Astromagn.etic Theory 1 The Sun: Its Myths and Cycles 19 The Equinox Ceremony of the Golden Dawn 49 Z-6 A Commentary on the Equinox...»

«Red Panic Button Mobile Application User’s Guide Get out of harm’s way with just one touch! Red Panic Button The one call that can make a difference! In an emergency, information means survival. Red Panic Button is your lifeline! Contents Welcome Chapter 1 What is RPB all about? How does the Red Panic Button application work? Areas of action Types of users Chapter 2 Availability Chapter 3 Installation Chapter 3 User Interface Essentials Android User Interface iOS User Interface Chapter 4...»

«Value: Love Lesson M1.8 FRIENDSHIP Objective: To stimulate thinking about the effect that caring has on me and on others. To recognise that friends should care for each other. Key Words: cobweb, seaweed, slight, smugglers, specks, spotted, stashed, steep, symbol Curriculum Links: Citizenship & PSHE at KS1: 1a,b,c. 2a,c. 4d. Literacy: Drama Materials Needed: The Manual or copy of lesson plan • Silent sitting exercises from the ‘Introduction’ Manual • CD player • CD 1 track 27 (music...»

«[Translating and the computer 10. Proceedings of a conference. 10-11 November 1988, ed. Pamela Mayorcas (London: Aslib, 1990)] Themes in the work of Margaret Masterman Yorick Wilks Computing Research Laboratory, New Mexico State University, New Mexico, USA INTRODUCTION In this paper I shall seek to reintroduce and then focus the work of Margaret Masterman by enumerating a number of themes in her work. Some of these have been successful – in the sense of appearing, usually rediscovered, in...»

«Separating the Hope from the Hype: More perspectives on the use of information and communication technologies (ICTs) to benefit education in developing countries Excerpts from the World Bank’s EduTech blog (Volume III) Michael Trucano The World Bank 2012 Separating the Hope from the Hype: More perspectives on the use of information and communication technologies (ICTs) to benefit education in developing countries Excerpts from the World Bank’s EduTech blog Michael Trucano The World Bank...»

«Michael D. Kehler 97 Taboo, Spring-Summer 2004 Masculinities and Resistance: High School Boys (Un)doing Boy Michael D. Kehler In Australia, Canada, the United States, and the United Kingdom there has been a resurgence in attention directed at boys and schooling. The media and public discourse describes it as a burgeoning moral panic. Mainly grounded in public concerns about achievement levels and violence in schools, the response has been to develop quick fix and visible approaches. Such...»

«THURS 2ND MON 6TH JUNE 2016 THECATLAUGHS.COM Supported by: Pouring Partner: BOOK NOW: THECATLAUGHS.COM / 056 776 3837 OUR SPONSORS 2016 FUNDING PARTNERS POURING PROGRAMME MEDIA PARTNER PARTNER PARTNER ACCOMODATION PARTNERS RESTAURANT PARTNERS PERSIAN PAL IT PARTNER WELCOME Welcome to Kilkenny City: home of Ireland’s Medieval Mile, Ireland’s Ancient East and the “best little comedy festival in the world”. It is with great honour and pride that I present my fourth and final programme for...»

«MG3005 Member’s Manual Scrapbooking 101 The 4-H program has adopted a process that allows youth to first learn by doing before being told or shown how and then process the experience. The experiential learning model developed by Pfieffer and Jones (1985) and modified by 4-H includes five specific steps: The Experiential Learning Process allows an individual to go through the process of discovery with very little guidance from another individual. A situation, project or activity is presented...»

«DOT HS 811 630 August 2012 Functional Assessments, Safety Outcomes, and Driving Exposure Measures for Older Drivers DISCLAIMER This publication is distributed by the U.S. Department of Transportation, National Highway Traffic Safety Administration, in the interest of information exchange. The opinions, findings, and conclusions expressed in this publication are those of the authors and not necessarily those of the Department of Transportation or the National Highway Traffic Safety...»

«CURRICULUM VITAE Devin K. Binder, M.D., Ph.D. EDUCATION/PROFESSIONAL POSITIONS UNIVERSITY OF CALIFORNIA Riverside, CA Assistant Professor, Center for Glial-Neuronal Interactions, Division of Biomedical Sciences. Director, Translational Neuroscience Laboratory. Assistant Clinical Professor of Neurological Surgery, UCR-UCLA Thomas Haider Program in Biomedical Sciences. January 2010–present. BRAIN AND ELECTIVE SPINE TREATMENT (B.E.S.T.) CENTER Newport Beach, CA Neurosurgeon specializing in deep...»





 
<<  HOME   |    CONTACTS
2016 www.dissertation.xlibx.info - Dissertations, online materials

Materials of this site are available for review, all rights belong to their respective owners.
If you do not agree with the fact that your material is placed on this site, please, email us, we will within 1-2 business days delete him.