タグ

algorithmとgameに関するtomoemonのブックマーク (8)

  • d.y.d. Bowling

    21:11 07/02/26 俺定義で書けたら via この辺。 それをネタ元にして一人用パズルゲームが作れたらNP完全ぽい。 二人用対戦ゲームが作れたらPSPACE完全ぽい、というのを時々聞きます。 NP完全の一番基的な問題が SAT: bool型変数 x1 ~ xn を and と or と not で組み合わせた式があります。 さあ、あなたは、変数 x1 ~ xn の値をうまく決めて式全体の値を true にすることができますか?? という答えを見つけましょう系なのに対して、PSPACE完全の一番基的な問題が QBF: bool型変数 x1 ~ xn を and と or と not で組み合わせた式があります。 x1 をうまく決めて、「例えx2 がtrueでもfalseでも、そこですかさず x3 をうまく決めたら、 x4 がtrueになってもfalseになっても (以下繰り返し

  • Game complexity - Wikipedia

  • 人工知能の話題: TDギャモン (TD-Gammon)

    TDギャモン (TD-Gammon) TDギャモン (TD-Gammon)(注1)は,G.Tesauroが開発したシステムで,バックギャモンというゲームの対戦を行います.強化学習(注2)という方法で自分でいろいろな手を試して強くなることができます. はじめに,バックギャモンのルールについてごく簡単に説明します.このゲームは右の図の盤上で,赤と黒の丸いコマを受け持つ二人が対戦します.コマをおくマスは図の水色と黄色の部分です.ルールは「すごろく」と似ています.図のようにお互い15個ずつコマを並べた状態から始めます.2個のサイコロの目に応じて交互にコマを進めて,全部のコマをアガリまで先に動かした方が勝ちです.赤は反時計回り(24→1の方向)に,黒は時計回り(1→24の方向)にコマを動かします. その他,相手をとばしてしまうヒットや,相手の進行を妨害できるブロックといったルールがあり,駆け引きが必

  • KamoLand

    KamoLand Mastodon

    tomoemon
    tomoemon 2009/05/21
    ぷよぷよのAI
  • 「しりとり」の戦いかた、すこし反省した - Active Galactic : 11次元と自然科学と拷問的日常

    「しりとり」は経験者人口が極めて多いゲームだけど、鬼神のごとき強さで他を圧倒するしりとりプレイヤーを私は知らない。ちょっと真剣に戦ってみたところで、 そんな程度のレベルで満足していやしないか。 さいしょは「る」の同字返しでガッチリ組み合う。先に「る→る」のストックが切れて、「る」で返せなくなったほうがひたすら「る攻め」で投げられ続ける。 小学生の時から進歩していないような、こんな大雑把でマンネリな「る攻め」戦略から脱却できないものか。 攻撃防御比最大の最強文字「る」 復習。周知の事実だが「る」は強い。 下の表は、[A](文字Xで終わる単語)と、[B](文字Xではじまる単語)をその比[A/B]の高いものから順にリストしたものである。標の単語数は20万語であり豚辞書から、伸ばし棒をトリムした上で抽出した。*1 文字X[A]Xで終わる単語[B]Xで始まる単語[A/B] 1位る43235208.

    「しりとり」の戦いかた、すこし反省した - Active Galactic : 11次元と自然科学と拷問的日常
  • セルオートマトンを用いたシューティングゲーム - Tosikの雑記

    セルオートマトン(以下 CA)を用いた自作シューティングゲーム(パニックシュータ)を公開します。 プレイ動画 YouTubeに動画をアップロードしました。横長になっちゃいました。 動作環境 Windows2000,WindowsXP。CPU使用率が高いので注意。 ダウンロード・実行 Panic Shooter(パニックシュータ) ダウンロードしたZIPファイルを解凍し、pshooter.exeを実行してください。 遊び方 やってみればわかる、を目指したので説明なしで遊べると思いますが、下は簡単なルールと操作法です。 緑色の自機をカーソルキーとスペースキーで操作します。青色の箱に入ったらステージクリアです。黄色いドットにぶつかるとライフが減ります。ライフが0になったら残念。全部で10ステージクリアできるかな? あれこれ 高校のころライフゲームなどのCAにはまってから、いつかゲームにしたいと考

    セルオートマトンを用いたシューティングゲーム - Tosikの雑記
  • 第8回 倉庫番を解くアルゴリズム - 地球にやさしいアルゴリズム:ITpro

    「倉庫番」*1というゲームをご存じでしょうか。図1のように盤面にはいくつかの「荷物」とそれを運ぶ「人」がいます。人は1個の荷物を押して運ぶことができます。荷物を引っ張ったり,二つ並んだ荷物を同時に押して運ぶことはできません。人と荷物は縦横4方向に動けますが,壁のある位置には進めません。人を使って盤面上の荷物を動かし,すべての荷物を目的地(ゴール)に収めることができればゲーム・クリアとなります。図1の問題を解くための手順を示すアルゴリズムを作ってください。 友人たちと車でスキーに行くとき,いつも困るのは「トランクへ荷物を詰め込む順番」です。大きなスキーやかさばるスキーウエアを詰め込んでいるうえ,人によってはゲーム機やを持ってきたりするので,各自の荷物の量がまったく違うのです。狭い車のトランクには,これら荷物をうまい順番で入れていかないとなかなか全部収まりません。寒い冬の夜中にごそごそと詰

    第8回 倉庫番を解くアルゴリズム - 地球にやさしいアルゴリズム:ITpro
  • ゲーマーでなくても仕組みぐらいは知っておきたいアルゴリズムx40

    高校生の時、数学の先生がこう言いました。 ゲームなんて、開発者が作ったルールの上で遊ばれるだけだ。 と。 その時、ゲーマーな自分はこう思いました。 ゲーマーは、開発者が作ったルールの上で遊ばれたい。 と。 というわけで、普段何気なくプレイしているゲームには、どのようなルール(アルゴリズム)があるのか。それを知るために、いろいろなゲームのアルゴリズムなどを解析しているページへのリンク集を作りました。 ほとんどのゲームのアルゴリズムは正式に発表されていないので、ユーザーの手による逆解析だったり、大学の研究による真面目な考察だったりします。(リンク先には、一部アルゴリズムと呼べないものも含まれています) 各種ゲームのプログラム解析 ドラクエ、FF、ロマサガのプログラム解析 DQ調査報告書(リンク切れ) ドラクエの物理ダメージ計算式は質的にどれも同じだが、細かい部分で微妙に違う RPG INST

    ゲーマーでなくても仕組みぐらいは知っておきたいアルゴリズムx40
  • 1