この記事は、インテル® デベロッパー・ゾーンに公開されている「Playing an Infinite Game of Monopoly with Python」(https://software.intel.com/en-us/blogs/2016/04/07/playing-an-infinite-game-of-monopoly-with-python) の日本語参考訳です。
インテル® Distribution for Python* 2017 のリリースに伴い、私は新米 TCE として、インテル® VTune™ Amplifier XE の Python* コードのプロファイル機能について初期サポート資料の作成を任されました。ヘルス & ライフ・サイエンス・グループに所属していたため、Python* を使い始めて数年になりますが、ここしばらくは Python* プログラミングにかかわる機会がありませんでした。
新しいインテル® VTune™ Amplifier XE の Python* 機能を試すには、コードが必要です。私の手元には、Project Euler の問題を解くための Python* コードが、この記事の執筆時点で 70 問分ありますが、そのほとんどは短時間で実行できるものばかりです。プロファイラーが処理できるように、実行時間が長く、意味のある解析結果が得られるコードがないか考えてみました。少なくとも 1 つのソリューションの実行時間が長かったことを思い出しました。しかし、どのコードだったか思い出せなかったため、(私の大好きな) 素数を扱うコードを選択し、実際に実行してみたところ、2 秒未満で解が算出されました。実行時間を長くするため、検索範囲を拡大しました。
解析結果 (下の図) は想定通りでしたが、インテル® VTune™ Amplifier XE の新しい機能を試すことができてよかったです。
インテル® Distribution for Python* 2017 に含まれるライブラリーや拡張パッケージ (NumPy*、SciPy* など) をもっと活用できないかと考えたとき、以前に遊びで記述した BLAS ルーチンを使用する Fortran コードを思い出しました。このコードは、従来のモノポリーゲームのボードで最も占有率の高いマスを見つけることを目的としています。繰り返し行列-ベクトル積を計算するマルコフ連鎖を含むアルゴリズムを使用します。行列には、サイコロを振るか、チャンスカードまたは共同基金カードを引くことで、1 つのマスから別のマスに移動する確率を格納します。ベクトルには、スタート時の初期状態から指定されたマスに到達する現在の確率を格納します。1 つの乗算のベクトル値と次の乗算のベクトル値が変わらなくなったら、計算は完了です。
この問題は、数年前にネットサーフィンしているときに Andrew Pinzler 氏の “My Science Fair Project” サイトで見つけました。Pinzler 氏は、移行行列の設定と計算方法、実行結果、およびそれらの知識をモノポリーに応用する方法を説明していました。私は、Fortran コードを記述後、Pinzler 氏に謝意を伝え、倍精度演算でも同様の結果が得られたことを報告しました。
この Fortran コードを Python* に適合できないかと思い、パーソナルアーカイブを探してみました。残念ながら、コードは見つかりませんでした。そこで、Pinzler 氏の “My Science Fair Project” サイトを Web で検索してみました。幸い、Pinzler 氏のサイト (英語) はまだあり、設定の詳細を再度入手することができました。(その後 Pinzler 氏は、より大きな興味深いプロジェクトに取り組んでいました。サイトは長い間更新されていないようです。モノポリーの販売元が Parker Brothers のままであり、ページの下部にあるアイコンには Netscape Navigator* 4.0 推奨と記載されています。)
Python* の参考資料を片手に、キーボードを叩いて、プログラムを再度作成しました。興味のある方は、記事の最後にコードのダウンロード・リンクがあります。(zip ファイル形式ですが、中身は Linux* 上で Python* 3.5 を使用して作成した Python* コードだけです。) Pinzler 氏の説明から 1 点だけ変更しています。“刑務所見学/刑務所” のマスは、ボード上で同じ位置にありますが、実際には異なります。Pinzler 氏のサイトでは、これらは同じマスとして扱われていますが、私は個別のマスとして扱うことにしました。どちらの場合もサイコロを振って移動する先は同じですが、刑務所に入るのと、ステート通りに行く途中に刑務所のマスを通過するのでは異なるからです。このため、“刑務所に入る” という “実在しない” マスを移行行列の “ボードウォーク” と “Go” の間に設けました。サイコロの目が出る確率を設定した後、実在しないマスをスキップするようにし、ほかのマスへの移動が “刑務所見学” と同じになるように行列を修正する必要がありました。また、刑務所に直接移動するすべての移動 (GO を通過しない、$200 を受け取らない) は、実在しないマスに送るように変更しました。
インテル® Distribution for Python* 2017 の利点についてより納得がいく検証ができるように、私は当初、行列表現にリストのリストを使用して行列-ベクトル積をハンドコードしていました。これをインテル® VTune™ Amplifier XE で検証し、関数で時間がかかっている個所を特定して、それらの計算に NumPy* 行列を使用した場合と比較することが目的でした。残念ながら、すぐにこれではだめだと気付きました。
従来のモノポリーボードには 40 マスしかありません。私が追加した “刑務所に入る” マスを含めても 41×41 行列にしかならないのです。この行列-ベクトル乗算を含むコードを実行すると、188 反復で (188 回サイコロを振ると) 解が算出され、一瞬で実行完了になります。
失敗です。
そこで、使用するボードを見直すことにしました。再帰処理を含むものに変更すべきかもしれません。(退屈な N-Queens ではない別のものが良いでしょう。) 特殊な大量の演算を行い、実行時間が長いものであれば、インテル® VTune™ Amplifier XE でランタイムを解析できるかもしれません。
当初の目的は達成できませんでしたが、このプロジェクトは (初めて取り組んだときと同様に) 非常に面白いものでした。行列のサイズと実行時間を拡張する方法がないか Web で調べた結果、Deviant Art サイトで jonizaak 氏による Ultimate Monopoly を見つけました。これであればより大きな行列を作成し、解の算出までにかかる反復回数も増やすことができるでしょう。しかし、残念ながら、これは良くできていますが、市販されているゲームではありません。雨の日に友人とプレイしたり、おやつを片手に楽しむのには良いでしょう。
| monopoly.zip (1.67KB) https://software.intel.com/sites/default/files/managed/59/6a/monopoly.zip |
コンパイラーの最適化に関する詳細は、最適化に関する注意事項を参照してください。
