ToDo:
かしら？
http://twitter.com/masa_edw/statuses/432464042
http://morihyphen.hp.infoseek.co.jp/prog/fontlist.html
(01:53)
http://d.hatena.ne.jp/hayamiz/20071121/1195598233
面白そうだなぁ。 PEG はなんかパーサ書こうと思って昨日なんかちょっとだけ眺めたのだった。
(01:54)
一応終わるんだよな。 同じ盤面が3手来たら終わるから。 でもまぁその組み合わせは尋常じゃない量あるからまぁいいや。
http://www.kmonos.net/wlog/70.html#_2111070226
でこのへん、固定ターン数のゲームは PSPACE っても 囲碁も固定ターンだよなぁとかそんなこんな。
http://ja.wikipedia.org/wiki/EXPTIME
とりあえずチェスも囲碁も EXPTIME 完全らしい。
一方、一般化されたゲームでも、盤の大きさに対して多項式回数の手数で終わるゲーム はPSPACE完全であることが多い。指数回数の手数がかかっても、自動的に非反復となる ゲームは同様である。
とか書いてあるんだけど、囲碁は盤の大きさにたいして定数倍だしなぁ。 「日本ルールの囲碁は扱いにくいから EXPTIME 完全」とか よくわからん表現で PSPACE と EXPTIME は 相変わらずほげほげぽい的指標がよくわからないにゃー。
kinabaさんの「長続き」ってのが まぁ気持ちはわかるんだけどよくわからんな的な。
(02:53)
var evt = doc.createEvent('MouseEvents');
evt.initMouseEvent('mousedown', true, true, view, 1, x+1, y+1, 0, 0, eve
nt.ctrlKey, event.altKey, event.shiftKey, event.metaKey, 0, null);
elem.dispatchEvent(evt);
var evt = doc.createEvent('MouseEvents');
evt.initMouseEvent('click', true, true, view, 1, x+1, y+1, 0, 0, event.c
trlKey, event.altKey, event.shiftKey, event.metaKey, 0, null);
elem.dispatchEvent(evt);
このへんちゃうんかね。
(04:41)
| 前 | 2007年 11月 |
次 | ||||
| 日 | 月 | 火 | 水 | 木 | 金 | 土 |
| 1 | 2 | 3 | ||||
| 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| 11 | 12 | 13 | 14 | 15 | 16 | 17 |
| 18 | 19 | 20 | 21 | 22 | 23 | 24 |
| 25 | 26 | 27 | 28 | 29 | 30 | |
全てリンクフリーです。 コード片は自由に使用していただいて構いません。 その他のものはGPL扱いであればあらゆる使用に関して文句は言いません。 なにかあれば下記メールアドレスへ。
囲碁がEXPTIME完全とわかっているのは「コウあり＆＆同じ盤面が来たら終わるルールなし」の場合だけらしいのですが、この場合盤面サイズ×定数のターンでは終わらないような…
手数が多項式で押さえられるなら、普通にバックトラックで全盤面シミュレートするとメモリ消費は多項式に収まる（スタックとして盤面サイズ×最大手数くらいメモリを取れば足りる）ので、PSPACEに入ると思います。
あーなるほど。囲碁ってそういえば相手の石取れるんでしたね…なんかよくわからんなりに PSPACE と EXPTIME の違いがわかった気がします。ありがとうございます。
スコットランドヤードとかは状態が盤面の 6乗で PSPACE なんかなぁと。