[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [computer-go] citation
Ladder reading is so trivial it can be done in linear-time. Give me a
break.
It's not the reading but deciding whether a ladder works which is a
PSPACE-complete
problem (see abstract below).
-Floris
Ladders Are PSPACE-Complete
Marcel Crâsmaru A1 and John Tromp A2
A1 Department of Mathematical and Computing Science, Tokyo Institute of
Technology, 2-12-1 Oo-okayama, Meguro-ku, Tokyo, Japan, 152,
marcel@xxxxxxxxxxxxxxxxx
A2 CWI Kruislaan 413, 1098 SJ Amsterdam, The Netherlands tromp@xxxxxxxxxxxxxxxxx
Abstract:
In the game of Go, the question of whether a ladder-a method of
capturing stones-works, is shown to be PSPACE-complete. Our reduction
closely follows that of Lichtenstein and Sipser [2], who first showed
PSPACE-hardness of Go by letting the outcome of a game depend on the
capture of a large group of stones. A greater simplicity is achieved by
avoiding the need for pipes and crossovers.
In: Computers and Games: Second International Conference, CG 2001,
Hamamatsu, Japan, October 26-28, 2000.
_______________________________________________
computer-go mailing list
computer-go@xxxxxxxxxxxxxxxxx
http://www.computer-go.org/mailman/listinfo/computer-go/