BEAR Blog

Because everything is a resource.

GDD2011 DevQuiz

| Comments

今年もGoogle Developers Days 2011のDevQuizに挑戦しました。
以下、その記録です。

Web Game

Chromeのエクステンションを作成。サンプルに少し追加して全てのカードをクリックするようにして解答しました。

多くの人が思ったようにChromeのエクステンションは簡単にできるのよく分かりました。solver.jsとmanifest.jsonの2つのファイルを作成するだけです。

このエクステンションはhttp://gdd-2011-quiz-japan.appspot.com/webgame/problem%E3%81%AE%E3%82%B5%E3%82%A4%E3%83%88%E3%81%AB%E5%87%BA%E7%8F%BE%E3%81%99%E3%82%8B%E5%85%A8%E3%81%A6%E3%81%AE%E3%82%AB%E3%83%BC%E3%83%89%E3%82%92%E3%82%AF%E3%83%AA%E3%83%83%E3%82%AF%E3%81%97%E3%81%BE%E3%81%99%E3%80%82

solver.js

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
var i = j = 0;
cont = true;
while (cont == true) {
  var element0 = document.getElementById('card' + i);
  var element1 = document.getElementById('card' + j);
  console.log(j);
  if (element0 == null) {
      cont = false;
  }
  if (element1 == null) {
      console.log('Card element is not found. Check element id.');
      i++;
      j = i;
  } else {
      var myevent = document.createEvent('MouseEvents');
      myevent.initEvent('click', false, true);
      element0.dispatchEvent(myevent);
      element1.dispatchEvent(myevent);
      console.log('Card color is "' + element1.style.backgroundColor + '".');
  }
  j++;
}

manifest.json
{ "name": "ChromeExtensionSolverHint", "version": "1.0", "description": "Open the first card and show background color of the card.", "content_scripts": [ { "matches": [ "http://gdd-2011-quiz-japan.appspot.com/webgame/problem*" ], "js": [ "solver.js" ] } ], "permissions": [ ] }

Go

Go言語で与えられた画像ファイルの使用色数を答える関数を作成するという問題です。

まずはOSX/LionにGoをインストールです。このサイトを参考にしました。1
http://jeremyhubert.com/articles/installing-google-go-on-osx-snow-leopard.html

Go言語は初めてだったのですが触ってすぐに色々な興味深い特徴に気がつきます。2
静的型付けのコンパイラ言語なのですが、丁寧に削られた簡素な記述のおかげかスクリプト言語のような柔軟でソフトな印象を感じました。

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
31
32
33
34
35
36
37
38
39
40
41
package main
import (
    "fmt"
    "io"
    "strings"
  imagep "image/png"
    /* add more */
)
func CountColor(png io.Reader) int {
  image, err := imagep.Decode(png)
  if err != nil {
      fmt.Printf("Error from png.Decode: %s\n", err)
  }
  width := image.Bounds().Size().X
  height := image.Bounds().Size().Y
    //fmt.Printf("width: %d, %d\n", width, height)
  result := map[uint32]bool{}
  var idx uint32
  for y:=0 ; y < height ; y++{
      for x:= 0 ; x < width ; x++ {
          color := image.At(x, y)
          //fmt.Printf("x, y, color: %d %d %x\n", x, y, color)
          r, g, b, _ := color.RGBA();
          idx = r*0x100*0x100 + g*0x100 + b
          result[idx] = true
      }
  }
  cnt := len(result)
    return cnt
}
/* これらの関数は提出時に自動挿入されます。 */
func main() {
    png := GetPngBinary()
    cnt := CountColor(png)
    fmt.Println(cnt)
}
func GetPngBinary() io.Reader {
    // img_strの中身は提出するたびに変化します。
    img_str := "\x89PNG\r\n\x1a\n\x00\x00\x00\rIHDR\x00\x00\x00\x18\x00\x00\x00\x08\x08\x06\x00\x00\x00\xe3\xa1?c\x00\x00\x02\xeeiCCPICC Profile\x00\x00x\x01\x85T\xcfk\x13A\x14\xfe6n\xa9\xd0\"\x08Zk\x0e\xb2x\x90\"IY\xabhE\xd46\xfd\x11bk\x0c\xdb\x1f\xb6E\x90d3I\xd6n6\xeb\xee&\xb5\xa5\x88\xe4\xe2\xd1*\xdeE\xed\xa1\x07\xff\x80\x1ez\xf0d/J\x85ZE(\xde\xab(b\xa1\x17-\xf1\xcdnL\xb6\xa5\xea\xc0\xce~\xf3\xde7\xef}ov\xdf\x00\rr\xd24\xf5\x80\x04\xe4\r\xc7R\xa2\x11il|Bj\xfc\x88\x00\x8e\xa2\tA4%U\xdb\xecN$\x06A\x83s\xf9{\xe7\xd8z\x0f\x81[V\xc3{\xfbw\xb2w\xad\x9a\xd2\xb6\x9a\x07\x84\xfd@\xe0G\x9a\xd9*\xb0\xef\x17q\nY\x12\x02\x88<\xdf\xa1)\xc7t\x08\xdf\xe3\xd8\xf2\xec\x8f9Nyx\xc1\xb5\x0f+=\xc4Y\"|@5-\xce\x7fM\xb8S\xcd%\xd3@\x83H8\x94\xf5qR>\x9c\xd7\x8b\x94\xd7\x1d\x07inf\xc6\xc8\x10\xbdO\x90\xa6\xbb\xcc\xee\xabb\xa1\x9cN\xf6\x0e\x90\xbd\x9d\xf4~N\xb3\xde>\xc2!\xc2\x0b\x19\xad?F\xb8\x8d\x9e\xf5\x8c\xd5?\xe2a\xe1\xa4\xe6\xc4\x86=\x1c\x185\xf4\xf8`\x15\xb7\x1a\xa9\xf85\xc2\x14_\x10M'\xa2Tq\xd9.\r\xf1\x98\xae\xfdV\xf2J\x82p\x908\xcada\x80sZHO\xd7Ln\xf8\xba\x87\x05}&\xd7\x13\xaf\xe2wVQ\xe1y\x8f\x13g\xde\xd4\xdd\xefE\xda\x02\xaf0\x0e\x1d\x0c\x1a\x0c\x9a\rHP\x10E\x04a\x98\xb0P@\x86< \x1a14\xb2r?#\xab\x06\x1b\x93{2u$j\xbbtbD\xb1A{6\xdc=\xb7Q\xa4\xdd<\xfe(\"q\x94C\xb5\x08\x92\xfcA\xfe*\xaf\xc9O\xe5y\xf9\xcb\\\xb0\xd8V\xf7\x94\xad\x9b\x9a\xba\xf2\xe0;\xc5\xe5\x99\xb9\x1a\x1e\xd7\xd3\xc8\xe3sM^|\x95\xd4v\x93WG\x96\xacyz\xbc\x9a\xec\x1a?\xecW\x971\xe6\x825\x8f\xc4s\xb0\xfb\xf1-_\x95\xcc\x97)\x8c\x14\xc5\xe3U\xf3\xeaK\x84uZ17\xdf\x9fl\x7f;=\xe2.\xcf.\xb5\xd6s\xad\x89\x8b7V\x9b\x97g\xfdjH\xfb\xee\xaa\xbc\x93\xe6U\xf9O^\xf5\xf1\xfcg\xcd\xc4c\xe2)1&v\x8a\xe7!\x89\x97\xc5.\xf1\x92\xd8K\xab\x0b\xe2`m\xc7\x08\x9d\x95\x86)\xd2m\x91\xfa$\xd5``\x9a\xbc\xf5/]?[x\xbdF\x7f\x0c\xf5Q\x94\x19\xcc\xd2T\x89\xf7\x7f\xc2*d4\x9d\xb9\x0eo\xfa\x8f\xdb\xc7\xfc\x17\xe4\xf7\x8a\xe7\x9f(\x02/l\xe0\xc8\x99\xbamSq\xef\x10\xa1e\xa5ns\xae\x02\x17\xbf\xd1}\xf0\xb6nk\xa3~8\xfc\x04X<\xab\x16\xadR5\x9f \xbc\x01\x1cv\x87z\x1e\xe8)\x98\xd3\x96\x96\xcd9R\x87,\x9f\x93\xba\xe9\xcabR\xccP\xdbCRR\xd7%\xd7eK\x16\xb3\x99Ub\xe9v\xd8\x99\xd3\x1dn\x1c\xa19B\xf7\xc4\xa7Je\x93\xfa\xaf\xf1\x11\xb0\xfd\xb0R\xf9\xf9\xacR\xd9~N\x1a\xd6\x81\x97\xfao\xc0\xbc\xfdE\xc0x\x8b\x89\x00\x00\x00\x97IDAT(\x15\x9d\x92\x81\x0e\x80 \x08D\xa5\xf9m\xf5Y\xad\xcf\xaa\x9f#nz$\xba\xb9\xca\xad\x85\xc1\xbd\x03S\xd4\x96H\xf2\xa5\xea\xe1\xeb@\x8e\x02\xd0}\x14/\x80\x03\xca\xa75{\xeb0\x80\x01\xa9\xa0\xdcC|\x02:\xf1\xc3U\xc7\\K\x97}\xda9HPcq0pQ\x8aE\xe94y\x05'3\x92M[\x86\xc7\xc1\xa4n\x82\x01\x8ci\xe2\xc5\x7f\x02N`\xda\xdcCK\xaeqbqsD\xbd\x86=\xe0g\xdb\x9dy\xba\xb4Xp\x8bX\xf0\xe7\x8d\x89g\x84pD_\x0cx\x9438x7\xa4yC\r7\x04z\xae\x00\x00\x00\x00IEND\xaeB`\x82"
    return strings.NewReader(img_str)
}

ポイントというほどの所もないですが、色を数えるのに各色8bitなので16進数3桁の数字にしてキーにしその数を数えました。

スライドパズル

大きさが色々あり、盤面の中にも壁がある15パズルの変形版のようなパズルを5000問解くという問題です。一問0.1点。これまでの3つのクイズの合計100点あったのですが、101点になるために今までの100点獲得の労力を軽く超えるような難易度でした。難しかったです。

CPU100%でファンを全開で一晩中計算し続けさせるようなパズルの解法のプログラムは、ms単位で処理の終わる普段のwebプログラムと全く違う世界です。AIプログラミングの基礎的な事から分かってなかったのでその学習から始めました。前回のGDD Pacman問題の反省です。3 

まず大事なのは問題をツリー構造にモデル化することです。問題プロセスの状態を節点(node)、その状態遷移を枝(branch)で表します。一番初めの節点を根(root)、一番末端を葉とした状の不可逆のツリー構造をモデルとし、そのルートからゴールまでの状態遷移に様々な探索方法をあてはめ解法を求めます。

競技用プログラムやAIプログラムに慣れてる方ならこの辺りの話は基礎の基礎なのだと思いますが、自分は一つ一つをあーなるほどと理解するところから始めました。

最良優先探索はいくつもあるのですが、向いてそうなのは A*、評価関数はオーソドックスなマンハッタン距離に少しオリジナルな関数を加えたらと考えました。

言語の選択

最初は普通に考えて速度の速いコンパイル言語をと、ちょっと学習してみたGoか普段使わないC/C++/Javaに挑戦するかとか考えました。4 しかし#gdd11jpでPythonで高得点を取ってる方がいたのを見たのと 5 使った事のないPHP5.3の機能ややってみたい実装があったのでPHPにしました。6。目標として(使い切りだし時間も限られてますが)丁寧なOOPでマンハッタン距離+αのヒューストリックのA*で実装というのを立てます。

実装

https://github.com/koriym/gdd11jp

以下、READMEからです。

■slide.php
本体。answer.txtがあれば解答済みファイルとしてスキップに利用、答えはoutput.txtで出力。
どのパズルをスキップするか、およびパズルに応じたタスク管理を選択するロジックをクロージャで渡して演算を開始。

幅優先探索は、反復深化深さ優先探索ははどちらもブラインドサーチで3x3と3x4,4/3のみに対応。それ以上は=(壁)検知付きマンハッタン距離、正位置にあるピースに重みづけ、それに手数削減のための過去の移動距離をそれぞれコストとして合計したものを関数としてヒューリスティック探索。繰り返し検知、逆探索検索付き。消費メモリ、消費時間に応じて無回答。制限時間になってもヒューリスティック関数の値が上昇し続けてたら時間制限を延長する”もう少しかも、頑張れ"機能。"下端を除くゲーム盤面の端で1つ足りないだけの状態にペナルティの効果"は今ひとつ。

演算コスト削減は、マンハッタン距離コストマップ、移動可否マップの事前演算。メモリ省力化として配列のSplFixedArray使用等。基本的な探索実装で目標スコア3000後半程度。肝心のソルバーは強くないが想定の範囲は大体実装。

クラス

PuzzuleRepository
ファイルからパズルオブジェクトを取り出せるリポジトリクラス。
Puzzle
パズルの基本データ。プロパティの公開されているデータ構造クラス。
Game
ゲーム状態を保持しパズルの基本操作ができるオブジェクト。方向と合わせてタスクとして登録される。
Play
ルールを知りプレイを行うクラス。ゲーム完了するまでループ実行。
Task
BFS, IDDFS, A*探索を行うためのタスクマネージメントクラス。
それぞれPHPのSplQueue、SplStack、SplPriorityQueueクラスを利用。

PHPには A*にそのまま適用できるSplPriorityQueue クラス、幅優先探索にSplQueueクラス、深さ優先探索 にSplStack クラスという標準的なデータ構造用のクラスが5.3から用意されていてこれを利用しました。
肝心のソルバーはマンハッタン距離(途中の壁検知付の)と移動ヒストリーの長さを合算してコストにするものと、その逆探索の基本的なものですが、パズルを二次元配列にしないで高速化と処理の簡素化のために一次元にしたのと、移動処理の時のif R, if L …と4つ続ける冗長さを排除したのが小さなこだわりです。双方向探索の実装をしてれば大きくスコアを伸ばせたのではないかと思います。高速な言語に移植する方法もありましたがPHPと基本的なアルゴリズムでどれくらいのスコアが取れるのだろうという興味もありました。少しの改善で4000ありえるかなあというところでタイムアップでした。3750/5000です。高得点とは言えませんが、幅優先実装してたった0.57点でPHPじゃやっぱり…と途方にくれた時から考えると大きな前進でした。

Clean Code

限られた時間である程度の結果を出しながら多くのOOP原則に従ったClean Codeで記述というのも今回の目標の一つでした7
単一責任原則(SRP:the Single Responsibility Principle) 、デメテルの法則(Law of Demetre (LoD))、おまえが呼ぶな、俺が呼ぶの「ハリウッドの原則」、オープン・クローズドの原則(OCP)、gettr/setterの排除、等々意識したのですが不十分な所も多々あり反省の残るところです。それでも"次"にはかなり再利用できそうです。また、PHPのコーディングでprivate/protectedのprefixに_(アンダースコア)を使わないスタイルがいいのでは?にというトレンドが一部であるようで今回はそれに従ってみました。その他は現在のPHPのごく標準的なコード規約に従ってると思います。

実行方法

$ git clone git@github.com:koriym/gdd11jp.git
$ cd gdd11jp/puzzle
$ php slide.php

まとめ

コンテストと違ったイベント感、使用言語を超え同じ取り組みをする事で生まれる共有感、高得点の人もそうでない人も、DevQuizはプログラミングが本来持つコーディングの楽しみが実感できる素晴らしい機会だと思います。8 機会を与えてくれた主催者の方々と#gdd11jpで楽しい時間を共有してくれた皆様には感謝を申し上げます。ありがとうございました。GDD11でお会いしましょう!

  1. コンパイルとリンクを行うスクリプトもあって便利です。 []
  2. 例えば、変数名の後に型が続く事や、大文字始まりならpublic宣言など。また未使用変数があればコンパイルにすら通りません。 []
  3. 自分で適当に考え実装し後からああ自分の実装はBFSというやつだったのか..などとならないように! []
  4. Cはその昔SonyのPlayStation用ゲーム制作の一部を手伝った事があるくらいでポリゴンで3Dの関節プログラムとか、アセンブラのゲームの移植とか、すっかり忘れてるのですが再挑戦も面白いと思いました []
  5. Cythonというコンパイラがあって超高速で実行できるのは後で知りました^^; []
  6. どうせならPHP5.4でやれば良かったですね []
  7. 点にはなりませんが []
  8. 中学生の時にはじめてプログラミングしたワクワク感が少し甦りました。 []

