BOFと最中限のアルゴリズム

昨日、a2cさんが主催しているBOFに参加させていただいた。それぞれ思い通りに開発しつつ、わからないところはみんなで解決的なのり。是非また参加させていただきたい。

BOFの中で、西尾さんが、最中限という3人でやるゲームを教えてくれた。ルールは本家サイトを参照していただくとして、これをコンピュータ大戦するためのアルゴリズムを考えたい。

ゲーム理論で考えた場合、ミニマックス法でやる場合はすべての条件を網羅しないといけない。この場合の計算コストは以下のようになる。

  • カードは全部で52枚ある
  • 自分は17枚のカードを持っている

単純に計算すると、最初のターンで(17×3)×(16×3)×(15×3)× ・・・ (1×3)通りの条件を網羅しないといけない。500垓(該=10の20乗)回の計算。うーん無理だろ。

実際のゲームもこんなに計算しているわけじゃない。っていうかできない。再帰的なスレッドを入れ子して作るんだけど、これはアーランは得意そう。でも現実的には全パターンを網羅する必要なんてまったくない。ということで、アルファ・ベータ法等で、ゲーム木の深さを制限したい。それには条件が色々と必要になる。昨日初めて遊んだだけなので不確かだけど、以下のような条件では探索は不必要となる(と思うｗ)。

  • 1回目のラウンドは、0か一番少ない得点を狙いたい
  • 2回目のラウンド以降、自分が一番高得点の場合、相手に自分以上の得点を取らせたい
  • 2回目のラウンド以降、自分が最中限の場合、この状態をキープしたい
  • 2回目のラウンド以降、自分が一番低得点の場合、最中限の人を超えて最大得点以下の点を取りたい
  • ラウンド内の各ターンでは、ラウンドで最大の成果を出せるように得点を取りたい
  • 1番強いカードと1番弱いカードは絶対に取りたい時、取りたくない時に有効
  • 点数を取りたくない場合、ターンで最大を目指すか、最少を目指す
  • 点数を取りたい場合、最中を目指す

うーん。どれぐらい減るのかは書いてみないと分からないな。。。まだまだです。各自が作ったアルゴリズムを実装したら対戦して、誰のアルゴリズムが強いかを競い合ったりしたいｗ

コメント

コメントを投稿

このブログの人気の投稿

Python から Win32 API 経由で印刷する

Win32 API から印刷をするためには、プリンタデバイスコンテキスト (Printer DC) を利用します。具体的には以下のような順序で印刷します。 プリンタドライバからハンドルを取得する プリンタドライバのステータス API から印刷可能か同かを取得する プリンタデバイスコンテキストを作成する ドキュメントを開始する 必要であればフォント等を設定し、印字、改ページ処理などをする ドキュメントを終了する (この時点でプリンタスプールサービスに登録されるようです) プリンタデバイスコンテキストを開放する プリンタドライバのステータス API を監視し、印刷が正常に終了したかを取得する プリンタドライバのハンドルを解放する 太字の手順 (3 - 7) は Win32 API で共通ですが、それ以外の手順 (1, 2, 8, 9) はプリンタドライバに依存しているため、Python から制御したい場合はライブラリを作成する必要があります。これについては、ドライバマニュアルとにらめっこしながら ctypes.windll でがんばります・・・。プリンタ接続、用紙切れ、ミスフィード等のプリントエラーを制御する必要がなければ、書く必要はありません (排他制御が必要なプリンタを除く)。プリンタドライバ毎に変わる部分は置いといて、太字の Win32 API の部分の覚書です。 プリンタデバイスコンテキストを作成する import win32ui import win32con PRINTER_NAME = '[コンパネ -> プリンタとFAX -> に登録しているプリンター名]' PIXELS_PER_INCH = 1440 # 1 インチ毎のピクセル数 INCH_PER_POINT = 72 # 1 インチ毎のポイント数 SCALE_FACTOR = int(PIXELS_PER_INCH / INCH_PER_POINT) #　わざわざ計算せず 20 と指定する場合が多い dc = win32ui.CreateDC() dc.CreatePrinterDC(PRINTER_NAME) # 指定したプリンタ名のプリンタデバイスコンテキストを作成する self.dc.SetMapMode(win32con.MM
続きを読む

