トップ «前の日記(2007-11-21) 最新 次の日記(2007-11-23)» 編集

はじめてのにき

ここの位置付け

2004|11|
2005|03|04|05|06|07|08|09|10|11|12|
2006|01|02|03|04|05|06|07|08|09|10|11|12|
2007|01|02|03|04|05|06|07|08|09|10|11|12|
2008|01|02|03|04|05|06|07|08|09|10|11|12|
2009|01|02|03|04|05|06|07|08|09|10|11|12|
2010|01|02|03|04|05|06|07|08|09|10|11|12|
2011|01|02|03|04|05|06|07|08|09|10|11|12|
2012|01|02|03|04|05|06|07|08|09|10|11|12|
2013|01|02|03|04|05|06|07|08|09|10|11|12|
2014|01|02|03|04|05|06|07|08|09|10|11|12|
2015|01|02|03|04|05|06|07|08|09|10|11|12|
2016|01|02|03|04|05|06|07|08|09|10|11|12|
2017|01|02|03|04|05|06|07|08|09|10|11|12|
2018|01|02|03|04|05|06|07|08|09|10|11|12|
2019|01|02|03|04|05|06|

ToDo:


2007-11-22

_ PEG

http://d.hatena.ne.jp/hayamiz/20071121/1195598233

面白そうだなぁ。 PEG はなんかパーサ書こうと思って昨日なんかちょっとだけ眺めたのだった。

(01:54)

_ 帰省やめた

やめ

(02:04)

_

http://hillbig.cocolog-nifty.com/do/2007/11/tx_bep_9fc3.html

これ聞いたけど面白かったから見るといいと思う

(02:18)

_ 将棋

一応終わるんだよな。 同じ盤面が3手来たら終わるから。 でもまぁその組み合わせは尋常じゃない量あるからまぁいいや。

http://www.kmonos.net/wlog/70.html#_2111070226

でこのへん、固定ターン数のゲームは PSPACE っても 囲碁も固定ターンだよなぁとかそんなこんな。

http://ja.wikipedia.org/wiki/EXPTIME

とりあえずチェスも囲碁も EXPTIME 完全らしい。

一方、一般化されたゲームでも、盤の大きさに対して多項式回数の手数で終わるゲーム
はPSPACE完全であることが多い。指数回数の手数がかかっても、自動的に非反復となる
ゲームは同様である。

とか書いてあるんだけど、囲碁は盤の大きさにたいして定数倍だしなぁ。 「日本ルールの囲碁は扱いにくいから EXPTIME 完全」とか よくわからん表現で PSPACE と EXPTIME は 相変わらずほげほげぽい的指標がよくわからないにゃー。

kinabaさんの「長続き」ってのが まぁ気持ちはわかるんだけどよくわからんな的な。

(02:53)

_ hah

       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)

_ たぶん

ctrlKey を true にしちまえば

(04:41)

_ たいぴんぐ

会社でちょとやてやめたのでやってみたら 56 points とかいわれたよ

(23:59)

本日のツッコミ(全2件) [ツッコミを入れる]
_ kinaba (2014-05-24 01:42)

囲碁がEXPTIME完全とわかっているのは「コウあり&&同じ盤面が来たら終わるルールなし」の場合だけらしいのですが、この場合盤面サイズ×定数のターンでは終わらないような…

手数が多項式で押さえられるなら、普通にバックトラックで全盤面シミュレートするとメモリ消費は多項式に収まる(スタックとして盤面サイズ×最大手数くらいメモリを取れば足りる)ので、PSPACEに入ると思います。

_ shinh (2014-05-24 01:42)

あーなるほど。囲碁ってそういえば相手の石取れるんでしたね…なんかよくわからんなりに PSPACE と EXPTIME の違いがわかった気がします。ありがとうございます。

スコットランドヤードとかは状態が盤面の 6乗で PSPACE なんかなぁと。

お名前:
E-mail:
コメント:
人生、宇宙、すべての答え
本日のリンク元

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
1.phoenix(2014-05-24 01:42) 2.shinh(2014-05-24 01:42) 3.ku-ma-me(2014-05-24 01:42)
search / home / index

全てリンクフリーです。 コード片は自由に使用していただいて構いません。 その他のものはGPL扱いであればあらゆる使用に関して文句は言いません。 なにかあれば下記メールアドレスへ。

shinichiro.hamaji _at_ gmail.com / shinichiro.h