PHP Hello Worldコールグラフ(2011)

| Comments

Hello Worldベンチマーク

去年のHello Worldコールグラフに続いて再度HelloWorldグラフをとりました。

グラフをとるためにリファレンスにしたHelloWorldベンチマークのサイトは前回とは違い、SolarPHPというフレームワークのリードDeveloperのPaul M Jones氏のphp-framework-benchmarksというプロジェクトです。

SolarPHP自体はYiiのようにミニマムオーバーヘッドを特別アピールしているフレームワークではありませんが、Paul M Jones氏は数年前から定期的にこのような発表を行っていて、PHPでこの種のベンチマークに最も熱心に取り組んでる人だと思います。 Symfony2.0のリードコミッターのFabien氏もこのプロジェクトをforkしてSymfony2.0を加えています。

HelloWorldアプリのスペック

基準となるHelloWorldアプリは以下のようなものです。

  • 最小限のアプリ(フルアプリケーションでない)
  • 通常のconfig
  • アクションコードなし
  • ビューレイアウトもビューヘルパーもなし
  • スタティックなテキスト
  • ページキャッシュなし
  • データーベースなし

アプリケーションロジックを含まないが「HelloWorldに徹底的にカスタマイズしたされたものでもない」、ごく標準的仕様のミニマムアプリです。

このアプリのベンチマークにはどういう意味があるのでしょうか。また比較にはどういう点に注意が必要でしょうか。スライドから抜粋して紹介します。

ベンチマーク結果の比較

同じフレームワークでの比較

継続的ベンチマーキング、新しいアーキテクチャの採用には実行コストが伴う、その利点/コスト分析として。新旧バージョンでの比較統計。

違うフレームワークでの比較

他システムとの応答比較、アーキテクチャコスト比較等。速度比較をする場合は同じような”スタイル/クラス”(PHP5/デザインパターン/front,pageコントローラ/ビューの分離など)で比べるべきです。つまりCIとKohana、Cake/Lithium/Solar/Symfony/Yii/Zendで比較するのが妥当です。

以上は特にフレームワーク開発者にとって重要です。同じクラス/スタイルのアーキテクチャで同程度の機能で極端な速度さがあればそれは設計や実装に見直す点が有るという事に繋がるでしょう。

Webサイトは高度になり表現方法も多様化しています。1つのページを表示したあと、様々な”ページの断片”が用意されるようなGmailのようなページではそのつぶつぶのような断片的JSONの発行にそれぞれこのミニマムオーバーヘッドコストがかかってます。実行コストを最小化しつつ豊富な機能を実装するような技術的試みが続けられてると思います。12

結果を過大評価しない

スライドの中では「最も遅いフレームワークでも充分早い」と言っています。フレームワークの選定基準には様々な判断材料がありますが、この種のベンチ結果は重要でないことは前回記事のリファレンスのphp-markでも言っていますし、このプロジェクトでも言っています。Do not interpret the numbers alone http://code.google.com/p/phpmark/。この数字を過大評価してフレームワークを選定したり批評したりするのは適切ではないでしょう。

「フレームワーク対決」の結果などではなく 、開発や対策など特定の目的を持ったときに意味のある数字だと思いますがどうでしょうか。

ベンチマーク結果

スライドで紹介されてる結果です。

WARNING: ベンチマークはミスリードさせる可能性があります

フレームワークのスケール

アーキテクチャの似たフレームワーク同士では結果が似たような速度の傾向があります。
DBアクセスを含めたアプリで比較してるcakephperさんの記事と合わせて見ると一層興味深いのではないでしょうか。

ベンチマーク結果の利用

基本的にアプリケーションロジックが取り除かれたこのコードが性能の上限です。キャンペーンや有名サイトでの紹介など一時的高負荷が予想されるときの負荷対策の基準になりえます。3

XHGUI

コールグラフはXHGUIというツールを利用しました。xhprofをフォークしたプロファイリングツールで結果保存にDBを利用し、複数回のプロファイリングを管理できます。

apacheを毎回リスタートさせ、以下のコマンドラインで出た結果のうち良いものをグラフ描画用に使用しています。

ab -c 10 -t 10 http://examplle.com/helloWorld/

XHGUI - ヒストリー画面

XHGUI - プロファイル詳細画面

Hello Worldコールグラフ

本題のコールグラフです。コール数の少ない順に表示しています。
※クリックすると別画面で開きますが画像はとても大きいのに注意してください。

アーキテクチャの似通ったフレームワークはやはり似通ったグラフの大きさとcall数になってますが、Yiiだけ特別です。特筆すべきはCakePHPの前回調査(v1.2)と今回(v1.3)の違いでコール数が1/10以下になっています。4

Yii1.1.5 / 269 calls / 4853x6728 px

Kohaa3.0.9 / 365 calls / 3240x3451 px

CodeIgniter 2.0 / 447 calls / 3515x3250px

Lithium 0.9.9 / 732 calls / 5839x6856 px

SolarPHP 1.1.1 / 1,174 calls / 3228x5477 px

CakePHP 1.3.10 / 1,177 calls / 4767x5982 px

Symfony2 pr4 / 1,274 calls / 4595x7373 px

symfony1.4.8 / Calls 1,661 / 5837x5280 px

Zend Framework 1.11.9 / 1,799 calls / 7324x6819 px

  1. そういう意味でSymfony2のベンチ結果に注目していました []
  2. 前回の記事でのCakePHPやsymfonyはこの点にまったく配慮がなかったのですが、今回大きく改良しています。 []
  3. 高負荷のトップサイトなどでデータソースをRDBから他のキャッシュ向けストレージで利用する場合は、データベースの速度はあまり問題にならないでしょう。 []
  4. 前回が大すぎですね []

BEAR (Sunday)

| Comments

BEAR Sundayデザインメモ

PHP5.3+(またはPHP5.4)専用BEARのデザインメモをスライドとgist(テキストメモ)にしました。

アーキテクチャ的には「リソース指向」の更なる追求と「RESTful CQRS」が大きなテーマです。沢山のアイデアがあるのですが、今回はその2つを前回のBEAR1 to Saturday (2003, 2011)に続いて記事にします。

リソース指向フレームワーク

リソース指向で、MVCのモデルにあたる部分をリソースとして扱うだけでなく、ページやビューにあたる他のコンポーネントもリソースとして扱います。それによりコントローラー、ビューもリソース同様のテスト可能性や再利用性の向上が求められるのではないかと考えます。もし全てのコンポーネントがCLIで簡単にリクエストして結果が求められるのであれば、テストの記述も簡単なものになるのではないでしょうか。キャッシュや外部アプリ/ホストの利用も同様に有効になるのではと思います。1

CQRS (コマンドクエリ責務分離)


CQRSとは「コマンドクエリ責務分離」といって簡単にいうと参照と更新では責任や仕組みを分離しましょうというアーキテクチャパターンです。

Greg Young流CQRS – Mark Nijhof

例えばブログ記事の投稿を考えてみます。記事の投稿の時には、モデルはデータベースのテーブルの様々な項目に興味を持ちます。正規化され、結合され、複数のテーブルが更新されます。テーブルのコラムの情報はアトミック性をもち、関係性を持ちます。リレーショナルデータベースが有効に機能します。

ところが投稿されたこのブログ記事を読み込むときには、記事表示ページはこの関連付けされたリレーションを持った情報に興味を持たない事がほとんどです。結合、ソートされ、HTML化されたブログの記事の「文字列」が読めさえすれば読めればいいのです。この場合はただの1つの文字列がブログ記事IDから読み込めればいいということになります。つまり更新と参照では関心が異なるのです。

これを現状のBEAR(あるいは多くのフレームワーク)では通常はキャッシュとして実装し速度向上を目的にします。キャッシュは生成は簡単ですが破壊のタイミングが問題になることがあります。適当な秒数で破壊再生成したり、データ更新の時にモデルやコントローラが破壊します。

代わりにフレームワークがこれを行い、キャッシュの生成と破壊を透過にするだけでなく、キャッシュ生成のトリガーをユーザーでなくデータ作成、更新時にします。キャッシュというより、読み込み用データを書き込み時に作成すると言った方がピンと来るかもしれません。2

あるいは更新処理が、参照を行うまで保持されているモデルはどうでしょうか?。そのような”遅延更新モデル”ではブログを誰も見なければ、記事が実データベーステーブルにinsertされる事はありません。代わりに更新イベントハンドラ(BEARではリソースリクエストハンドラ)は誰かがそのブログを見てくれるその日まで、その書き込みイベントを保持してるはずです。3

REST meets CQRS

同じインターフェイスを持つ(RESTful)、実処理とそのリクエストが関心に応じて分離(CQRS)がされるという事はフレームワークやアプリケーションにとって他にどういう力をもたらすでしょうか?クエリー(参照)とコマンド(更新)はその実処理においてだけでなく、コーディングについても非対称性があります。多くの場合、更新参照のページの方がコーディングが簡単なのです。

あるモデルの更新と参照を違うプログラマが担う事ができます。参照データだけ用意すれば参照ページが機能するという事は、参照しか必要のないプロトタイプ開発にも役立てる事ができるでしょう。4

リクエストの公開宣言と境界の明確化、リクエストと実行の分離などCQRSの特徴の多くはフレームワークやアプリケーションのみならず、プロジェクトの進め方までに柔軟性を与える優れた可能性を持っているのではと考えます。

webアプリケーションをwebのアーキテクチャで構築する

CQRSのwebフレームワークというものは自分が知る限り数は少なく、またこれをRESTfulにというのはアイデアとしては語られても5 実装を知りません。

しかしCQRSは「コンポーネントよりむしろ接続に注目する」BEARを拡張するアーキテクチャとしては最良のものではないかと考えます。またこの実装はチャレンジな部分が大きく6 開発時に再検証や方針の再検討など必要な不確定部分が多いとは思います。スライドやGistではアイデアを大きく広げましたが、どこもまで、あるいはどのように実装するかは検討すべき点はまだまだあります。メモでかいたデザインのいくつかは実装、検討過程でボツになるかもしれません。7

色々な技術がありますが、やはりこれまでのBEARの開発と運用で学んだ「webアプリケーションをwebのアーキテクチャ8 で構築する」有用性、そこを忘れず軸にして進めたいと思います。

「クライアントやサーバーサイドがどんなに複雑に高度になってもHTTPという接続技術のアーキテクチャが基本的に変わらず機能し続けてきた」 – これにはまだまだ学べる事があると思っています。

  1. 例えばidを受け取ってそのIDのユーザーリソースとリンクされたその友達リソースを取得しHTML viiewリソースにリンクする「ページリソース」を考えてみます。ページはユーザーや友達リソースの値や実装には関心を持ちません。リソースの値の取得・セットではなく、接続性だけが記述してあります。そのように高度に疎結合なページではアプリケーションを超えた利用が可能です。写真サイトでもブログサイトでも「ユーザーと友達を表示する」というリソースの接続性が変わらないためです。写真サイトのユーザーページリソースをブログサイトのユーザーページが利用する事ができます。 []
  2. クローラーがインデックスをつくるように []
  3. つまり、遅延読み込みだけでなく、遅延作成、遅延更新といった遅延結合が可能になります。 []
  4. “この種のアーキテクチャを採用することで得られるメリットとしてもう1つ強調しておきたいものがあります。それは異なるチーム間で作業負荷を分担するのがきわめて簡単であるということです。これはチーム間に時差がある場合に特に言うことができます。ドメインロジックは正しくなければならないものです。これは単価の高い開発者を投入したいと思う場所でしょう。つまり、業務を理解し、正しいコーディングプラクティスを理解した開発者をということです。言っていることは分かりますよね?しかし、参照部分はそれほど重要ではありません。もちろん正しい必要はあるのですが、価値がある場所ではなく、素早く作って1、2年のうちに作り替えることができます。つまり、単価の低い開発者に作ってもらうことができるものだということです。ドメインに関する知識が多く求められることもなく、本当に重要なのは、GUIがどのように機能し、どのようなコマンドが使え、どのようなイベントが要求されるかということだけです。” – Greg Young流CQRS – Mark Nijhofより引用 []
  5. DDD/CQRS REST and CQRS []
  6. 今までもそうでしたが []
  7. その過程でよりよい実装アイデアがでるかもしれませんが []
  8. RESTful []

読了 ネットバカ

| Comments

この本は自分の長年の問いに、それが自分だけが感じてた疑問ではなく、多く語られ議論されてきたものだと知らせてくれ、その疑問にははっきりと用語が与えられそれぞれ深い洞察があるのだと知らせてくれた良書。本書の主題とは外れるところはあっても気になった引用等を記してみたい。

メッセージであるというメッセージ

「メディアはメッセージである」
- マーシャル・マクルーハン 1964年「メディア論」

本書で最初に引用されるのがマクルーハンのこの有名な一文。自分が初めて聞いたのは確か高校生の時だったと思う。それからあらゆるメディアの登場の度に引用され、語られて来たのを見ている。12

新しいコミニケーションテクノロジーが持つ変容のパワーをマクルーハンはただ認め、祝福してただけではないということだ。彼はこの脅威について警告もしていたーそしてその脅威について無知であることの危険性についても

メディアはメッセージである – 高校生の僕にはマクルーハンのこの謎めいたメッセージの真の意味を理解する事はできなかった。しかし強烈な印象を持っていてずっと離れない言葉だったのは確か。その意味に迫るんだろうと予感させる本書のプロローグに期待をした。

プラスティックな脳

plastic(形容詞) – 自由な形にできる, 塑造できる, 可塑性の;

1968年 – 「2001年宇宙の旅」が封切られた僕の生まれた年 – に26才のマイケルマーゼニックという博士号を取得したばかりの若者がサルの頭蓋骨に穴をあけ、神経可塑性の研究をし、驚くべき発見をする。

成人の脳は可塑的3で(後の研究者によれば「非常に可塑的」あるいは「とてつもなく可塑的」)で全ての神経回路 – 感情、視覚、聴覚、運動、思考、学習、認識、記憶、神経回路のすべてが変化しうる。しかし、「多忙者生存」といわれ与え続けた刺激にしたがってのみ変化する特質は、人の生存や活動に適したように成形されるわけではない。プラスティック(可塑的)ではあるがエラスティック(弾性がある)わけではない。

これはそれまで信じられて来た機械的な脳 – 成人になれば変わらぬ構造をする – を大きく覆すものだった。最初は四肢の喪失など神経の構造な大規模な構造変化のときに「アップデート」されると信じられた脳の変化も、どうもそうではなく健全で機能してる神経回路に対しても常時アップデートされてる事がわかる。4

脳は外界からの刺激によって、変化する。massiveに、物理的に。
本書の主題だ。

OECD高所得国の平均修学年数は10年を超える。
こんな事勉強して何になるんだろう?そう思った事の学生の時の自分に伝えたい。
脳に新しいスキーマを構築し、知性を深めるプロセスを繰り返す刺激を脳に与え続ける事が大事と。

インストゥメンタリスト

パーソナルコンピュータ、携帯電話、常時接続のような携帯電話のEメール、FB, Twitter、色々なテクノロジーやメディアが登場しマスコミで面白く便利なものとして、あるいは時には脅威を持って紹介され、その後こう締めくくられる「(技術は技術、それ以上であってそれ以下でもなく)結局はそれを使う私たち自身の問題なのかもしれません。」

僕は直感的に「これは間違ってる」と思ってた。支配権、決定権は使用者にあると心地よく聞こえるけど、その捉え方はちょっとイノセントすぎるというか違和感があった。強力なメディアやテクノロジーは、単に新しいオプションというだけではないんじゃないだろうか。 5

道具主義者(インストゥメンタリスト) – 道具は中立的人口物であり、ユーザーの意識的欲望に完全に従属するものだと考える人々である

