「どうぶつしょうぎ」の完全解析
田中哲朗 女流棋士の北尾まどか初段によって考案されたボードゲー ム どうぶつしょうぎ(Wikipedia: どうぶつしょうぎ) の初期局面 から(相手のライオンを取れる時は必ず取るという条件で)到達可能な局面すべ てを求め，後退解析(retrograde analysis)により，すべての局面の「勝ち」/ 「引き分け」/「負け」と双方最善を尽くした時の手数を求めるプログラムを作成 しました． ゲーム情報学研究会での発表について 2009年6月26日に開催された第22回ゲーム情報学研究会で発表した際の資料と，プレゼンテーション資料を置きます． なお，資料の図5に誤りがあります．正しい図は， となります． また，参考文献として2009年6月時点で「どうぶつしょうぎ」のオフィシャルサイト を記載しましたが，現在は有効ではないようです． プログラム dobutsu-src-20150109.tar
2007-12-10
指名を受けたので記事書こうかと思ったけど, okamoto7先生ので十分だと思ったので止め. (id:smoking186さん) えー． もうこの話題関連から抜け出せなくなってるのかも．若干古いところから引いてきますが． 不正確だったり自己流の表現だから悪いという人は、「わかりやすさ」というものの本質を理解していない。「わかりやすさ」とは突き詰めれば「不正確さ」だ。厳密に正しい説明をするとわかりにくいから、あえて不正確に表現して分かりやすくする。 http://mechag.asks.jp/131404.html あえて極論っぽく書かれてるのかもしれませんが，「不正確でいる」ことと「端折る」ことは全然違うと思うんです．はい． それと，不正確な記述をしていることを意識しているかそうでないか，とか，不正確な部分に疑問を抱かれたときにそれを正確にできるかそうでないか，とか，そういうことが重要なの
記述計算量 - Wikipedia
記述計算量（きじゅつけいさんりょう、英: Descriptive complexity）は、有限モデル理論の一種であり、計算複雑性理論と数理論理学の一分野である。複雑性クラスを言語で表現するのに必要とされる論理の種類によって特徴付けることを目的とする。例えば、PHは二階述語論理の論理式で表現される言語のクラスと正確に対応している。このような複雑性と論理の繋がりによって、2つの分野の間で容易に変換が可能となり、新たな証明手法を生み出したり、ある複雑性クラスが本質的なものであって、特定の抽象機械に結びつくものではないことを示すことができる。 概要[編集] 特に、それぞれの論理体系は、その中で表現可能なクエリの集合を生み出す。クエリは計算複雑性理論における計算問題と対応している。 記述計算量の最初の成果として、1974年にロナルド・フェイギンが示した Fagin の定理がある[1]。これは、NP
ホワット・ア・ワンダフル・ワールド 真面目に計算の複雑性の理論を勉強してこなかったツケが
twitter 某所では，ジョジョや幽遊白書ネタについてこれない naoya_t さんがツケが回ってきたと嘆いてましたが(ボクもガンダムとキンニクマンネタは全くわかりません) # cf. オタクの常識 某所でテキトーなコメントをした (via 博士号の取り方)ところ，おそらく twitter の niha さん経由で shinh 神に話が伝わり，それに答える形で sin-x さんが素晴らしい回答 を示してくださいました．なんという高度情報化社会．僕らみんなが有機的につながる Web 2.0 社会は大変素晴らしいですね． # そもそも囲碁は石が取れるじゃないか… いろいろひどすぎるなぁ．恥のメニーな生涯を送って来ました．ヒューマン失格． ちなみに，その後の twitter では非決定性の話からチューリングマシンに話題が飛び，P!=NP 関係の話題がピークに達すると共に twitter の柱
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
The Domino Problem of the Hyperbolic Plane Is Undecidable
The periodic domino problem is undecidable in the hyperbolic plane
The finite tiling problem is undecidable in the hyperbolic plane
SpringerLink - Book - The Dynamical System Generated by the 3n+1 Function
ECCC - TR09-064 - H. Buhrman, L. Fortnow, R. Santhanam "Unconditional Lower Bounds against Advice"
SpringerLink - Book Chapter - Andrew Chi-Chih Yao "Communication Complexity and Its Applications "
Average Case versus Worst Case
Shaving Logs with Unit Cost
Simulatabilation
my choices [Oded Goldreich]
P vs NC Part I: Preliminaries
Cryptology ePrint Archive 2003/187 - T. Okamoto, R. Kashima "Resource Bounded Unprovability of Computational Lower Bounds "
たまの雑記(2006-05-23)
２００６年数学基礎論サマースクール 限定算術の新展開 黒田覚（群馬県立女子大学） 2006/8/31–9/2 目 次 1 イントロダクション 1 2 計算量理論 2 2.1 基本概念など . . . . . . . . . . . . . . . . . . .
SpringerLink - V. Guruswami "List Decoding and Pseudorandom Constructions " (AAECC 2007)
2007-11-29