BEAR Blog

Because everything is a resource.

GDD2011 DevQuiz

| Comments

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

Web Game

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

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

このエクステンションは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点。これまでの３つのクイズの合計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. 中学生の時にはじめてプログラミングしたワクワク感が少し甦りました。 [↩]