どの道具を使うかについて個人や社会が様々な決定を行ってるとしても、テクノロジーと進歩の方向性とペースを我々が充分にコントロールしてきた事にならない。地図や時計を使う事を我々が「選んで」きてのだと主張するのは無理な話だ。(あたかもそうしないことができたのようでないか)また、そうしたテクノロジーの副作用を我々が「選んだ」と考えるのもなおさら無理なことである。そうした副作用の多くはそのテクノロジーが使用され始めた時にはまったく予想されてなかったのだから。政治学者ラングドン・ウィナーは次のように言う、。「近代社会の経験が我々に何かを教えてくれるとしたら、それはテクノロジーが人間の活動に対する補助でなく、その活動、およびその意味を再形成する、強力な力でもあるということだ」

その自分のもやもやした「結局は私たち自身の問題なのかも知れません」という「新たなテクノロジーは新しい選択肢にすぎない」という見方に対する自分の疑問にはっきり答える章がでてくる。

そしてそののちに、道具が我々を

われわれが道具とのあいだに結ぶ強い絆は、二つの方向に働く。テクノロジーがわれわれの延長になるにつれ、われわれもテクノロジーの延長になる。ハンマーを手にした大工は、自分の手を、ハンマーを使うようにしか使うことができない。その手は、釘を打ったり抜いたりするための道具になるのだ。双眼鏡を顔の前に持ってきた兵士は、そのレンズが見せてくれるものしか見ることができない。遠くは見えるようになるが、近くのものは見えなくなるのだ。

「我々は道具を作る。そしてそののちに、道具が我々を作る。」 – 1967  ジョン・カルキン (イエズス会神父、メディア学者)

「物は鞍にまたがり/人類を乗りこなす」 ラルフ・ウォルドー・エマソン

テクノロジーは我々を拡張し、再定義する。
技術は我々の延長にあるが、その我々も技術の延長にあるようになる。

映画や小説、ジャーナリズムはテクノロジーのこの側面を暗くとらえ警鐘する。しかし過去に置いても人とはずっとそういうものだった。映画「2001年宇宙の旅」で人類の祖先が骨をハンマーとして振り上げ(つまり初めて道具を使う生物が誕生して)その骨が宇宙船になり100万年をスキップするシーンがある。人と道具が不可分であった事を示す映画史上に残る名シーンだと思う。再理解した。

自分の疑問に確信が得られた。

新しいテクノロジーは決して単なるオプション、新しいー選択肢などでは無い。使用する者を拡張し、再定義する、未来の自分自身の一部だ。

テクノロジーの鈍感化効果

拡張には代償がある。

力織機が発明されたとき、織工たちは手で織ってたときよりもはるかに多くの布を一日で製造できるようになったが、手の器用さをいくらか犠牲にしてしまった。

これを経験してない現代人はいない。

増幅の代償として鈍感がもたらされる。ワープロソフトと車載ナビゲーションが何を増幅して何を鈍感にしただろう。先人達が一ヶ月かかって耕せなかった土地を一日で耕す、巨大トラクターの空調の聞いたケージはどんな鈍感をもたらすんだろうか。

テクノロジーの鈍感化効果を考察したのは自身も認めてるようにマクルーハンではない。これをもっとも雄弁かつ不吉な形で表現したのは、おそらく旧約聖書の詩編作者だ。

彼らの偶像は金銀の、
人の手になる者たちである。
口はあるが、語らない。
耳はあるが、聞こえない。
鼻はあるが、匂わない。
手はあるが、取らない。
足はあるが、歩かない。
のどから声を出すこともない。
それらを作った者たちは、それらに似ている。
それらを信じるものたちもみなそうである。

あらゆる場面で鈍感を強要する現代の都市生活。
鈍感は力なんだという事を言い始める人まででてきた。

記憶のトランスファー

作動記憶、ワーキングメモリと呼ばれ”る情報を一時的に保持し操作するためのシステム”は脳科学者達の初期の研究(1956)によると7つ±2の情報の断片しか処理できない。6 後にそれは2から4に訂正され、後に恐らく低い方の数字と見積もられる。人が同時に持てる記憶のエレメントは非常に限られている。7

コンピュータのプログラムを良く知る人は、一体人の脳というのはコンピュータプログラムとどのような点で似ていて、どのような点で似ていないかとか一度は考えた事があると思う。知性の正体とはどういうものであろうか。あるいはコンピュータの記憶と人の記憶は何が似ていて何が違ってるだろうか。

作動記憶と長期記憶は例えば、RAMとHDDのようなものなのだろうか。その例えはRAMの方はいいかもしれない。しかし長期記憶は全く違う。

コンピュータの世界では長期記憶と作動記憶は、保存方法に違いはあれど基本的にはビット単位で同じだ。予め容量には上限がある点も同じ。ところが脳は違う、全然違う。

知性の正体

長期記憶は、事実、印象、出来事を保管する巨大な倉庫のような役割だけを果たしていて、「思考や問題解決といった複雑な認知プロセスでは、ほとんど何の役割も果たしていない」とかつては考えられていた。だが、長期記憶がじつは理解を行う場でもあると、脳科学者達は気がついた。長期記憶はは事実だけでなく、複雑な概念、すわなちスキーマ(体系的図式)をも保管しているのだ。バラバラの断片をパターン化された知識へと組織する事によって、スキーマは我々の思考を豊かなものにする。「われわれの知的能力の大部分は、長きにわたって獲得したスキーマに由来している。専門的な概念を理解できるのは、それらの概念に関連するスキーマを持ってるからである」

作動記憶から長期記憶へと情報を差し替え、概念スキーマとして組み上げる能力によって、知性の深さは決定される

僕は知識を「知恵」に変換するプロセスが大切だと考えてた。(知恵とは、より抽象度、応用度が高い動的知識みたいなものと理解していた。) つまり本書で言う概念スキーマに近い。しかし本書ではその漠然とした考えに、実際には睡眠で見る夢やタンパク質、脳神経の物理現象など色々な要素が関わって物理的につくられていくという事が説明してあって大変興味深かった。知性や知恵とは概念というだけなくて、現象でもあった。

ソクラテスとプラトン、音声文化から文字文化へ

「王様、この文字というものを学べば、エジプト人たちの知恵はたかまり、もの覚えはよくなるでしょう。私の発見したものは、記憶と知恵の秘訣なのですから。」──しかし、タモスは答えて言った。

「たぐいなき技術の神テウトよ、技術上の事柄を生み出す力をもった人と、生み出された技術がそれを使う人々にどのような害をあたえ、どのような益をもたらすかを判別する力をもった人とは、別の者なのだ。いまもあなたは。文字の生みの親として、愛情にほだされ、文字が実際にもっている効能と正反対のことを言われた。なぜなら、人々がこの文字というものを学ぶと、記憶力の訓練がなおざりにされるため、その人達の魂の中には、忘れっぽい性質が植え付けられることだろうから。それはほかでもない、彼らは書いたものを信頼して、ものを思い出すのに、自分以外のものに彫りつけられたしるしによって外から思い出すようになり、自分で自分の力によって内から思い出すことをしないようになるからである。じじつ、あなたが発明したのは、記憶の秘訣ではなくて、想起の秘訣なのだ。また他方、あなたがこれを学ぶ人たちに与える知恵というのは、知恵の外見であって、真実の知恵ではない。すなわち、彼らはあなたのおかげで、親しく教えをうけなくてももの知りになるため、多くの場合ほんとうは何も知らないでいながら、見かけだけはひじょうな博識家であると思われるようになるだろうし、また知者となる代りに知者であるといううぬぼれだけが発達するため、つき合いにくい人間となるだろう。」
(プラトン『パイドロス』藤沢令夫訳 岩波文庫 134、135頁)

