継続による時間操作とフィラデルフィア・エミュレータ(1)

要約:

フィラデルフィア演義の戦闘エミュレータを作り始めた。まだちゃんと動かない。
その過程でambを作り直し、時間属性を持つオブジェクト操作に関するバッドノウハウを収集した。

http://www.geocities.jp/steppersstop/ の縮退演義

これを解いてみたくなったので、まずはとりあえず、フィラデルフィア演義の願い無し戦闘エミュレータを試行錯誤しながら書いてみる事にした。
そして、ある程度書いた。

作成時の問題点として、「実際のフィラデルフィア演義で、コンピュータが最適手を選び出すアルゴリズム」が分からない。
例えば、各メンバーの武力がそれぞれ'(10 2 1)のチームAと'(9 8)のチームBが戦ったとする。
一番最初に行動するチームAの10は、チームBの9を攻撃するのがベストだというのはすぐに分かる。
しかし、その後に行動するチームBの8は誰を攻撃するのがベストなのかというのを判断する為の汎用アルゴリズムがちょっと分からない。そして、実際にはもっと複雑な組み合わせが多く出てくるだろう。
そこで、amb( http://www.shiro.dreamhost.com/scheme/wiliki/wiliki.cgi?amb )を使って、総当たりで最適手を探し出す事にした。と言うか、これ以外には無いように思える。
但し、以下の制約を守る必要がある。

対戦するそれぞれのチームがそれぞれamb状態を持つ事。
チーム及びチーム内メンバーの内部状態を破壊的更新してはならない。

最初の制約は、要するに、チームAが勝つ為に試行錯誤する為のambと、チームBが勝つ為のambを別々に用意する必要があるという事。
そして、(相討ちにならない限りは)どちらかが全滅して決着が付く為、どちらかのambが必ず破綻する、という事になる。
とりあえずの目的として、それが見極められればokとする。
(将来的には戦闘過程をdumpさせたりできるように改良すれば、より面白くなると思う。)
尚、相討ちについては、後述する非常に厄介な性質があるが、それは後述。

二番目の制約については、この前に日記に書いた関数脳関連のところそのまま。
ambは要するに、「こっちを選ぶとどうやっても勝てなくなる」という情報を得たら、過去の選択の時点まで戻って、他の選択肢を試す、という挙動をする為、チームオブジェクトやチーム内メンバーオブジェクトを破壊的更新してしまうと、過去に戻っても破壊的更新されたままになってしまい、まずい。
よって、戦闘過程をコード化するにあたっては、この部分に副作用を持ち込む事は許されない。
とりあえず今回は、オブジェクトを更新する時は、「新しいオブジェクトを作成してそっちを指すようにする」実装にした(この部分のソースはあとで公開する)。
尚、元々は、チームはlist、そのメンバーは武力値のみで表現していたものの、なんか未来にチームに名前付けたり拡張しそうな気がしたので、クラス表現にしてしまった。
(クロージャやgauche.parameterで扱うよりも、多分そっちの方があとで属性を追加しやすいような気がしたので。また、今回は総当たりで最適手を探す為、「願い」を実装しても最適手を探す事が可能になる……筈。)
関数脳で言ったのとは違い、自分もやっぱり「状態」を扱ってしまっている。
あとは、オブジェクト指向と関数指向は直交する、という事で、誤魔化す事にする。

この二つの制約を考慮しつつ書いてみたのが、以下のコードとなる。

(define (make-amb . opt-failed-thunk)
  (let1 fail (get-optional opt-failed-thunk
               (lambda ()
                 (error "amb failed")))
    (define (choose . args)
      (if (null? args)
        (fail)
        (let1 old-fail fail
          (let/cc cc
            (set! fail (lambda ()
                         (set! fail old-fail) ; restore
                         (cc (apply choose (cdr args)))))
            (car args)))))
    choose))

このコードは、 http://www.shido.info/lisp/scheme_amb.html のcode 1のchooseをベースに、高階関数化したもの。
(make-amb)を実行すると、内部にfail束縛を個別に持つchoose手続きを返す。
つまり、

(define choose (make-amb))

を実行すれば、普通にsample 1を動作させられる。
また、オプショナル引数で、全検索失敗時の挙動を自分で設定できるようにしてみた。
(尚、オリジナルはマクロ化して、引数の評価を後回しにできるようにしていたが、今回はその必要が無かったのと、高階関数化する時点でマクロ化が難しくなった為に、手続きとして作成する事にした。)

しかし、結論から先に言うと、これは正常に動作しなかった。
それは何故かと言うと、チームAとチームBは交互または同時に行動していく訳で、その際の攻撃相手の選択の為にこのambを利用するという話だった。
そして、その為には前述の二つの制約を守る必要があるという事であった。
しかし、このamb自体が内部でset!を使い、破壊的更新を行ってしまっている。
ambが一つだけならばこれでも別に問題は起こらない。
しかし、ambを二つ使った時点で、片方のambがバックトラックを実行した際に、もう片方のambもバックトラックした時点までロールバックが行われないといけない。
しかし、このambは破壊的更新によって実装されている為、これでは正常にバックトラックが行われず、正しく全検索が行われない。
よって、副作用無しに実装されたambを作る必要がある。

次回に続く。