NP-complete -> PSPACE-complete problem

Go

Description: This ancient game is played by placing stones on a 19*19 board. When a group of stones of one color is completely surrounded by stones of the other color, the surrounded group is removed from the board. The object is to control empty squares by surrounding them; after both players are unwilling to continue play, these squares are counted and the scores adjusted by the numbers of stones that had been removed.

Status: This is a finite game, but can be generalized to n*n boards. Even without ko (special rules related to repetition of positions) the game is PSPACE-hard; with ko (Japanese rules) it is EXPTIME-complete. It is apparently still open whether Chinese or US rules Go is EXPTIME-complete. Even certain "simple" endgames in which the go board has been decomposed into many small independent regions of play are PSPACE-hard.

References:

* GJ 257 [GP11]. * D. Lichtenstein and M. Sipser, Go is polynomial-space hard, J. ACM 27 (1980) 393-401. * J. M. Robson, The complexity of Go, Proc. IFIP (1983) 413-417. * J. M. Robson. Combinatorial games with exponential space complete decision problems. Proc. Mathematical Foundations of Computer Science, Springer-Verlag, LNCS 176, 1984, pp. 498-506. * E. Berlekamp and D. Wolfe, Mathematical Go: Chilling Gets the Last Point, A. K. Peters, 1994. * D. Wolfe, Go endgames are hard, MSRI Combinatorial Game Theory Research Worksh., 2000. * M. Crâşmaru and J. Tromp, Ladders are PSPACE-complete, Proc. 2nd Int. Conf. Computers and Games, Springer-Verlag, 2000, pp. 241-249.

Nov. 11, 2008 - Terra Soft to merge with Japanese Cell Developer Fixstars .

Reading 'A Rough Guide to Go Gaming on the Play Station3 ' (77 pages)

Sony PS3 Cluster (IBM Cell BE)

yeh, raph.

last read book 'going postal - rage, murder and rebellion: From Reagan's workplaces to clinton's Columbine and Beyond' byM ark Ames. also by him, 'The War we don't know'

reading Italo Calvino's Cosmicomics... "The distance of the Moon" - what a story!

love Eric's voice over D.H. Lawrence's 'Honeymoon'

complete poetry and prose of William Blake

Poetic Sketches

*To SPRING

 
 O thou with dewy locks, who lookest down
Thro' the clear windows of the morning, turn
Thine angel eyes upon our western isle,
Which in full choir hails thy approach, O Spring!

 
 The hills tell each other, and the listening
Valleys hear; all our longing eyes are turned
Up to thy bright pavilions: issue forth,
And let thy holy feet visit our clime.

 
 Come o'er the eastern hills, and let our winds
Kiss thy perfumed garments; let us taste
Thy morn and evening breath; scatter thy pearls
Upon our love-sick land that mourns for thee.

 
 O deck her forth with thy fair fingers; pour
Thy soft kisses on her bosom; and put
Thy golden crown upon her languished head,
Whose modest tresses were bound up for thee.

 
 * TO SUMMER
O thou who passest thro' our valleys in
Thy strength, curb thy fierce steeds, allay the heat
That flames from their large nostrils! thou, O Summer,
Oft pitched'st here thy goldent tent, and oft
Beneath our oaks hast slept, while we beheld
With joy thy ruddy limbs and flourishing hair.

 
 Beneath our thickest shades we oft have heard
Thy voice, when noon upon his fervid car
Rode o'er the deep of heaven; beside our springs
Sit down, and in our mossy valleys, on
Some bank beside a river clear, throw thy
Silk draperies off, and rush into the stream:
Our valleys love the Summer in his pride.

 
 Our bards are fam'd who strike the silver wire:
Our youth are bolder than the southern swains:
Our maidens fairer in the sprightly dance:
We lack not songs, nor instruments of joy,
Nor echoes sweet, nor waters clear as heaven,
Nor laurel wreaths against the sultry heat.

 
 * TO AUTUMN

 
 O Autumn, laden with fruit, and stain'd
With the blood of the grape, pass not, but sit
Beneath my shady roof; there thou may'st rest,
And tune thy jolly voice to my fresh pipe,
And all the daughters of the year shall dance!
Sing now the lusty song of fruits and flowers.

 
 'The narrow bud opens her beauties to
The sun, and love runs in her thrilling veins;
Blossoms hang round the brows of Morning, and
Flourish down the bright cheek of modest Eve,
Till clust'ring Summer breaks forth into singing,
And feather'd clouds strew flowers round her head.

 
 'The spirits of the air live in the smells
Of fruit; and Joy, with pinions light, roves round
The gardens, or sits singing in the trees.'
Thus sang the jolly Autumn as he sat,
Then rose, girded himself, and o'er the bleak
Hills fled from our sight; but left his golden load.

 
 * TO WINTER

 
 O Winter! bar thine adamantine doors:
The north is thine; there hast thou built thy dark
Deep-founded habitation. Shake not thy roofs,
Nor bend thy pillars with thine iron car.'

 
 He hears me not, but o'er the yawning deep
Rides heavy; his storms are unchain'd, sheathd
In ribbd steel; I dare not lift mine eyes,
For he hath rear'd his sceptre o'er the world.

 
 Lo! now the direful monster, whose 1000 skin clings
To his strong bones, strides o'er the groaning rocks:
He withers all in silence, and in his hand
Unclothes the earth, and freezes up frail life.

 
 He takes his seat upon the cliffs,--the mariner
Cries in vain. Poor little wretch, that deal'st
With storms!--till heaven smiles, and the monster
Is driv'n yelling to his caves beneath mount Hecla.

 
 * TO MORNING

 
 O holy virgin! clad in purest white,
Unlock heav'n's golden gates, and issue forth;
Awake the dawn that sleeps in heaven; let light
Rise from the chambers of the east, and bring
The honey'd dew that cometh on waking day.
O radiant morning, salute the sun
Rous'd like a huntsman to the chase, and with
Thy buskin'd feet appear upon our hills.

 
 * TO THE EVENING STAR

 
 Thou fair-haired angel of the evening,
Now, whilst the sun rests on the mountains, light
Thy bright torch of love; thy radiant crown
Put on, and smile upon our evening bed!
Smile on our loves, and while thou drawest the
Blue curtains of the sky, scatter thy silver dew
On every flower that shuts its sweet eyes
In timely sleep. Let thy west wing sleep on
The lake; speak silence with thy glimmering eyes,
And wash the dusk with silver. Soon, full soon,
Dost thou withdraw; then the wolf rages wide,
And the lion glares through the dun forest.
The fleeces of our flocks are covered with
Thy sacred dew; protect with them with thine influence.

 
 * SONG: How sweet I roam'd from field to field

 
 How sweet I roam'd from field to field,
And tasted all the summer's pride,
'Till I the prince of love beheld,
Who in the sunny beams did glide!

 
 He shew'd me lilies for my hair,
And blushing roses for my brow;
He led me through his gardens fair,
Where all his golden pleasures grow.

 
 With sweet May dews my wings were wet,
And Phoebus fir'd my vocal rage;
He caught me in his silken net,
And shut me in his golden cage.

 
 He loves to sit and hear me sing,
Then, laughing, sports and plays with me,
Then stretches out my golden wing,
And mocks my loss of liberty.

 
 * THE GARDEN OF LOVE

 
 * HUMAN ABSTRACT