財務諸表 (Financial Statements)

※ 業務 & 英語の勉強 財務諸表 (Financial Statements) の種類 諸表名 英語表記 概要 損益計算書 Profit and Loss Statement [P/L] ※ Income Statement など様々 収益と費用の状態を表す 貸借対照表 Balance sheet [B/S] 資産、負債、純資産を表す キャッシュ・フロー計算書 Cash flow Statement [C/S] 資金の増減を表す 株主資本等変動計算書 Statements of Shareholders' Equity [S/S] 純資産の変動状況を表す 損益計算書 損益計算書とは 収益から費用を差し引いた利益を計算するためのもの 利益 (profit) = 収益 (revenue) - 費用 (expense) 損益計算書の構成 記載内容 英語表記 概要 売上高 Sales 販売した財やサービスの金額 売上原価 Cost of Sales 財やサービスを生み出すための経費 期首繰越高＋当期仕入高－期末棚卸高 - 売上総利益 Gross Profit = 売上高 - 売上原価 ※ 売上高総利益率 [ 粗利益率] (Shareholder Equity Ratio) = 売上総利益 / 売上高 販売費及び一般管理費 Selling and General Administrative expenses [SGA] 売上原価以外の企業を運営するための経費 販売費: 販売手数料、広告宣伝費など 一般管理費: 人件費、福利厚生費、交際費、賃借料、減価償却費、雑費など - 営業利益 Operating Profit = 売上総利益 - 販売費及び一般管理費 営業外収益 Non-operating income 本業以外で経常的に発生する収益 受取利息、有価証券売却益、配当金、不動産賃貸収入など 営業外費用 Non-operating expense 本業以外で経常的に発生する経費 支払利息、有価証券売却損など - 経常利益 Ordinary Profit = 営業利益 + 営業外収益
続きを読む

Django と Python 3 - #python_adv

Django-ja の方からきました。こんにちわ。さて、昨日の Ian 先生のブログ にも書いてある通り、ついに Django にも本格的に Python 3 の足音が近づいてきました。ただし現在 alpha 版が公開されている 1.5 では "実験的" なサポートで、1.6 以降で正式にサポートする予定となっています。あくまでも "実験的" であり、プロダクションでの利用は "非推奨" となっています。Django コミュニティでは、この 1.5 でサポートをテストしてもらい、そのフィードバックを呼びかけています。なのでプロダクションでの利用は 1.6 まで待ちでしょうね。また Python 3 サポートと同時に、Django 1.4 では Python 2.4 がサポートから外れ、1.5 では Python 2.5 がサポートから外れます。これで 1.7 以降から django.utils 配下が軽くなっていくんでしょうかね (現在は 3 サポートのためにさらに増えてる)。 バージョン 下位互換 Python サポート 2.5 2.6 2.7 3.2 3.3 Django 1.4 > 1.2 ○ ○ ○ - - Django 1.5 > 1.3 - >= 2.6.5 ○ >= 2.7.3 △ 実験的 △ 実験的 Django 1.6 > 1.4 - >= 2.6.5 ○ >= 2.7.3 ○ ○ Python 2.5 系を利用している場合は、1.6 のリリースまで (2013 後半ぐらい?) に Python 2.6.5 以上 (2.7.3 以上を強く推奨) への移行が必要です。1.5 は今月 (2012/12) 中にリリース予定とのことなので、今のうちに Python 3 へ移行方法を抑えときたいなと。以下 Django ドキュメントの翻訳作業がてら " Porting to Python 3 " を元にご紹介。さすが
続きを読む