((新興メディア叩き in 古代ギリシア http://trushnote.exblog.jp/14087619/)) 8

紀元前3500年、シュメール人が楔形文字を発明し、知が話し言葉の「音声文化」から文字が思考表現の主要媒体となる「文字文化」へ移行するという人類史上最大のメディアシフトが起こる。9

「文字を学ぶ物達にあなたが与えるのは真の知恵ではなく知恵のようにみえるものでしかない。多くの事を知ってるようにみえるがたいていの場合何も知らない人になる。」 と「文字は記憶と知恵の秘訣を授けるものであるから、エジプトの民を賢くし記憶力を高めるであろう」と文字の有効性を説く技術の神テウトにエジプトの王は否定的な見方をする。「文字は人々の魂に忘れっぽさを植え付けるだろう。みずからのなかから思い出すのではなく、外に記されたものから呼び起こそうとするようになるだろう」

技術の神テウトはGoogleになった

5500年の時を経て技術の神テウトはインターネットに、Googleになった。

最初のマクルーハンの警鐘が思い起こされる。「脅威について無知であることの危険性」を語る人も出てきた。10

警告を受け入れ、脳や自分たちの変質を拒否するために検索エンジンの過度な使用をやめるべきか?そんな事はできない。
「技術は我々の延長にあるが、その我々も技術の延長」にもうなっている。携帯電話と同じ。それらは単なる選択可能な1オプションではない、使い手を変容させるメッセージだ。しかし脅威について無知である必要はない。ではどうすれば。

僕が面白いと思うのはこのソクラテスの話を書き記したのがプラトンという事だ。ソクラテスは弁論家 11でプラトンは書き手だ。

「うちなる考えを外なる記号に置き換える事によって、より浅い思考をするものにわれわれを変える恐れがある」というソクラテスの考えを共有しつつもプラトンは書き言葉の新しい可能性を認識していた。新しいメディアの脅威について警告を理解しつつ祝福もしていた。著作を残さなかったこのソクラテスの話を現代の我々が知る事ができるのは、そのテクノロジーをつかって文字として残したプラトンのおかげだ。

テウト神を警戒するエジプトの王の思慮深さは素晴らしいが、同時にプラトンのようでありたいと思った。崇拝でも否定でもなく、思慮深さを持ちつつ新しい可能性を見いだすところに本当の進歩があると思う。

タイトルの軽さから気楽に読み始めた本書は、脳科学という乗り物で人類と技術を旅する壮大な旅になった。ネット以前、ネット以後を経験した人類唯一の我々の世代全ての人にお勧めする。1964年のマクルーハンの警鐘に耳を傾けよう。

  1. いつか読もうと思ってるが僕はこのメディア論を読んだ事はない。しかし絶頂期でさえ読まれる事より引用される事の方が多かったそうだ。 []
  2. http://ja.wikipedia.org/wiki/%E3%83%9E%E3%83%BC%E3%82%B7%E3%83%A3%E3%83%AB%E3%83%BB%E3%83%9E%E3%82%AF%E3%83%AB%E3%83%BC%E3%83%8F%E3%83%B3 []
  3. 外から成形されやすい []
  4. つまり「ゲーム脳」とか言ってる人や記事を色眼鏡で見てた僕の認識にも”アップデート”が必要 []
  5. こっちをもっと巻き込むような…そもそも自分達使用者は本当に選んでいるんだろうかという疑問もあった。 []
  6. Miller (1956年)による「マジカルナンバー7±2」 []
  7. 短期記憶には感覚入力そのものの500msからせいぜい5秒程度の持続時間しか持たない非意識的な感覚記憶から、選択的注意を伴い意識化することで短期記憶貯蔵庫に15秒から30秒間保持されるものまで記憶保持時間に幅があります http://www.blog.crn.or.jp/report/04/52.html []
  8. パイドロス http://ja.wikipedia.org/wiki/%E3%83%91%E3%82%A4%E3%83%89%E3%83%AD%E3%82%B9 []
  9. 僕はイランイラク国境に近いジグラットでこの楔型文字を見た事がある。その時の感動がこの対話を知った事で深まった。 []
  10. Googleで人の記憶は変質する――米心理学者が発表 http://www.itmedia.co.jp/enterprise/articles/1107/15/news062.html []
  11. 生涯に渡って著作がない []

BEAR1 to Saturday (2003, 2011)

| Comments

Sundayへ

元々頭にあったBEARのラフなロードマップとしてv0.8までに機能的な実装を終え、v0.9でテストとパフォーマンスチューニング、リファクタリングを行いv1.0に繋げるというものでした。着々と続けてたのですが、(特にPHP 5.3に合わせた)PHPでの開発手法やwebアプリケーションフレームワーク世界の大きな潮流の変化を感じ、フルスクラッチで再構築する事を決めました。それをBEAR2にするのか、BEAR v1.0にするのか今はまだ未定ですが、そのコード名を”Sunday”にしました。(同時に現状今サービスしてるPHP5.2+のものが”Saturday”になりました。)

これを機会にこれまでを一度振り返って記録します。

BEAR1

最初のBEARの開発と利用は2003年12月です。自分でもびっくりするほど古いのですが、日本でMojaviが2004年後半から注目を集めたという事ですのでその1年前ぐらいです。

構成としてはページコントローラのシンプルなMVCのようなものでした。ページクラスをテンプレートパターンで必要メソッドを記述してメインクラスがページクラスをイベントに応じてコールし、ページの結果をHTMLとして出力する…そういう基本は今のBEARと同じです。

つまりメイン(クライアント)とページ(サービス)の分離が設計の中心です。モデルはクラス設計されてて、そのメソッド内(例えばUser::postEntry())でPEAR::DBを使ってSQLを発行してました。テンプレートエンジンにはSmarty、ページャーにPEAR::Pagerなどを用い、認証にTCI(電話認証)を使う今で言う携帯専用のSNSです。

これはインスパイアされたり、お手本にしたものがありません。何も知りませんでした。フレームワークという言葉もMVCもこれをつくったずっと後で知りました。複数人数での開発と、webの処理フローの単純さから、こういうのがいいんじゃないかと思って作ったのがこの時のBEARです。 1

なので自分のWebプログラミングのごく初期からフレームワークをつくってたということになります。

旧Bear

2005年5月19日にAUから携帯専用ブログDuo Blogがリリースされます2 これに用いたのが”Bear”です。しかしこの時のBear3 の反省は大きくリリース後に大改造を行い、アーキテクチャ的に今のに近い形にはなりました。まだ時代はPHP4です。

オブジェクトモデルを廃止して、自由にメソッドを持てないようにしました(統一インターフェイス)、その時のメソッドはたった2つ。「参照」と「アクション」だけでした。4リクエストは状態を持たず(ステートレスリクエスト)、機能毎に名前があり(アドレス可能性)、処理は処理を呼ぶ事ができ(レイヤード)処理を直接は呼ばないでそのモデルアクセスクラスが間接的に呼ぶようになっていて機能名と引き数と状態を持たないので簡単にキャッシュがつくれました(ULC$SS=Uniform-Layered-Client-Cache-Stateless-Server) 。今考えるとリソース指向設計(ROA)の特徴の多くを持っていたのですが、まだそのときそういう言葉や概念を知らず、手探りで良い設計を求めていました。

つまりモデル部分を関数ファイルにしたのです。URIは要は関数名です。関数はステートレスです。キャッシュ化もレイヤー化も簡単です。独立性もあり、利用クライアント対してに内部技術の暴露はありません。時代はPHPもOOPという感じでしたが、このモデル部分に関しては完全に逆を行きクラスから関数にしました。

単純ですがこのアーキテクチャは機能しました。スコープは制限され、モジュラー性は高まり、複数人での作業もスムーズになりました。学習、コーディング、メンテ、CPU、コストが低下しパフォーマンスもあがったように思えました。携帯用で始めましたが、PCや途中でやってきたAJAXブームにも(prototype.jsで)対応しました。ROR / CakePHPの大波も来たのですがマイペースで開発を続けました。

BEAR meets REST.

ある日、山本陽平さんのREST 入門 を知りました。5

自分が考えてた事、経験を通じて知った事、BEARの基本設計部分ですがその全てに名前付き解説がされてる事を知ります。これはとてつもない衝撃でした。BEARはRESTfulとしてつくってのではなくRESTfulだったのです。良いのでは信じてた設計のほとんどはHTTPで実装されてたものでした。自分では解決できなかった問題の解答もすでにありました。HTTP/RESTのと偉大さを改めて知り、そろそろと考えていたPHP5対応に明確な指針が生まれました。「リソース指向アーキテクチャ」です。

つまり、BEARは従来のMVCのアンチテーゼや、REST賛美から生まれた訳ではありません。アプリケーション要求と開発メンテ効率の最大化を求め、それを実践していて気がついたらRESTfulだったのです。

Saturday

デザイン

他のフレームワークに詳しい人や従来使ってた人に色々ヒアリングを行って追加機能も決めて行きました。例えばツーステップビューなどです。しかし不思議な事に他のフレームワークでは当たり前のフロントコントローラーやActive Record / ORMを検討してほしいという人はその時あまりいませんでした。それでもそれらを否定するものではなく、後から簡単にアドオンできるという目処があり標準で不採用は簡単に決まりました。

またリソースアクセスにhttpと同じようなURI6を使う事にしました。これにより処理系をスキーマとして切り替える事ができ、今まで固定されていた「関数」というただ一つのモデル・アーキテクチャの依存から抜けることができました。これは過去に作成した関数リソースを無駄にしないだけでなく、別アーキテクチャのレガシーモデルも同じように扱えることを意味していました。

URIでモデルとコントローラを接続するのは単にCとMにAというラッパーを差し込もうというのとは別の話です。URIスキーマのスキーマは本当の意味でのスキーマ(式型、図式、形式、シェーマ=ドイツ語)になり、接続に異なったソフトウエアパラダイムを持ち込む事が可能になりました。

Active Recordなどコンポーネントの利用の簡単さと機能の豊富さを語る時代ですが、むしろ、その接続と入れ替え可能性に注力しようという方針も立てました。SQLを記述するのがいいか、ORMがいいのかではなく、それらが選択可能で等価的であるという事が重要だと考えました。RESTfulがそれを実現します。

標準を選択

コンポーネントはなるべく標準的なもの広く使われているようなものをを選択するように考えました。迷ったのは開発終了のPEAR::DBに変わりにPDOを使うかPEAR::MDB2を使うかです。より標準的なのはどちらでしょうか?エクステンションであるPDOにも思えます。

結局、より抽象化された拡張機能とPEAR::Pagerと相性の良さそうなMDB2にしたのですが7 しかし重要なのはアプリケーション開発者がMDB2不使用を決めた場合に、それがマイナスにならないという事です。その場合はリソースのMDB2の依存はゼロにならないと行けません。

コード規約、ファイル配置、命名規則、それら全てをより標準的なものを採用しようという方針もたてました。これは難しくありません、(規約などの)フレームワークとしてPEARには圧倒的なプレゼンスがあり、Zendも基本的にはそれを踏襲していました。SolarPHPもそうでそれらに習うだけです。8 JSも標準で用意するbear,jsをprotyotype.jsベースからjQueryベースにしました。

DI

RESTと並んで初期に注力したのはDIです。今でもそうですが、PHPに要らないという意見が多くありまた色々な実装が出ては定着してないという現実もありました。しかし、最大の問題は「自分がよく分かってない」という事でした。(笑)9

PHPでは標準的でもなく、自分が使った事もなく、要求もされてないソフトウエアパラダイムを採用に引かれたのはもちろん理由があります。旧Bearであった問題の解決と、方針として立てた「入れ替え可能性」です。

ライブラリを整備していくと、様々な要求があります。例えばiPhoneのページ用意されてなかったら、表示するのは携帯用でしょうか? PC用でしょうか?そういう一つ一つの設定、ロジックに様々な要求がある場合にグローバルdifineや、configファイルをどんどん増やして行ってユーザーが選択可能にしていくのがway to goでしょうか?フレームワークコードにバグがあれば、あるいは機能追加したければユーザーはどういう行動をとる事ができるのがベストでしょうか?

インスタンス管理にも不満がありました。DRYといいながら同じようなシングルトンコードが色々なクラスに存在します。

コンストラクタの引き数のデフォルトはどうやって決めたら良いでしょうか?クラスに直接かけば値がハードコードされてます。グローバルdefineを山のように書いてたのが旧Bearです。クラスを生成するとき > アプリケーションのデフォルト > フレームワークのデフォルトと優先順位をもって初期値を決めたい時に、旧来のnew演算子や各メソッドが実装するsingleton/factoryパターンでは限界がありました。10

またどういうDI実装がいいのかというのも大きな問題でした。旧来のやり方の弊害はJavaでも語られていました。JavaではXMLは「アジャイル」ですがPHPでは「コードの方がアジャイル」とも言えます。欲しいのは形式としての正しさよりその効果です。

Solar::dependency()

そこで大きく惹かれたのはPHP5専用フレームワークのSolarPHPのDependency Injectionです。ただし、そのままではちょっとmagicすぎるという印象を持ち、そこでインジェクターメソッドというコンストラクトの後に呼ばれる注入メソッド(実際は初期化メソッド)を生成時に必ず呼ばれるようにし、そこで利用オブジェクトをサービスロケータ経由でPull(Dependency Pull)する仕組みのものを設計しました。そのメソッドは外部から選択可能です。生成時に呼ばれるという点ではコンストラクトインジェクションに近いものですが、選択可能であるという点でそのデメリットを補い、コンテナを不要にできるのではと考えました。

「いや、しかしクラス自身が依存オブジェクトをとってきてこれって注入..?」「外部インジェクターが使えるし…」色々思いましたが、しかし重要なのは外部から依存(利用)オブジェクトをコントロールできるのか?という事です。利用メソッドから見れば、どっかの誰かが準備してくれて、利用オブジェクトは準備されてます。それがコントロールできるのが重要です。言葉の厳密性に多少目をつぶりSolarPHPのDIの模倣し、より単純にしてDIが解決することを別のより簡単な手段で解決しようと試みました。

それともう一点、初学者がスムーズにたとえば模倣から入れるかということでした。

学習コストの低減は大きなテーマです。そこで「制御の反転って知ってますか?」「依存性の注入とはですねえ、DIコンテナってのがありまして」というようにパラダイムの説明抜きには入れなうような事態に抵抗がありました。「BEAR::dependencyってnewみたいなもんなんですよ、クラス名と初期値でオブジェクトが得られます。」という風に旧来のnew演算子からスムーズに入れそうな気がした事も採用動機になりました。

ほとんどをSolar::depedncy()から学びました。リスペクトもありメソッド名を変えずにそのままにしてます。最初に恩恵を受けたのはBEAR自身です。BEARではこの技術の適用範囲に制限を持ちませんでした。後にデバック用やテスト用の別コンポーネントを持つときにも大きな効用を発揮しました。

現在発表されているPHP5.3+用のフレームワークの多くにDI 11が導入されていて、この方針の方向性にある程度の確信が生まれます。また、DIの他にも以下のPHP5.3+フレームワークの多く(またはいくつか)で見られる特徴もありました。

  • オートローダーOnly (PSR-0)
  • アノテーション
  • 非フルスタック指向
  • 非スタティックコール指向
  • ユニバーサルコンストラクタ
  • グローバルdefineの原則廃止
  • ミニマムレイテンシー(速度)の重視
  • 遅延評価(レイジーロード)

リソースオブジェクト

BEARで様々につかわれてるDTO(データー転送用オブジェクト)がRO(リソースオブジェクト)です。このDTOはcode,header, bodyといったリソースの値を保持するのも大きな役割ですが、リクエストに対する統一インターフェイスとリンク機能を備えてるのが特徴です。リソース内部で何が起ころうともクライアントには同じフォーマットのものが帰ってくるのはHTTPをモデルにしています。ユーザーのURI入力間違いだろうと、内部のサーバーエラーであろうとwebサーバーは同じフォーマット(code, header, body)のデータを処理するだけで、そのリクエスト状態に関心を持つことはありません。

新しく最もROA的に思えたの機能がリンクです。Aタグの無いWWW世界を想像してみてください。あるいは情報と情報の関係性を利用者側ですべて把握する必要がある情報システム。それらに命を吹き込むのがリンクです。その点、今のBEARのリンク実装はまだ大きなイノベーションの余地があると考えています。

Saturday公開

2008年7月31日に初めてBEARを外部に公開します。PHP5.2対応の初のリリースです。
最初の動機はごく単純で、社内リポジトリ/wikiだと外注さんが見れないというものでした。

そしてSundayへ

ここまでが簡単にまとめた「BEARの今まで」です。
これまでの成果と反省をしROAを再確認しつつSundayに繋げたいと思っています。

そのために現在起こっているWebアプリケーションの開発手法の変化、アプリケーション要求、クライアントとアウトプットの多様化、PHPの言語仕様等、ソフトウエア設計の外側の世界もバランスのとれた態度を示さなければなりません。解決としてのRESTfulがその解答になると思っています。

  1. PEARコンポーネントのグルー(当時言葉知りませんでしたが)が必要だとは思っていました。BEARの名前の由来の一つでもあります。 []
  2. テレビCMでは仲間由紀恵がブログもできるよ!とCMしていました []
  3. 数年ぶりのPHP、Webプログラミング []
  4. これはモデルがあり、つまりDBの「ビュー」と「ストアドプロシージャ」です。PC用でASPのレガシープロジェクトをPHPでモバイル用に作り替えたときに、この構成の疎結合性が大変有効に機能するのに注目しました []
  5. 2005年4月の新しいとはいえない記事ですがこの時まで知りませんでした。 []
  6. 迷ったURIテンプレートの採用は見送りました []
  7. 今ならDoctorine DBALでしょうか []
  8. その点何故SymfonyやCakePHPがああいう俺俺規則なのかはさっぱり分かりませんでした。 []
  9. 多くの解説記事は特定のDI実装と強く結ばれた話ばかりで、真の本質的なところや使用すべき用語がなかなか分かりませんでした。分離の原則を実現する技術の解説なのに皮肉な話です []
  10. New Considered Harmfulという記事を読んだのもその頃です。 []
  11. またはDIの解決しようとする問題を解決する技術 []

PHPもやらなきゃJenkins

| Comments

改名なのかフォークなのか、とにかくHudsonプロジェクトはHudsonとJenkinsに分かれました。(開発者はフォークではなく改名と主張していて、この辺りの話はinfoQが詳しいようです。http://www.infoq.com/jp/hudson )
※前回の記事で紹介したphp-hudson-template はphp-jenkins-template に変わっています。

またPHPUnitで有名なSebastian氏がbuld.xmlを自動で作成してくれるPPW (PHP Project Wizard )というツールをリリースして、面倒だったプロジェクトの設定ファイルbuld.xmlの作成がとても簡単になりました。

Sebastian氏はhttp://jenkins-php.org/というPHPでJenkinsを使うためのガイドをするサイトも用意しています。以下はその補足です。

Jenkins インストール

本体

  1. Jenkinsをインストール
    Jenkins公式サイト http://jenkins-ci.orgあらダウンロードしてインストールします。Windows/OSX/Ubuntu等のネイティブインストーラーもあるのでそれを利用するのがいいんじゃないでしょうか。自分はOSXのネイティブインストーラを使用しました。以下の例はOSXでのものです。

起動はCLIで行います。
$ java -jar /Applications/Jenkins/jenkins.war

http://localhost:8080%E3%81%A7Jenkins%E3%81%AE%E7%94%BB%E9%9D%A2%E3%81%8C%E7%A2%BA%E8%AA%8D%E3%81%A7%E3%81%8D%E3%82%8B%E3%81%AF%E3%81%9A%E3%81%A7%E3%81%99%E3%80%82

続いてJenkins用プラグインをインストールをします

wget http://localhost:8080/jnlpJars/jenkins-cli.jar java -jar jenkins-cli.jar -s http://localhost:8080 install-plugin checkstyle java -jar jenkins-cli.jar -s http://localhost:8080 install-plugin clover java -jar jenkins-cli.jar -s http://localhost:8080 install-plugin dry java -jar jenkins-cli.jar -s http://localhost:8080 install-plugin htmlpublisher java -jar jenkins-cli.jar -s http://localhost:8080 install-plugin jdepend java -jar jenkins-cli.jar -s http://localhost:8080 install-plugin plot java -jar jenkins-cli.jar -s http://localhost:8080 install-plugin pmd java -jar jenkins-cli.jar -s http://localhost:8080 install-plugin violations java -jar jenkins-cli.jar -s http://localhost:8080 install-plugin xunit java -jar jenkins-cli.jar -s http://localhost:8080 install-plugin git java -jar jenkins-cli.jar -s http://localhost:8080 safe-restart mv jenkins-cli.jar /Applications/Jenkins/

次はPHPのツールです。

sudo pear channel-discover pear.pdepend.org sudo pear channel-discover pear.phpmd.org sudo pear channel-discover pear.phpunit.de sudo pear channel-discover components.ez.no sudo pear channel-discover pear.symfony-project.com sudo pear install pdepend/PHP_Depend sudo pear install phpmd/PHP_PMD sudo pear install phpunit/phpcpd sudo pear install phpunit/phploc sudo pear install PHPDocumentor sudo pear install PHP_CodeSniffer sudo pear install --alldeps phpunit/PHP_CodeBrowser sudo pear install --alldeps phpunit/PHPUnit sudo pear install phpunit/ppw

PHP Project Wizard (PPW)を使ってbuild.xmlを作成

プロジェクト用の設定ファイルbuild.xmlファイルを作成します。リポジトリに対して一つ用意します。通常はパッケージのトップディレクトリに配置します。

作成はPPWというツールを使えば簡単です。

例えばzf2の場合はbuild.xmlが用意されていませんが、下記のようにppwコマンドでzf2/build.xmlとzf2/phpunit.xml.distが作成できます。

$ git clone git://git.zendframework.com/zf.git zf2 $ cd zf2 $ ppw -name zf2 --source library/Zend/Acl --tests tests/Zend/Acl/ --bootstrap tests/Bootstrap.php --phpcs Zend .

Wrote build script for Apache Ant to ./build.xml
Wrote configuration for PHPUnit to ./phpunit.xml.dist

$ cd zf2 $ ant
buildがうまくできると、zf2/build/に出力結果が保存されます。作成されたcode browserを開いてみましょう。
$ open build/code-browser/index.html

Jenkinsで試す前にまずantでbuildができるか試してみるのがいいと思います。

Jenkinsでプロジェクト作成

プロジェクトのテンプレート作成

jobフォルダにgitでプロジェクトテンプレートを用意します。

$ cd ~/.hudson/jobs $ git clone git://github.com/sebastianbergmann/php-jenkins-template.git php-template $ java -jar /Applications/Jenkins/jenkins-cli.jar -s http://localhost:8080 reload-configuration

新規プロジェクト作成

利用可能にしたプロジェクトテンプレートを指定して、新規プロジェクトを作成します。

次の画面で、ビルド無効化 のチェックを外し、ソースコード管理システムを編集してソースコードレポジトリ情報を設定します。プロジェクト設定を保存し、ビルドを実行します。

まとめ

  • HudsonはJenkinsに
  • Sebastian氏がppwというbuild.xml作成ツールとプロジェクトテンプレートを用意し利用が楽に
  • PHPコミュニティに多大な貢献をしてる氏に感謝
  • CIしよう

PHPもやらなきゃHudson

| Comments

Hudsonとは

Hudsonとは「継続的インテグレーションサーバー」です。継続的インテグレーションとは

Extreme Programmingに端を発し,Martin Fowlerによって広められた概念で,狭義には,別々に開発された部品を持ち寄ってお互いの動作を検証する「統合テスト」を早い段階から恒常的に行うことを指します。

Hudsonを使ったアジャイルな開発入門より

原文: Continuous Integration

公式サイトからも説明を引用します。

Hudsonは、ソフトウェアのビルドやcronで起動するジョブなどの繰り返しのジョブの実行を監視します。これらのうち、Hudsonは現在次の2つのジョブに重点を置いています。

  1. 継続的なソフトウェアプロジェクトのビルドとテスト: つまり、CruiseControlやDamageControlが行うこと。 一言で言えば、Hudsonは、容易ないわゆる「継続インテグレーションシステム」を提供し、開発者が変更をプロジェクトに統合でき、ユーザーがより新しいビルドを容易に取得できるようにします。自動化された継続的なビルドは、生産性を向上させます。
  2. 外部で起動するジョブの実行監視: cronによるジョブやprocmailのジョブで、リモートマシンで動作するものも含みます。例えばcronについて言えば、出力をキャプチャーした定期的なメールだけ受信し、こつこつとそれを見ます。おかしくなっていることに気がつくかどうかは、すべてあなた次第です。Hudsonは出力を保存し、 いつおかしくなったのか容易に把握することができるようになります。

PHPの実行にコンパイルは必要ありません。では動的言語のPHPが必要とするビルドとはなんでしょうか?

HudsonはAPIドキュメントの作成やユニットテスト、コード解析ツール、コード重複発見ツールなど開発支援ツールやソフトウエア品質向上のためのソフトウエアを自動実行しレポートにまとめ、CI (継続的インテグレーション) システムとして機能します。

具体的にはレポジトリからソースを取得し、各種テストやソフトウエア品質解析ツールを実行し、その出力をまとめ管理します。

以下の作業がクリック一つあるいは定期的に実行され、その結果や履歴をwebで確認することができます。

  • ユニットテスト
  • テストカバレッジ
  • コード規約チェック
  • 重複コードチェック
  • ドキュメント作成
  • ソフトウエアメトリクス(品質測定)
  • コード分析

※ソフトウエアメトリクスとは?

以下のリンクをご覧ください

またソフトウエアメトリクスには様々な議論があるようです。

Hudsonのインストール

Hudson公式サイト http://hudson-ci.org/ からDownload hudson.warの hudson.warファイルをダウンロードします。

Download hudoson.war


起動

$ java -jar /Applications/hudson.war
http://localhost:8080/ で確認します。こんな画面でHudson先生が出現するはずです。

立ち上げたまま

立ち上げた直後のHudson実行画面


必要なHudsonプラグインのインストール

CI(継続開発)のためのテストや品質測定ツールをインストールします。様々なプラグインがありますが、ここでは以下のHudsonプラグインをインストールします。またそれぞれのプラグインはPHPのライブラリに依存し、別途PEARでのインストールが必要です。

その他以下のプラグインも結果表示等のためにインストールします。

  • HTML Publisher (for publishing the PHPUnit code coverage report, for instance)
  • Template Project (for using php-hudson-template as a template for Hudson jobs)
  • Violations (for processing various logfiles)

立ち上げたHudoson CIサーバーをから以下のコマンドでインストールします。

$ sudo java -jar hudson-cli.jar -s http://localhost:8080 install-plugin checkstyle dry htmlpublisher jdepend pmd template-project violations xunit clover

Installing checkstyle from update center
Installing dry from update center
Installing htmlpublisher from update center
Installing jdepend from update center
Installing pmd from update center
Installing template-project from update center
Installing violations from update center
Installing xunit from update center
Installing clover from update center

PHPのツールのインストール

Hudsonプラグインが必要とする出力する(多くはXML)PHPのツールです。全てPEARパッケージでインストールします。

pear channel-discover pear.pdepend.org pear channel-discover pear.phpmd.org pear channel-discover pear.phpunit.de pear channel-discover components.ez.no pear channel-discover pear.symfony-project.com pear install pdepend/PHP_Depend-beta pear install phpmd/PHP_PMD-alpha pear install phpunit/phpcpd pear install PHPDocumentor pear install PHP_CodeSniffer pear install --alldeps phpunit/PHP_CodeBrowser-alpha pear install --alldeps phpunit/PHPUnit

build.xml

buildを行うために各ツールの設定等を記したxmlファイル build.xmlを作成します。
https://github.com/sebastianbergmann/php-hudson-template/blob/master/README.markdownのbuild.xmlファイル(sebastianbergmann氏のOject Freezerというパッケージ用のもの)を参考にし自分が対象とするパッケージ用のbuil.xmlを作成します。デフォルトのパスは “リポジトリルート/build.xml” です。

それぞれのツールのマニュアルを参照してbuild.xml内の引数を設定します。

※例えばコード規約の設定をPEARにしたいのならphpcsのセクションを以下のようにします。

<!-- Generate checkstyle.xml --> <target name="phpcs"> <exec executable="phpcs" output="/dev/null"> <arg line="--report=checkstyle --report-file=${basedir}/build/logs/checkstyle.xml --standard=PEAR BEAR" /> </exec> </target>

Hudsonでプロジェクト作成

まずphp-hudson-templateというSebastian氏作成のプロジェクトテンプレートをgitで取得します。
これはプロジェクトの設定のひな形です。使用しないで全て手動で設定する事も可能です。

$ cd ~/.hudson/jobs
$ git clone git://github.com/sebastianbergmann/php-hudson-template.git

php-hudson-templateに掲載されている”Use publishers from another project “の方法では何故かうまくいかなかったので、ひな形をコピーして新規作成。

  • Hudsonをリスタート
  • 「既存ジョブのコピー」でphp-hudson-templateを入力して作成。これができないときは上記のgitでの取得ができていない。
  • “ソースコード管理システム” を指定
  • Ant-based build を設定

それでもphpmdがうまくいかない。antをコマンドラインで実行してみる。

$ cd ~/.hudson/jobs/< プロジェクトフォルダ>/workspace $ ant phpmd phpmd: [exec] Invalid field modifiers given, allowed modifiers are IS_PUBLIC, IS_PROTECTED, IS_PRIVATE and IS_STATIC. [exec] Result: 1

とエラーがでる。
恐らくPEAR等のPHP4コードで修飾子がついてないところで例外が出てるのではと当たりをつけてみる。とりあえず消極的解決法として該当例外をコメントアウト。

/pdepend/PHP/Depend/Code/ASTFieldDeclaration.php
のsetModifiers()メソッド内の例外スローをコメントアウト
if (($expected &#038; $modifiers) !== 0) { //throw new InvalidArgumentException( // 'Invalid field modifiers given, allowed modifiers are ' . // 'IS_PUBLIC, IS_PROTECTED, IS_PRIVATE and IS_STATIC.' //); }
再度$ ant phpmd

BUILD SUCCESSFUL
Total time: 1 second

通った。~/.hudson/build/logs/pmd.xmlも作成されている。

build成功

以下はbuild成功した各ツールの結果画面です。

API Document

Code Browser

Code Coverage

PMD警告

重複コード警告

メトリックス1

ユニットテスト

リンク

GDD 2010 Pacman問題

| Comments

GDD 2010 Pacman Lv.3

GDD 2010 Dev Quiz

GDD2010のDev Quizの最終問題Pacman。DevQuizは見事不合格に終わったのですが、挑戦の記録というのと、提出後ですがLv.3が解けるようになったので記念に記します。

PHPで

普段使っているPHPでコーディングしました。WebではなくCLIです。1ファイルでコンソールでアニメが表示されるようにしました。現在のコードでのハイスコアはLv1, Lv2, Lv3それぞれ、41, 210, 489です。これは人の手をともわなないAI探索のみでのスコアです。

Pacman Lv.3 demo1

Pacman AI

最初にPacmanに適当な移動ロジックを組み込んでモンスターのいない迷路でドットが全部とれるかというところから始めました。

「誘惑に弱いけど好奇心が強く、失敗してもすぐに反省する」

こういうのどうだろう。Pacmanに性格をつけしてAIっぽい動きすれば面白いんじゃないかと。つまり…

  • 誘惑に弱い=隣接するドットを食べること優先
  • 好奇心=足跡を記録してなるべく行っていないところに行く
  • すぐに反省=反復強化学習

こんな感じです。実装にうつります。

まず移動可能な場所(上下左右、0〜4カ所)を調べます。0〜2カ所なら自動的に決めます。

0カ所=動けないので停止。
1カ所=その方向に移動。
2カ所=来た方向と逆の方向に(途中で反転しない)

※基本的にモンスターと同じです。

3、4カ所ある場合

移動可能な場所のうち、次の優先順位で方向を決めました。

  • 隣接するところにエサがあればその方向
  • 隣接するところで一回しか行ってなければその方向
  • 直線でエサが見えればその方向
  • 上記のどれにもあたらなければランダム

とりあえずこんなもので、この優先順位を変えたりできる仕組みもあればと。

モンスターのいない迷路を走らせてみる

迷路を自走させてみるとそれなりに効率的に走りドットを全て食べてくれます。ちょっと安心。
パックマンというより自走式掃除機ルンバのような動きです。みててなかなか面白い。

あとはモンスター…どうだろ?

モンスターは基本、壁と考えてみる。単にその場所にいけないという点で壁と同じ。つまりパックマン視点だと迷路が1フレーム単位で変化するようなもの。

元々迷路全体をしっかり把握してるわけでなし、上記のその場その場のロジックでドットが全部食べれるのだからまあ何万回も走らしたら全部適当に食べてくれるだろう…と。2

モンスターを組み込んでみる

取りかかるとパックマン自走のコーディングのヒントと思えるようなとこが多々あり…先にモンスターからやれば良かったとすぐに気づきます。orz

パックマン自走コードにも手をなおしつつ、それでも一つ一つモンスターを組み込みます。

例えば敵V3 はこんな感じ。

敵 V

  • 敵から見た自機の相対位置を (dx, dy) と表すものとします。次のルールを上から順に適用し、最初に選ばれた方向に移動します。

  • dy ≠ 0 でかつ dy の符号方向にあるマスが進入可能であれば、その方向に移動します。

  • dx ≠ 0 でかつ dx の符号方向にあるマスが進入可能であれば、その方向に移動します。
  • 現在位置の 下、左、上、右 の順で最初に進入可能なマスの方向に移動する。

こういうABSでの割り算で方向を出すとか、中学生の時にBASICで書いて以来かも…とか懐かしみながら組み込んで行きます。

1
$ddy = $dy/abs($dy);

敵L、敵R

面倒そうなモンスターのロジックが出てきました。現在の方向からみての右、左です。

敵 L

現在位置への進入方向から見て相対的に 左、前、右 の順で最初に進入可能なマスの方向に移動します。

「右向いてるキャラの左は上」を求めるような実装です。普段しているWebのプログラミングで現在の方向からの相対的な「右」とか「左」は中々でてきません。

どうしようか、「もし今右を向いてたら、”右”は下方向」「下を向いてたら右は…」こういうのを4つ書くかなあ…いや…

…それもちょっと…そもそも「右」とは何かっていうと..うーん、国語辞書でも苦しい感じの説明だよなあ….コーヒー飲みつつ色々考えながら窓の外を一分眺めます。

…配列で相対方向?

結局、「時計回り」の配列を用意して利用する方法を考えました。

1
2
3
4
5
6
    /**
     * 時計回り配列
     *
     * @var array
     */
    protected $_clockwiseDirection = array(array(0, 1), array(-1, 0), array(0, -1), array(1, 0));

array(0, 1)、array(-1, 0)…と下、左、上、右という時計回りの方向が並んでる配列(↓←↑→)です。

↓、←、↑、→と右回りの配列をつくって、1つ進んだら右回り、1つ後退したら左回り。

時計方向で並んでる配列の中で自分の「となりの右」が現在の方向から見た「右」です。配列の添字を1つ進めると右、減らすと左になります。一番右や左ではぐるっとまわって反対側の配列をとります。

うまく行きそうです。

モンスターはこれに優先順位があります。このようなコードになりました。4

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
    /**
     * モンスターL
     *
     * 現在位置への進入方向から見て相対的に 左、前、右 の順
     *
     * @param array $maze    迷路
     * @param int   $pacmanX パックマンX座標
     * @param int   $pacmanX パックマンY座標
     *
     * @return array
     */
    private function _moveL(array $maze, $pacmanX, $pacmanY)
    {
        $directionStrategy = $this->_getRelativeDirection(array(-1, 0, 1));
        $this->_setPositionStatus($maze, $directionStrategy, true);
        $result = array($this->_wayToGo[0]['dx'], $this->_wayToGo[0]['dy']);
        return $result;
    }
     */

14行目:左(-1)、前(0)、右(1)を優先順位にした絶対方向座標が$directionStrategyとしてつくられます。
15行目: 迷路配列をみて、優先順位($directionStrategy)どおりの順番で壁ではないかチェックして移動可能な座標の配列をつくります。
16行目: 移動可能で優先順位の最も高い座標が配列の最初(0)にはいりっているのでそれを取り出します。

「特定の優先方向配列を用意して、その移動可能状態を調べ、個別ロジックによって移動方向を決定」…

これがキャラクターの移動の基本戦略となり、Pacmanにも利用しました。

モンスターの動きデバック用の迷路をつくり、動きを一つ一つ確認。コンソールでのPHPプログラムでしたがusleep()関数と画面クリアを使えば、コンソールでもアニメーションが見られるのがわかりました。

1
 echo "\033[;H\033[2J"; // これで画面クリア

いよいよモンスターのいる迷路をパックマンが自走

予想と違ってなかなか厳しい。最初はクリアできませんでした。….レベル1でさえも!!
当初、レベル3は現状の反復学習なし実装だと無理と確信します。

ところがレベル1は無理なのですが、レベル2をやると割とあっさりクリアできました。

???

debugモードで観察すると。効率よくするための「パックマンAI」が逆に正解ルートを必ず行けなくしてるのがわかりました。

レベル1の方針を変えます。

“ランダム”

何も考えずランダムに動かしてを繰り返すと数秒で最適解41点にたどりつけました。orz
レベル1、レベル2なんとか解けてそろそろタイムリミット。解けないLv.3の得点とソースコードを添えて提出しました。

不合格、そしてLv.3クリア

枠や開催場所によってはメアド入れたら通ったという方もいる中、GDD2010の参加不合格通知が届きます。結果からいうとパックマンはやる必要がないくらいの配点でした。5 自走パックマンに一生懸命で他の問題にほとんど手をつけてないのも原因でした。

しかししばらくして、やりかけだったプログラムの興味70%、勉強20%、パックマンLove10%という気持ちがLv.3解へのコーディングへと向かわせます。

反復学習の実装です。

深さ優先探索

深さ優先探索のイメージ

プログラムしたときは手法は思いついきで適当にした方法なのですが、実装が完全に終わって今日読んだオライリーの アルゴリズムクイックリファレンスで分かったのがこれは深さ優先探索というものなんだそうです。 6

wikiで以下のように説明されてます。

深さ優先探索(ふかさゆうせんたんさく、英: depth-first search, DFS、バックトラック法ともいう)は、木やグラフを探索するためのアルゴリズムである。アルゴリズムは根から(グラフの場合はどのノードを根にするか決定する)始まり、バックトラックするまで可能な限り探索を行う。

オライリー本からも引用します。

「出来る限り前方に進み、同じ状態を二度と本文せずに、目的状態への経路を見つけようとする。探索木によっては、盤面の数が大変多くなるので、深さ優先探索は最大探索深さが前もって定まっているような場合にのみ実用的になる。深さ優先探索は、これから訪問する盤面状態をスタックに積み、訪問した盤面状態を集合に保持して、管理する。深さ優先探索は、スタックから未訪問の盤面状態を取り出し、可能な手を用いて、次の盤面状態集合を計算して木を拡張する。目標状態に到達したら、探索は終了する。」

Pacmanでこう実装していました。7

  • ブランチは移動可能な場所が3つ以上あったとき
  • ブランチがあるときにそのゲーム状態をスタックに積む。
  • 失敗したらスタックからゲームを取り出し失敗する前まで戻ってゲーム再開
  • 自分の行動は記録し、失敗を繰り返さない

※ゲーム全体はゲームオブジェクトとして1つの変数になってるので、それをarray_pushで配列としてスタックに積みます。8

探索木

実際の動きはこのようになります。

h mark 行き先(h)をマークし pushed 失敗しても前回の状態に戻れるように前回ゲームをスタックにつみ h moved 進みます hh mark 行き先(hh)をマークし...  以下同様 h pushed hh moved hhk mark hh pushed hhk moved hhkk mark hhk pushed hhkk moved hhkkl mark hhkk pushed hhkkl moved hhkkl GAME OVER ゲームオーバーになったので hhkk is poped 積まれたゲームを上からとりだし hhkkl is marked 移動可能方向を確認。hhkklという方角はすでに探索してるのでいきません。 hhkk GAME OVER 移動できる方角がもうないのでここでもゲームオーバーです。 hhk is poped その前につまれたゲームを取り出し ....以下同様 hhkk is marked hhk GAME OVER hh is poped hhk is marked hhl mark

これを繰り返せば全ての木の枝が探索できるはずです。9

Lv.1でも全経路は無理?

ところがそんなに簡単ではありません。Lv1くらい無条件の全経路を調べられないかと思いましたが、やはり難しそうです。この動画が少し参考になるでしょうか。階乗の計算量は膨大です。

GDD Pacman LV.1 Deep-First Search

Lv2, Lv3では3つ以上の交差点でのみブランチをつくることにしました。また時間によるゲームオーバーからはスタックからゲームを取り出すことなしに、最初からやり直すのを繰り返す事にしました。10 11

幅優先探索

試してはいませんが、他の検索の紹介を。幅優先探索も同じ様に同じ状態を2度と訪問しないようにして、ゲーム状態を初期状態から近い順に評価します。深さ優先と違うのは、探索開始点から近いところから順に探索をしていくところです。深さ優先探索がスタックを使用するのに対して、幅優先探索はキューをする違いを理解すれば実装のイメージがわくのではないでしょうか。12

Lv.2, Lv.3の探索木

交差点だけブランチをつくるLv.2とLv.3でタイムオーバーまでゲームをしたら大体100ゲーム超ぐらいのゲームがスタックされます。Lv.2、Lv.3もあまり変わらなくLv.3がやや多いくらいです。

以下はタイムオーバーまで5回プレイした例です。

Lv.3 Score:284/296 Point:284 Game:700/700 Stacked Game:107 Score:277/296 Point:277 Game:700/700 Stacked Game:103 Score:277/296 Point:277 Game:700/700 Stacked Game:111 Score:269/296 Point:269 Game:700/700 Stacked Game:107 Score:267/296 Point:267 Game:700/700 Stacked Game:101 Lv.2 Score:131/147 Point:131 Game:300/300 Stacked Game:107 Score:129/147 Point:129 Game:300/300 Stacked Game:112 Score:120/147 Point:120 Game:300/300 Stacked Game:111 Score:127/147 Point:127 Game:300/300 Stacked Game:101 Score:135/147 Point:135 Game:300/300 Stacked Game:100

なかなか良いスコアです。これが一瞬で出るので、これを一晩ぶん回せば…と期待してしまいますがここからのスコアはなかなか伸びません。13 3ドット取り残しとゲームクリアではクイズの配点としての差はあまりないでしょうけど、プログラムの性能としては格段に違います。

それでもLv.3クリアが一瞬から数分程度でできるまでの性能になりました。僕のGDD2010はここで終わりです。

最後に

昔の事ですがファミコンやゲームボーイでアクションゲームをいくつか作ったことがあります。14 中高生の時もBASICや機械語15 でこういうキャラクタベースのゲームを趣味でつくったりしてました。16

思えばそれ以来のゲームプログラミングです。これからもこういうプログラムはする事はなかなかないと思うので貴重な機会となりました。参加はなりませんでしたが#gdd2010jpで他の参加者の話を聞いたりコードを見たりするのも楽しかったです。GDD2010JP DevQuiz ソース晒し祭りでもPHPや自動探査で解いてるコードが少ないのとどういう風にコーディングしたらいいかさっぱり分からないという方もTLで散見したりで、多少なりとも参考になればと思い記事をかきました。

最後にasannouさんの作製の素晴らしいガジェット17 を貼付けて終わりにします。Lv.3クリアのベストスコアです。18 長文読んで頂いてありがとうございました。

ソースコード

ダウンロードはcode pad

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
1110
1111
1112
1113
1114
1115
1116
1117
1118
1119
1120
1121
1122
1123
1124
1125
1126
1127
1128
1129
1130
1131
1132
1133
1134
1135
1136
1137
1138
1139
1140
1141
1142
1143
1144
1145
1146
1147
1148
1149
1150
1151
1152
1153
1154
1155
1156
<?php
/**
 * GDD 2010 DevQuiz Pacman for PHP 5.3
 *
 * @author @koriym
 */
/**
 * デバック用関数 p
 */
function p($values = '') {
    $trace = debug_backtrace();
    $file = $trace[0]['file'];
    $line = $trace[0]['line'];
    $method = (isset($trace[1]['class'])) ? " ({$trace[1]['class']}" . '::' . "{$trace[1]['function']})" : '';
    $fileArray = file($file, FILE_USE_INCLUDE_PATH);
    $p = trim($fileArray[$line - 1]);
    unset($fileArray);
    preg_match("/p\((.+)[\s,\)]/", $p, $matches);
    $varName = isset($matches[1]) ? $matches[1] : '';
    //    $label = "$varName in {$file} on line {$line}$method";
    $label = "on line {$line}$method";
    $values = is_bool($values) ? ($values ? "true" : "false") : $values;
    echo "\n{$varName}=[". print_r($values, true) . "] $label\n";
}
/**
 * キャラクターインターフェイス
 *
 * @param string $MyChar 文字
 * @param int    $y      y座標
 * @paramint     $x      x座標
 *
 */
interface Character_Interface{
    public function __construct($myChar, $y, $x);
}
/**
 * キャラクター
 *
 */
abstract class Character implements Character_Interface
{
    /**
     * キャラ文字
     *
     * @var string
     */
    protected $_char;
    /**
     * X座標
     *
     * @var int
     */
    protected $_x;
    /**
     * Y座標
     *
     * @var int
     */
    protected $_y;
    /**
     * X移動
     *
     * @var int
     */
    protected $_dx = 0;
    /**
     * Y移動
     *
     * @var int
     */
    protected $_dy = 0;
    /**
     * 移動可能座標
     *
     * @var array
     */
    protected $_wayToGo = array();
    /**
     * 移動可能場所数
     *
     * @var int
     */
    protected $_wayToGoCount = 0;
    /**
     * 時計回り配列
     *
     * @var array
     */
    protected $_clockwiseDirection = array(array(0, 1), array(-1, 0), array(0, -1), array(1, 0));
    /**
     * コンストラクタ
     *
     * @param string $myChar
     * @param int    $x
     * @param int    $y
     */
    public function __construct($myChar, $x, $y)
    {
        $this->_myChar = $myChar;
        $this->_x = $x;
        $this->_y = $y;
    }
    /**
     * ポジション取得
     *
     * @return array
     */
    public function getPosition(){
        return array($this->_x, $this->_y);
    }
    /**
     * データ取得
     *
     * @return array
     */
    public function get()
    {
        return array($this->_myChar, $this->_x, $this->_y, $this->_dx, $this->_dy);
    }
    /**
     * キャラクタの移動可能状態をセット
     *
     * @param array $maze              迷路
     * @param array $directionStrategy 移動方向戦略
     *
     * @return void
     */
    protected function _setPositionStatus($maze, $directionStrategy)
    {
        $cnt = 0;
        $this->_wayToGo = array();
        $wayToGo = array();
        foreach ($directionStrategy as $item) {
            list($dx, $dy) = $item;
            $x = $this->_x + $dx;
            $y = $this->_y + $dy;
            $isExist = isset($maze[$y][$x]);
            if ($isExist &#038;&#038; $maze[$y][$x] === '.' || $maze[$y][$x] === ' ') {
                $this->_wayToGo[] = array('dy' => $dy, 'dx' => $dx);
                $cnt++;
            }
            $this->_wayToGoCount = $cnt;
        }
    }
}
/**
 * パックマン
 *
 */
class Pacman extends Character
{
    /**
     * 方向履歴
     *
     * @var string
     */
    private $_joyStick = '';
    /**
     * 移動足跡
     *
     * @var array
     */
    private $_footprintMap = array();
    /**
     * 移動足跡初期化
     *
     * @param int $width 幅
     * @param int $hight 高さ
     *
     * @return void
     */
    public function setFootprintMap($width, $hight)
    {
        for ($i = 0; $i < $hight ; $i++) {
            $this->_footprintMap[$i] = array_fill(0, $width, 0);
        }
    }
    /**
     * パックマン移動
     *
     * @param array        $maze     迷路
     * @param int          $time     タイム
     * @param Pacman_Dicon $strategy DIコンテナ
     *
     * @return void
     */
    public function move($maze, $time, Pacman_Dicon $dicon)
    {
        $this->_wayToGo = array();
        $funcMoveStrategy = $dicon->get('move');
        $this->_setPositionStatus($maze, $dicon->get('direction'));
        try {
            list($this->_dx, $this->_dy, $takeSnapShot) = $r = $funcMoveStrategy($this->_x, $this->_y, $this->_dx, $this->_dy, $maze, $this->_wayToGoCount, $this->_wayToGo, $this->_footprintMap, $this->_joyStick);
        } catch (Exception $e) {
            Pacman_Quiz::$pacmanThought[$this->_joyStick][$this->_dy][$this->_dx] = true;
            throw $e;
        }
        if ($takeSnapShot) {
            $c = $this->getJoyStickChar($this->_dx,$this->_dy);
            Pacman_Quiz::$pacmanThought[$this->_joyStick][$this->_dy][$this->_dx] = true;
        }
        $this->_x += $this->_dx;
        $this->_y += $this->_dy;
        $this->_joyStick .= self::getJoystickChar($this->_dx, $this->_dy);
        $this->_footprintMap[$this->_y][$this->_x]++;
        $result = array($this->_x, $this->_y, $this->_dx, $this->_dy, $takeSnapShot);
        return $result;
    }
    /**
     * 方向からジョイスティック名を取得
     *
     * @param int $dx
     * @param int $dy
     *
     * @return string
     */
    public static function getJoyStickChar($dx, $dy) {
        $joyStickCharacters = array('j', 'h', 'k', 'l', '.');
        $direction = array_search(array($dx, $dy), array(array(0, 1), array(-1, 0), array(0, -1), array(1, 0), array(0,0)));
        $result = $joyStickCharacters[$direction];
        return $result;
    }
    /**
     * 足跡文字列取得
     *
     * @return string
     */
    public function getJoystick()
    {
        return $this->_joyStick;
    }
}
/**
 * パックマンDIコンテナ
 *
 */
class Pacman_Dicon
{
    /**
     * サービス取得
     *
     * @param string $service サービス取得名
     *
     * @return mixed
     */
    public function get($service)
    {
        switch ($service) {
            case 'direction':
                $directionStrategy = array(array(-1, 0), array(0, -1), array(1, 0), array(0, 1));
                shuffle($directionStrategy);
                return $directionStrategy;
                break;
            case 'move':
                $function =  function ($x, $y, $dx, $dy, $maze, &#038;$wayCnt, $wayToGo, $footprintMap, $joystick)
                {
                    switch ($wayCnt) {
                        case 0:
                            // 動けない
                            return array(0, 0, false);
                        case 1:
                            // 行き止まりなので唯一いける方向へ
                            $togo = $wayToGo[0];
                            return array($togo['dx'], $togo['dy'], false);
                        case 2:
                            // バックじゃない方
                            $isReverse0 = ($dx === ($wayToGo[0]['dx'] * -1) &#038;&#038; $dy === ($wayToGo[0]['dy'] * -1));
                            $isReverse1 = ($dx === ($wayToGo[1]['dx'] * -1) &#038;&#038; $dy === ($wayToGo[1]['dy'] * -1));
                            if ($isReverse0 || $isReverse1) {
                                $i = !$isReverse0 ? 0 : 1;
                                return array($wayToGo[$i]['dx'], $wayToGo[$i]['dy'], false);
                            } else {
                                break;
                            }
                        case 3:
                        case 4:
                            // 交差点で考える
                            break;
                    }
                    // 同じ行動はとらない
                    $wayToGoFiltered = array();
                    foreach ($wayToGo as $toGo) {
                        if (!isset(Pacman_Quiz::$pacmanThought[$joystick][$toGo['dy']][$toGo['dx']])) {
                            $wayToGoFiltered[] = $toGo;
                        } else {
                            $wayCnt--;
                        }
                    }
                    if (!$wayToGoFiltered) {
                        // どこも行けない
                        throw new Exception('no_way_to_go');
                    } else {
                        $wayToGo = $wayToGoFiltered;
                    }
                    foreach ($wayToGoFiltered as $toGo) {
                        if ($maze[$y + $toGo['dy']][$x + $toGo['dx']] === '.') {
                            return array($toGo['dx'], $toGo['dy'], true);
                        }
                    }
                    foreach ($wayToGoFiltered as $toGo) {
                        if ($footprintMap[$y + $toGo['dy']][$x + $toGo['dx']] < = 1) {
                            return array($toGo['dx'], $toGo['dy'], true);
                        }
                    }
                    foreach ($wayToGoFiltered as $toGo) {
                        $dx = $toGo['dx'];
                        $dy = $toGo['dy'];
                        while (true) {
                            if ($maze[$y + $dy][$x + $dx] === '.') {
                                $find = true;
                                break;
                            } elseif (!isset($maze[$y + $dy][$x + $dx]) || $maze[$y + $dy][$x + $dx] === '#') {
                                $find = false;
                                break;
                            }
                            $dx++;
                            $dy++;
                        }
                        if ($find === true) {
                            return array($toGo['dx'], $toGo['dy'], true);
                        }
                    }
                    $dx = $wayToGoFiltered[0]['dx'];
                    $dy = $wayToGoFiltered[0]['dy'];
                    return array($dx, $dy, true);
                };
        }
        return $function;
    }
}
/**
 * パックマンDIコンテナ 問題1用
 *
 */
class Pacman_Dicon_Q1 extends Pacman_Dicon
{
    /**
     * サービス取得
     *
     * @param string $service サービス取得名
     *
     * @return mixed
     */
        public function get($service)
    {
        switch ($service) {
            case 'direction':
                //$directionStrategy = array(array(-1, 0), array(0, -1), array(1, 0), array(0, 1), array(0, 0));
                $directionStrategy = array(array(-1, 0), array(0, -1), array(1, 0), array(0, 1));
                shuffle($directionStrategy);
                return $directionStrategy;
            case 'move':
                $function =  function ($x, $y, $dx, $dy, $maze, &#038;$wayCnt, $wayToGo, $footprintMap, $joystick)
                {
                    if ($wayToGo) {
                        $dx = $wayToGo[0]['dx'];
                        $dy = $wayToGo[0]['dy'];
                        return array($dx, $dy, true);
                    } else {
                        throw new Exception('no_way_to_go');
                    }
                };
        }
        return $function;
    }
}
/**
 * モンスター
 */
class Monster extends Character
{
    /**
     * 最初?
     *
     * @var bool
     */
    private $_init = true;
    /**
     * モンスターL
     *
     * @var string
     */
    private $_j = 'L';
    /**
     * 移動
     *
     * @param array $maze
     * @param int   $pacmanX
     * @param int   $pacmanY
     *
     * @return void
     */
    public function move($maze, $pacmanX, $pacmanY)
    {
        $this->_wayToGo = array();
        if ($this->_init === true) {
            //時刻 t = 0 においては、初期位置の 下、左、上、右 の順で最初に進入可能なマスの方向に移動します。
            $this->_init = false;
            $this->_setPositionStatus($maze, $this->_clockwiseDirection);
            $this->_dy = $this->_wayToGo[0]['dy'];
            $this->_dx = $this->_wayToGo[0]['dx'];
        } else {
            //下、左、上、右 の順
            $this->_setPositionStatus($maze, $this->_clockwiseDirection);
            switch ($this->_wayToGoCount) {
                case 1:
                    // 行き止まりなので唯一いける方向へ
                    $togo = $this->_wayToGo[0];
                    $this->_dy = $togo['dy'];
                    $this->_dx = $togo['dx'];
                case 2:
                    // バックじゃない方
                    $isReverse = ($this->_dx === ($this->_wayToGo[0]['dx'] * -1) &#038;&#038; $this->_dy === ($this->_wayToGo[0]['dy'] * -1));
                    if ($isReverse) {
                        $this->_dy = $this->_wayToGo[1]['dy'];
                        $this->_dx = $this->_wayToGo[1]['dx'];
                    } else {
                        $this->_dy = $this->_wayToGo[0]['dy'];
                        $this->_dx = $this->_wayToGo[0]['dx'];
                    }
                    break;
                case 3:
                case 4:
                    // モンスターに応じて
                    $method = '_move' . $this->_myChar;
                    list($this->_dx, $this->_dy) = $this->$method($maze, $pacmanX, $pacmanY);
                    if ($this->_dx == 0 &#038;&#038; $this->_dy == 0){
                        p("error $this->_myChar");exit();
                    }
                    break;
                default:
            }
        }
        $this->_y += $this->_dy;
        $this->_x += $this->_dx;
        // もし以前パックマンがいたところに移動したら”王手”。パックマンは前にモンスターがいたところには移動できない。仮に壁にする。
        $makeMeWall = ($this->_x === $pacmanX &#038;&#038; $this->_y === $pacmanY);
        $wall = $makeMeWall ? array('x' => $this->_x - $this->_dx, 'y' => $this->_y - $this->_dy) : false;
        $result = array($this->_x, $this->_y, $this->_myChar, $wall);
        return $result;
    }
    /**
     * モンスターV
     *
     * 敵から見た自機の相対位置を (dx, dy) と表すものとします。次のルールを上から順に適用し、最初に選ばれた方向に移動します。
     *
     * 1. dy ≠ 0 でかつ dy の符号方向にあるマスが進入可能であれば、その方向に移動します。
     * 2. dx ≠ 0 でかつ dx の符号方向にあるマスが進入可能であれば、その方向に移動します。
     * 3. 現在位置の 下、左、上、右 の順で最初に進入可能なマスの方向に移動する。
     *
     * @param array $maze    迷路
     * @param int   $pacmanX パックマンX座標
     * @param int   $pacmanX パックマンY座標
     *
     * @return array
     */
    private function _moveV(array $maze, $pacmanX, $pacmanY)
    {
        $dx = $pacmanX - $this->_x;
        $dy = $pacmanY - $this->_y;
        // 1
        if ($dy !== 0 ) {
            $ddy = $dy/abs($dy);
            if (isset($maze[$this->_y + $ddy][$this->_x]) &#038;&#038; $maze[$this->_y + $ddy][$this->_x] !== '#') {
                return array(0, $ddy);
            }
        }
        // 2
        if ($dx !== 0 ){
            $ddx = $dx/abs($dx);
            if (isset($maze[$this->_y][$this->_x + $ddx]) &#038;&#038; $maze[$this->_y][$this->_x + $ddx] !== '#') {
                return array($ddx, 0);
            }
        }
        // 3
        $result = array($this->_wayToGo[0]['dx'], $this->_wayToGo[0]['dy']);
        return $result;
    }
    /**
     * モンスターH
     *
     * 敵 V とほぼ同じです。唯一異なるのは 、進行方向を決めるルールのうち
     * 最初の二つのルールの適用順序が入れ替わるところです。
     *
     * @param array $maze    迷路
     * @param int   $pacmanX パックマンX座標
     * @param int   $pacmanX パックマンY座標
     *
     * @return array
     */
    private function _moveH(array $maze, $pacmanX, $pacmanY)
    {
        $dx = $pacmanX - $this->_x;
        $dy = $pacmanY - $this->_y;
        // 2
        if ($dx !== 0 ){
            $ddx = $dx/abs($dx);
            if (isset($maze[$this->_y][$this->_x + $ddx]) &#038;&#038; $maze[$this->_y][$this->_x + $ddx] !== '#') {
                return array($ddx, 0);
            }
        }
        // 1
        if ($dy !== 0 ) {
            $ddy = $dy/abs($dy);
            if (isset($maze[$this->_y + $ddy][$this->_x]) &#038;&#038; $maze[$this->_y + $ddy][$this->_x] !== '#') {
                return array(0, $ddy);
            }
        }
        // 3
        $result = array($this->_wayToGo[0]['dx'], $this->_wayToGo[0]['dy']);
        return $result;
    }
    /**
     * モンスターL
     *
     * 現在位置への進入方向から見て相対的に 左、前、右 の順
     * @param array $maze    迷路
     * @param int   $pacmanX パックマンX座標
     * @param int   $pacmanX パックマンY座標
     *
     * @return array
     */
    private function _moveL(array $maze, $pacmanX, $pacmanY)
    {
        $directionStrategy = $this->_getRelativeDirection(array(-1, 0, 1));
        $this->_setPositionStatus($maze, $directionStrategy, true);
        $result = array($this->_wayToGo[0]['dx'], $this->_wayToGo[0]['dy']);
        return $result;
    }
    /**
     * モンスターR
     *
     * 現在位置への進入方向から見て相対的に 右、前、左  の順
     *
     * @param array $maze    迷路
     * @param int   $pacmanX パックマンX座標
     * @param int   $pacmanX パックマンY座標
     *
     * @return array
     */
    private function _moveR(array $maze, $pacmanX, $pacmanY)
    {
        $directionStrategy = $this->_getRelativeDirection(array(1, 0, -1));
        $this->_setPositionStatus($maze, $directionStrategy, true);
        $result = array($this->_wayToGo[0]['dx'], $this->_wayToGo[0]['dy']);
        return $result;
    }
    /**
     * モンスターJ
     *
     * 最初は敵Lの行動、次回は敵Rの行動、さらに次回はまた敵Lの行動、と繰り返します。
     *
     * @param array $maze    迷路
     * @param int   $pacmanX パックマンX座標
     * @param int   $pacmanX パックマンY座標
     *
     * @return array
     */
    private function _moveJ(array $maze, $pacmanX, $pacmanY)
    {
        $method = "_move{$this->_j}";
        $result = $this->$method($maze, $pacmanX, $pacmanY);
        $this->_j = ($this->_j === 'L') ? 'R' : 'L';
        return $result;
    }
    /**
     * 進行方向に対しての相対方向(左右など)戦略の配列を作成
     *
     * @param interger $relativeDirection 1=右, -1=左
     *
     * @return array
     */
    private function _getRelativeDirection($relativeDirections)
    {
        $result = array();
        $currentDirection = array($this->_dx, $this->_dy);
        foreach ($relativeDirections as $relativeDirection) {
            $pos = array_search($currentDirection, $this->_clockwiseDirection);
            $directionIndex = $pos + $relativeDirection;
            if ($directionIndex === -1 ) {
                $directionIndex = 3;
            }
            if ($directionIndex === 4 ) {
                $directionIndex = 0;
            }
            array_push($result, $this->_clockwiseDirection[$directionIndex]);
        }
        return $result;
    }
}
/**
 * ゲーム
 *
 */
class Pacman_Game
{
    /**
     * スコア
     *
     * @var int
     */
    private $_score = 0;
    /**
     * クリアスコア
     *
     * @var int
     */
    private $_clearScore = 0;
    /**
     * 制限時間
     *
     * @var int
     */
    private $_timeOut = 50;
    /**
     * 時間
     *
     * @var int
     */
    private $_time = 0;
    /**
     * パックマン
     *
     * @var Pacman
     */
    private $_pacman;
    /**
     * モンスター
     *
     * @var array
     */
    private $_monsters = array();
    /**
     * 迷路
     *
     * @var array
     */
    private $_maze = array();
    /**
     * キャラ付迷路
     *
     * @var array
     */
    private $_mazeWithChar;
    /**
     * キャラなし迷路
     *
     * @var array
     */
    private $_mazeWithoutChar;
    /**
     * パックマンX座標
     *
     * @var int
     */
    private $_pacmanX;
    /**
     * パックマンY座標
     *
     * @var int
     */
    private $_pacmanY;
    /**
     * デバック?
     *
     * @var bool
     */
    private $_debug = false;
    /**
     * デバックアニメーション時間
     *
     * @var int
     */
    private $_debugTime = 0;
    /**
     * デバックアニメーション?
     *
     * @var bool
     */
    private $_debugAnimation = false;
    /**
     * パックマンDIコンテナ
     *
     * @var Pacman_Dicon
     */
    private $_pacmanDicon;
    /**
     * __clone
     */
    public function __clone()
    {
        $this->_pacman = clone $this->_pacman;
        $cloneMonsters = array();
        foreach ($this->_monsters as $monster) {
            $cloneMonsters[] = clone $monster;
        }
        $this->_monsters = $cloneMonsters;
    }
    /**
     * 迷路から必要なオブジェクトやプロパティをセット
     *
     * +Pacmanオブジェクト
     * +Monsterオブジェクト
     * +ドットの数
     * +キャラクターがいない迷路
     */
    private function _injectFromMaze($maze)
    {
        $point = 0;
        $this->_pacman = null;
        $this->_monsters = array();
        for ($y = 0; isset($maze[$y]); $y++) {
            for($x = 0 ; $x < count($maze[$y]); $x++) {
                $char = $maze[$y][$x];
                if ($char === '@') {
                    $this->_pacman = new Pacman($char, $x, $y);
                    $this->_pacman->setFootprintMap(count($maze[0]), count($maze));
                    $maze[$y][$x] = ' ';
                } elseif ($char === '.') {
                    $point++;
                } elseif (preg_match('/[A-Z]/', $char, $matches)) {
                    $this->_monsters[] = new Monster($char, $x, $y);
                    $maze[$y][$x] = ' ';
                }
            }
        }
        $this->_clearScore = $point;
        $this->_maze = $maze;
    }
    /**
     * 問題1
     *
     * @return void
     */
    public function _injectQuestionOne()
    {
        $maze = array();
        $maze[] = $this->_split('###########');
        $maze[] = $this->_split('#.V..#..H.#');
        $maze[] = $this->_split('#.##...##.#');
        $maze[] = $this->_split('#L#..#..R.#');
        $maze[] = $this->_split('#.#.###.#.#');
        $maze[] = $this->_split('#....@....#');
        $maze[] = $this->_split('###########');
        $this->_injectFromMaze($maze);
        $this->_pacmanDicon = new Pacman_Dicon_Q1();
        $this->_timeOut = 50;
    }
    /**
     * 問題2
     *
     * @return void
     */
    public function _injectQuestionTwo()
    {
        $maze = array();
        $maze[] = $this->_split('####################');
        $maze[] = $this->_split('###.....L..........#');
        $maze[] = $this->_split('###.##.##.##L##.##.#');
        $maze[] = $this->_split('###.##.##.##.##.##.#');
        $maze[] = $this->_split('#.L................#');
        $maze[] = $this->_split('#.##.##.##.##.##.###');
        $maze[] = $this->_split('#.##.##L##.##.##.###');
        $maze[] = $this->_split('#.................L#');
        $maze[] = $this->_split('#.#.#.#J####J#.#.#.#');
        $maze[] = $this->_split('#L.................#');
        $maze[] = $this->_split('###.##.##.##.##.##.#');
        $maze[] = $this->_split('###.##.##R##.##.##.#');
        $maze[] = $this->_split('#................R.#');
        $maze[] = $this->_split('#.##.##.##.##R##.###');
        $maze[] = $this->_split('#.##.##.##.##.##.###');
        $maze[] = $this->_split('#@....R..........###');
        $maze[] = $this->_split('####################');
        $this->_injectFromMaze($maze);
        $this->_pacmanDicon = new Pacman_Dicon();
        $this->_timeOut = 300;
    }
    /**
     * 問題3
     *
     * @return void
     */
    public function _injectQuestionThree()
    {
        $maze = array();
        $maze[] = $this->_split('##########################################################');
        $maze[] = $this->_split('#........................................................#');
        $maze[] = $this->_split('#.###.#########.###############.########.###.#####.#####.#');
        $maze[] = $this->_split('#.###.#########.###############.########.###.#####.#####.#');
        $maze[] = $this->_split('#.....#########....J.............J.......###.............#');
        $maze[] = $this->_split('#####.###.......#######.#######.########.###.#######.#####');
        $maze[] = $this->_split('#####.###.#####J#######.#######.########.###.##   ##.#####');
        $maze[] = $this->_split('#####.###L#####.##   ##L##   ##.##    ##.###.##   ##.#####');
        $maze[] = $this->_split('#####.###..H###.##   ##.##   ##.########.###.#######J#####');
        $maze[] = $this->_split('#####.#########.##   ##L##   ##.########.###.###V....#####');
        $maze[] = $this->_split('#####.#########.#######.#######..........###.#######.#####');
        $maze[] = $this->_split('#####.#########.#######.#######.########.###.#######.#####');
        $maze[] = $this->_split('#.....................L.........########..........R......#');
        $maze[] = $this->_split('#L####.##########.##.##########....##....#########.#####.#');
        $maze[] = $this->_split('#.####.##########.##.##########.##.##.##.#########.#####.#');
        $maze[] = $this->_split('#.................##............##..@.##...............R.#');
        $maze[] = $this->_split('##########################################################');
        $this->_injectFromMaze($maze);
        $this->_pacmanDicon = new Pacman_Dicon();
        $this->_timeOut = 700;
    }
    /**
     * 初期化
     *
     * @return void
     */
    public function init()
    {
        // init
        $this->_time = 0;
        $this->_score = 0;
        $this->_mazeWithChar = $this->_mazeWithoutChar = $this->_maze;
        $this->_pacmanX = $this->_pacmanY = 0;
    }
    /**
     * パックマン取得
     *
     * @return Pacman
     */
    public function getPacman()
    {
        return $this->_pacman;
    }
    /**
     * 1ゲームプレイ
     *
     * @return array
     */
    public function runGame()
    {
        // init
        $lastGame = clone $this;
        $isHit = $isTimeOut = $isClear = false;
        Pacman_Quiz::$gameCount++;
        // main
        while (!$isHit &#038;&#038; !$isClear) {
            $this->_time++;
            $isTimeOut = ($this->_time >= $this->_timeOut);
            if ($isTimeOut === true) {
                break;
            }
            // モンスター
            $this->_runMonsters();
            // pacman
            list($this->_pacmanX, $this->_pacmanY, $dx, $dy, $takeSnapShot) = $this->_pacman->move($this->_mazeWithChar, $this->_time, $this->_pacmanDicon);
            if ($this->_mazeWithoutChar[$this->_pacmanY][$this->_pacmanX] === '.') {
                $this->_score++;
                $this->_mazeWithoutChar[$this->_pacmanY][$this->_pacmanX] = ' ';
            }
            // 描画
            $this->_mazeWithChar[$this->_pacmanY- $dy][$this->_pacmanX - $dx] = ' ';
            $this->_mazeWithChar[$this->_pacmanY][$this->_pacmanX] = '@';
            if ($takeSnapShot === true) {
                //  パックマンが曲がるのでスナップショット
                $joy = $lastGame->getPacman()->getJoystick();
                array_push(Pacman_Quiz::$games, $lastGame);
            }
            // 後処理
            $isClear = ($this->_score == $this->_clearScore);
            //            $restDot = $this->_clearScore - $this->_score;
            //            $isTimeOut = ($restDot > $this->_timeOut - $this->_time || $this->_time >= Pacman_Quiz::$minClearTime + $restDot);
            $isHit = $this->_hitCheck($this->_pacmanX, $this->_pacmanY);
            if ($this->_debug) {
                $this->_showCompositScreen($this->_mazeWithoutChar);
                usleep($this->_debugTime);
                if ($this->_debugAnimation) {
                    echo "\033[;H\033[2J"; // clear screen
                }
            }
            $joy = $this->_pacman->getJoystick();
            $lastGame = clone $this;
        }
        if ($isTimeOut) {
            //            $this->_checkRepeatGame();
            $this->_gameOver('TimeOut', $this->_mazeWithChar);
            return true;
        }
        if ($isHit) {
            throw new Exception('hit');
            return;
        }
        if ($isClear) {
            if ($this->_time >= Pacman_Quiz::$minClearTime) {
                return false;
            }
            Pacman_Quiz::$minClearTime = $this->_time;
            $this->_gameOver('Clear', $this->_mazeWithChar, true);
            return;
        }
        return;
    }
    /**
     * ゲームを繰り返していないかdebugチェック
     *
     * @return void
     */
    private function _checkRepeatGame()
    {
        static $joystat = array();
        $joy = $this->_pacman->getJoystick();
        $key = md5($joy);
        if (isset($joystat[$key])) {
            $joystat[$key]++;
            echo "repeated. $joy\n";
        } else {
            $joystat[$key] = 1;
        }
    }
    /**
     * モンスター移動
     *
     * @return void
     */
    private function _runMonsters()
    {
        $this->_mazeWithChar = $this->_mazeWithoutChar;
        foreach ($this->_monsters as $monster) {
            list($monsterX, $monsterY, $myChar, $wall) = $monster->move($this->_mazeWithoutChar, $this->_pacmanX, $this->_pacmanY);
            $this->_mazeWithChar[$monsterY][$monsterX] = $myChar;
            if (is_array($wall)) {
                $this->_mazeWithChar[$wall['y']][$wall['x']] = '#';
            }
        }
    }
    /**
     * ハイスコアセット
     *
     * @return void
     */
    public function setHighScore()
    {
        if ($this->_score > Pacman_Quiz::$highscore) {
            Pacman_Quiz::$highscore = $this->_score;
        }
    }
    /**
     * Game Over画面出力
     *
     * @param string $reason       ゲームオーバーの理由
     * @param string $mazeWithChar キャラクター付迷路
     *
     * @return void
     */
    public function _gameOver($reason, $mazeWithChar, $forceShow = false) {
        if ($forceShow || $this->_score > Pacman_Quiz::$highscore) {
            Pacman_Quiz::$highscore = $this->_score;
            echo $this->_showCompositScreen($mazeWithChar);
            $msg = ($reason === 'clear') ? "Game Clear" : "GAME OVER($reason)" ;
            echo "High Score:" . Pacman_Quiz::$highscore . ' total:'. Pacman_Quiz::$gameCount . " $msg\n\n";
        }
        return;
    }
    /**
     * ヒットチェック
     *
     * @param $pacmanX パックマンX座標
     * @param $pacmanY パックマンY座標
     *
     * @return bool
     */
    public function _hitCheck($pacmanX, $pacmanY)
    {
        $isHit = false;
        foreach ($this->_monsters as $monster) {
            list($monsterX, $monsterY) = $monster->getPosition();
            if ($pacmanX === $monsterX &#038;&#038; $pacmanY == $monsterY) {
                $isHit = true;
            }
        }
        return $isHit;
    }
    /**
     * デバックモード
     *
     * @param int $time アニメーションタイム
     *
     * @return void
     */
    public function setDebug($time = 0) {
        $this->_debugTime =  $time * 1000;
        $this->_debugAnimation = (is_integer($time) &#038;&#038; $time > 0) ? true : false;
        $this->_debug = true;
    }
    /**
     * 迷路配列作成
     *
     * @return array
     */
    private function _split($str)
    {
        $result = array();
        for ($i = 0 ; $i < strlen($str); $i++){
            $result[] = substr($str, $i, 1);
        }
        return $result;
    }
    /**
     * ゲーム画面描画
     *
     * @reutnr void
     */
    private function _showCompositScreen(array $maze, $debug = false)
    {
        $characters = $this->_monsters;
        array_push($characters, $this->_pacman);
        foreach ($characters as $character) {
            list($char, $x, $y, $dx, $dy) = $character->get();
            $maze[$y][$x] = $char;
        }
        echo "\n";
        foreach ($maze as $y) {
            echo implode('', $y) . "\n";
        }
        $point = ($this->_score === $this->_clearScore) ? ($this->_timeOut - $this->_time) + $this->_score : $this->_score;
        echo "Score:{$this->_score}/{$this->_clearScore} Point:{$point} Game:{$this->_time}/{$this->_timeOut} Stacked Game:" . count(Pacman_Quiz::$games) . " \n";
        echo "High Score: ". Pacman_Quiz::$highscore . ' total: '. Pacman_Quiz::$gameCount . "\n";
        echo "Play:" . $this->_pacman->getJoystick() . "\n";
    }
}
/**
 * パックマンクイズ
 *
 * @author akihito
 */
class Pacman_Quiz
{
    /**
     * パックマンの行動
     */
    public static $pacmanThought = array();
    /**
     * ゲーム
     */
    public static $games = array();
    /**
     * ハイスコア
     *
     * @var int
     */
    public static $highscore = 0;
    /**
     * クリア最小時間
     *
     * @var int
     */
    public static $minClearTime = 999;
    /**
     * ゲーム回数
     *
     * @var int
     */
    public static $gameCount = 0;
    /**
     * TimeOutの時にゲームをpopするか
     *
     * @var bool
     */
    private $_popOnTimeOut = false;
    /**
     * TimeOutの時にゲームをpopするかを設定
     *
     * @param bool $setPopOnTimeout
     */
    public function setPopOnTimeout($setPopOnTimeout)
    {
        $this->_setPopOnTimeout = $setPopOnTimeout;
    }
    /**
     * クイズ実行
     *
     * @return void
     */
    public function run($injector = '_injectQuestionThree', $debug = null)
    {
        $game = new Pacman_Game();
        if (isset($debug)) {
            $game->setDebug($debug);
        }
        $game->$injector();
        $game->init();
        $firstGame = clone $game;
        array_push(Pacman_Quiz::$games, $firstGame);
        do {
            if (!$game) {
                echo "All Game is Over.\n";
                break;
            }
            try {
                $result = $game->runGame();
                $game = array_pop(Pacman_Quiz::$games);
            } catch (Exception $e) {
                $game = array_pop(Pacman_Quiz::$games);
                $result = false;
            }
            $this->_showCounter();
            // Time Out
            if ($result === true &#038;&#038; !$this->_popOnTimeOut) {
                self::$pacmanThought = array();
                self::$games = array(Pacman_Quiz::$games[0]);
                $game = array_pop(Pacman_Quiz::$games);
            }
        } while(true);
    }
    /**
     * クイズ実行 (問題1用)
     *
     * @return void
     */
    public function run1($injector = '_injectQuestionOne', $debug = null)
    {
        $game = new Pacman_Game();
        if (isset($debug)) {
            $game->setDebug($debug);
        }
        $game->$injector();
        $game->init();
        $firstGame = clone $game;
        array_push(self::$games, $firstGame);
        do {
            try {
                $result = $game->runGame();
            } catch (Exception $e) {
            }
            $game->setHighScore();
            self::$games = array();
            self::$pacmanThought = array();
            $game = clone $firstGame;
        } while(true);
    }
    /**
     * カウンタ表示
     *
     * @return void
     */
    private function _showCounter()
    {
        static $i = 0;
        if (++$i % 1000 === 0) {
            echo ".$i";
        }
    }
}
// クイズ実行
$quiz = new Pacman_Quiz();
//$quiz->setPopOnTimeout(true); // true:TimeOutしてもスタックからゲームを取り出すモード
//$quiz->run1('_injectQuestionOne');
//$quiz->run('_injectQuestionTwo');
// 問題3
//$quiz->run('_injectQuestionThree', true); //逐次画面描画
$quiz->run('_injectQuestionThree', 100);    //アニメーション
//$quiz->run('_injectQuestionThree');       //ハイスコアチャレンジ
  1. この動画はAIによる移動です。再現プレイではありません。 []
  2. 結局その見通しは大甘でした []
  3. AKABE? []
  4. モンスタークラスにそれぞれの性格のモンスターがメソッドとして実装されていて迷路とPacmanの座標を受け取ったメソッドが進行方向を配列で返します。 []
  5. 95%以上得点が圧縮調整されてました。参加者の得点が高かったのでしょう []
  6. それぐらい知っとけという感じですが []
  7. 正に深さ優先探索! []
  8. ゲームオブジェクトはプロパティとしてモンスターやパックマンのオブジェクトなどゲーム要素全てもっています。 []
  9. メモリと時間が許せば []
  10. その方がスコアが良く、ランダムで繰り返しても同じゲームが再現することがほとんどありませんででした []
  11. ゲームオーバー時に積まれたゲームスタックを再評価し、10,000回に一回しか出ないような良いスコアの途中のゲーム状態から再開してみる..など色々やってみましたがあまりスコアアップに繋がりませんでした。オライリー本にもありますが"大器晩成型"のスコアがとであがってくるタイプのを消してしまうからではないかと思いました。 []
  12. これも膨大なメモリを要します。他にもいろいろな探索がオライリー本に紹介されてますがどれが一番向いてたのでしょうか []
  13. 残りドットが少なくなったら取りにいくロジックを追加したらかなり性能があがるかもしれません []
  14. アセンブラは16bitのスーパーファミコン(65816)、メガドライブ (680000+Z80)までやりました []
  15. 懐かしい響き! []
  16. 自機が”@”でした!当時いろんなゲームの自機が@。PC-6001用ASCIIのAXシリーズとか... []
  17. 動作確認にも大変世話になりました []
  18. AI検索のみの移動です。人の手による修正はありません []

リソースキャッシュ

| Comments

BEAR 0.8.x

現在のBEARは0.8.Xで、コアな機能は大分実装されてきてました。ここで機能追加を一旦fix、BEAR0.9は確認、テスト、パフォーマンスの向上など安定性の向上のためのバージョンにしてBEAR1.0に繋げようかと考えてます。実装前にその後の機能追加や方向性など単なるアイデアでまとまってないのも含めてかいてみようと思います。

リソースキャッシュ

Webフレームワークのキャッシュで最も一般的なのはビューキャッシュでしょうか。ビュー部分をページまるごと、あるいは表示の一部分をキャッシュし、その取得ロジックやDBアクセスのコストをセーブします。Smartyでも簡単に使えます。モデルをキャッシュしようとするとコントローラでモデル(オブジェクト)を直接アクセスするフレームワークでは、コントローラでキャッシュを利用するか、モデル側(ビヘイビアなどで)でキャッシュ対応するのが一般的だとおもいます。

BEARではページはリソースを直接扱わず、ページにインジェクトされたリソースブラウザサービスがリソースアクセスを行います。キャッシュ機構はページが使用するリクエストサービスが実装しています。(WebアクセスでWebブラウザがキャッシュ機構をもっているようなものです)

NoSQLキャッシュ

ROAの「ステートレス」と「統一インターフェイス」で、リソースへリクエストをメソッド、URI、バリュー(引数)それにオプションが決まれば事前準備なしに行う事ができます。そのリクエストはURIとバリューの値をシリアライズすれば1つのキーにすることが可能です。そのシリアライズされたリクエスト”キー”でリソース状態をバリューにキャッシュとしてNoSQLを使えばどうかと考えてます。キャッシュというより参照用RDBの代わりです。

キャッシュ更新を時間切れでなくメソッドで

キャッシュ破棄のタイミングは時間指定でなくメソッドを用いるのはどうかと考えてます。つまり、特定バリューのリソースアクセスにバージョンを持っておき、”サイドエフェクトがある操作"(update, delete)を行うとバージョン番号があがるというものです。

IDしか引き数を持たないリソースがあったとして、バージョン番号1,ID=3というキー"1:ID=3"でread()を何時間してもキャッシュに変化がなくオリジナルデータソース(RDB)にアクセスはありません。ですがID=3でのupdateやdeleteが発生するとリソースバージョンが1から2になりキャッシュキーは(2:ID=3)になります。キーが代わりキャッシュヒットしないので新しいキャッシュデータがストアされます。(古いキャッシュを明示的に破棄しないでGCにまかせます)

閉じたリソースと開いたリソース

以上の事はリソースが他のリソースに依存していないことを前提としています。(join先のテーブルが別リソースに使われてて更新されていたら機能しない)。それを解決するためにリソースにそのリソースの依存性がないというアノテーションを用意したり(@cache closedとか?)リソースキャッシュの依存性を示すようなアノテーション(@cache dependency profile, followerとか?)を用意すればいいのかなとか考えてます(まだ自信がありません)

ビューキャッシュ

リソース状態だけでなく、リソーステンプレートを(しかもUA別に)ストアしてやればビューキャッシュになります。キャッシュはレイヤーを持つのでリソース状態キャッシュはリソースクライアントで利用する事ができます。それにリソーステンプレートが適用されたキャッシュはビューキャッシュとなります。※その場合のキャッシュキーはURI + バリュー + バージョン + UA + テンプレート

こういう風にうまくRDBのデータをマスターとしてNoSQLのキャッシュにうまく乗せ、RDBの使いやすさとNoSQLのスケールアウト性がうまく合成できれば理想的なんじゃないかと。RDBのリクエストを最小化することができれば使用するDBライブラリ(MDB2, PDO, Zend_Db)等の性能差をあまり考えなくてよくなるメリットもあります。揮発性のあるキャッシュというより、参照用DB(スレーブDB)の代替になれば理想的です。容量や実装の問題もあるかもしれませんが高い可能性を感じています。

Hello Worldコールグラフ

| Comments

Hello Worldベンチマーク

Performance of YiiというページでPHP主要フレームワークの”hello worldべンチマーク”を比較しています。phpmarkというGoogle Code Projectでホストされてる各フレームワークでHello Worldを出力するアプリケーションでベンチをとっているようです。Hello Worldベンチは最小のオーバーヘッド測定のためとされますが、そのコールグラフがどうなるかに興味を持ちました。

※なぜHello Wolrdなのか?どういう意味があるのか?などについてはPerformance of YiiPaul M. Jones » Blog Archive » New Year’s Benchmarksなどを参照してください。

コールグラフとは?

コールグラフ (マルチグラフとも呼ばれる) とは、コンピュータプログラムのサブルーチン同士の呼び出し関係を表現した有向グラフである。

コールグラフ – Wikipedia

コールグラフ描画にはfacebookの開発したxhprofが描画するgraphvizを用いました。web上で描画されたものです。以下、コールするファンクションの少ない順に並べています。

Yii1.0.3Lite

ファンクションコール数:119

PHP APC extension が有効である場合、 yii.phpを yiilite.php で置き換えることがで、さらにパフォーマンスを改善できます。
yiilite.phpはすべてのYiiリリースに含まれています。その内容はYiiの基本クラスをひとつにまとめたものです。コメントとトレース命令はすべて取り除かれています。したがって、yiilite.php を使うことで、インクルードされるファイルの数と、トレース命令の実行を減らすことになります。

というものだそうで、アプローチの仕方はちょっと違うようですがKohanaにもKohana-liteというものがあります。1

そのたっぷりつまったyiilite.phpの読み込みに最も時間がかかっています。

Yii 1.0.3 Lite

Yii 1.0.3 Lite

Yii 1.0.3

ファンクションコール数:161

YiiはHello Worldベンチの性能が良い原因を「他の遅いフレームワークは必要が無いかもしれないモジュールを初期化しているが、Yiiはレイジーロードを積極的に採用しているため」と説明してますがこのグラフを見る限り最低限のものしか呼び込まれていないすっきりした印象を受けます。

Yii 1.0.3

Yii 1.0.3

CodeIgniter 1.7.2

ファンクションコール数:377

Yiiの次にファンクションコール数が少ないのがCodeIgniterです。他のフレームワークと違うのはフレームワークの関数のものがあることでしょうか。最もコールされてるのがload_classの17回、get_config, log_messageと続きます。どれも関数です。

CodeIgniter 1.7.2

CodeIgniter 1.7.2

Zend Framework 1.7.3

ファンクションコール数:725

Yii, CIに続くのがZend Frameworkです。今回のフレームワークの中で唯一、クラス/メソッドの命名規則がPEARと同じで僕は一番分かりやすく感じました。最もコールされたのはZend_Loader_PluginLoader::_formatNameで17回、時間がかかったのはZend_Controller_Action_Helper_ViewRenderer::getInflectorで全体の5.1%です。

Zend Framework 1.7.3

Zend Framework 1.7.3

symfony 1.2.2

ファンクションコール数:1878

もっともカオスなコールグラフになったのがこのsymfonyで7489 x 5683ピクセルの巨大グラフになりました。sfConfig::get()が147回呼ばれ最も時間のかかったメソッドになっています。

symfony 1.2.2

symfony 1.2.2

CakePHP 1.2.1

ファンクションコール数:12,166

コール数が桁違いに多いので何かの間違いではないかと思いましたがMASA-Pさんの【CakePHP】xhprofでCakePHPのパフォーマンスを丸裸にする | ECWorks Blogという記事でも13,000を超えるコール数になっているのでこれで間違いではないと思います。特にFolder::系のコールが多いようです。
グラフのサイズはややsymfonyより小さいですがほぼ同等です。

CakePHP上位コールファンクション

CakePHP 1.2.1

Disclaimer

phpmarkのサイトにもあるのですが、このエントリーでも同じです。

  • 特定のフレームワークを応援したり攻撃する意図はありません。
  • ミニマムオーバーヘッドが低いというのはフレームワーク評価基準のごく一部です。フレームワーク選定で重視しすぎるべきではないでしょう。

関連リンク

  1. アクティブじゃないみたいですが []
  2. 上記の他にPrado, Solar, Agavi, Drupalのベンチとコールグラフがあります []
  3. 下のリンクの記事Entertaining But ~と合わせてどうぞ []
  4. ということでこのエントリーも… []