- 投稿日:2021-01-11T23:15:57+09:00
マンカラ(ボードゲーム)の思考エンジンのGUI化(デスクトップAPP)
はじめに
Nintendo Switch向けソフト「世界のアソビ大全51」に格納されている「マンカラ」というボードゲームを遊んでみました。プレイする中で、どうすると勝てるのかが全く分からなかったので、盤面の状態をもとにどの手を選ぶのが最善なのかを推計するGUIツールを作成してみました。
「マンカラ」とは
ルールについては、以下、youtubeでの任天堂の動画やWikipediaを参照ください。
「マンカラ」には派生ルールがいろいろあるようですが、上記の「世界のアソビ大全51」で採用されているルールは「カラハ(Kalah)」ルールに基づいています。端的には、2人で6個×2列の穴にそれぞれ4個ずつ入っている48個の石を交互に選んで動かしていき、最終的に獲得できた石が多い方が勝ち、というものです。
ちなみに一緒にプレイした相手の家庭内ルールはカラハルールとは異なり、「先に自分の陣地の手を無くした方が勝ち」というルールになっているとか。
このゲームは、いわゆる「二人零和有限確定完全情報ゲーム」「アブストラクトゲーム」に分類されるゲームです。将棋、囲碁、リバーシや〇×ゲーム(Tic-Tac-Toe)も同様の分類であり、要するに「プレーヤーが2人で、全ての情報がお互いに明かされており、偶然の要素が入らないゲーム」ということになります。
情報が完全に公開されていて偶然の要素も無いことから、理論上は完全な先読みが可能です。つまり、このタイプのゲームは双方が最善手を指すこと前提とすると、先手必勝か後手必勝か引き分けかが決まっています。例えば、〇×ゲームは双方ベストを尽くせば必ず引き分けになります。
しかし、実際には選択肢が多くなると完全な先読みを人間が行う事は難しく、そのためゲームとして成立しているといえます。
先行する研究や記事等
Irvingらの研究によると、上記の6個×2列の穴にそれぞれ4個ずつ石が入っているケースでは、先手後手が双方最善手を指した場合「29vs19」で先手の勝ちとなるようです。(Geoffrey Irving, Jeroen Donkers and Jos Uiterwijk(2000).SOLVING KALAH.ICGA Journal)
ただ、上記のとおり実装するとなると、実行端末上にそれなりのストレージ容量が必要になります。
これは少々扱いにくいので、ある程度で探索を打ち切り、評価値をもとに最善手を返す仕組みを検討していたところ、@dsanno様が2020年7月にQiita上で記事を公開していていたので、こちらのロジックをベースとして搭載することとしました。リンク:rustでマンカラ(ボードゲーム)の思考エンジンを作る
モジュール&ソース
モジュールおよびソースは、Github上で公開しています。
リポジトリ:https://github.com/kyosuke0924/Mancalaモジュールは上記リポジトリの「Release」ボードより「Mancala.zip」を取得してください。
リリース:https://github.com/kyosuke0924/Mancala/releases稼働環境
以下の環境で動作します。
項目 要求スペック OS Windows 10 ver.1607以降(64bit版) 必要なソフトウェア .NET Framework v4.8 解像度 1280×720 以上 WindowsFormsを用いて開発しているため、LinuxやMacOSはサポートしていません。
「.NET Framework v4.8」については、OSWindows 10 May 2019 Update(バージョン 1903)以降を使用している場合は、プリインストールされているため、特段インストール作業は不要です。上記より古いバージョンの場合は、別途Microsoft社のダウンロードページよりダウンロードとインストールを実施してください。開発環境
開発環境は以下の通りです。
項目 スペック OS Windows 10 ver.20H2 (64bit版) CPU Intel(R) Core(TM) i7-3770 @ 3.40GHz(4コア8スレッド) RAM 16.0 GB Storage SSD 1TB 解像度 1920×1080 開発言語 C# エディタ VisualStudio 2019(Windowsフォームアプリケーション) もともと、@dsanno様はRustでロジックを書かれていました。
そのため、ロジック部分についてはRust部を流用し、画面から関数をInvokeすれば効率が良かったのですが、Rustの開発技術がなかったため、すべてC#で書き直しています。処理の速度についてはRustよりC#の方が遅いので、同じ読み手の深さでも、もともとのロジックより少々時間がかかるようになってしまいました。
使用手順
インストーラはありません。
ダウンロードした「Mancala.zip」を任意の場所に解凍し、「Mancala.exe」を実行してください。設定ファイル
「Mancala.exe.config」がアプリケーションの設定ファイルです。
設定項目は以下のとおりです。
項目 初期値 意味 Depth 12 候補手を探索する深さです。値が大きいほど先読みが深くなるため、正確な判定ができますが、処理に時間がかかります。 EndingFileSeedNum 10 後述する終盤データベースを作成する際のシードの数です。これも値が大きいほど、ゲーム終盤の判定が正確になりますが、作成に時間を要するようになり、かつ作成されるファイルの容量が大きくなります。 Mancala.exe.config<setting name="Depth" serializeAs="String"> <value>12</value> </setting> <setting name="EndingFileSeedNum" serializeAs="String"> <value>10</value> </setting>特段、設定は不要ですが、処理時間に余裕があるようであれば、「Depth」の値を大きくすることでより正確な判定が可能です。
逆に処理に時間がかかるようであれば、値を小さくすることで処理時間を短くすることができます。(推計の精度は下がります)変更する場合は、該当ノードのvalueタグ内の値を変更し、ファイルを上書き保存してください。
画面イメージ
機能について
盤面の各ボタンをクリックしていくと、最善と推計される手がハイライトされます。
画面には、あわせて各情報が表示されます。候補
次手の候補と、各候補を選んだ場合の形勢を示します。
先手であれば形勢の値が最も大きくなる手、後手であれば形勢の値が最も小さくなる手を最善手としてハイライトします。
項目 意味 手 各手を意味します。各プレイヤーから見て左側から(1)⇒(6)となります。 形勢 各手を選んだ場合の盤面の評価値です。値が大きいほど先手有利、小さいほど後手有利となります。 形勢
初手からの形勢の推移を表す折れ線グラフです。値が大きいほど先手有利、小さいほど後手有利となります。
履歴
初手からの着手履歴、スコア、盤面の状態と形勢を表示します。
項目 意味 手番 着手が先手か後手かを示します。 手 各手を意味します。各プレイヤーから見て左側から(1)⇒(6)となります。 先手(後手)スコア 先手(後手)が獲得した石の数を示します。ゲーム終了時にこの値が大きい方が勝利となります。 先手(後手)盤面 先手(後手)の盤面の状態を示します。各プレイヤーから見て左側から(1)⇒(6)となります。 形勢 各手を選んだ後の形勢を示します。 各ボタンの機能
各ボタンの機能は以下のとおりです。
項目 意味 リセット 盤面を初期状態に戻します。 一手戻す 一手戻します。 盤面を反転する 盤面を反転して後手から見た目線の盤面にします。再度クリックすると元に戻ります。 endingファイルを表示 終盤データベースを表示します。 endingファイルを作る 終盤データベースを作成します。 終了 アプリケーションを終了します。 最善手の推計の仕組み
アプリケーション設定ファイルのDepthに指定した手数分先読みを行い、自分は最も自分にとって状況がよくなる手を、相手は最も自分にとって都合の悪くなる手を指したと仮定した場合に、どの手を選ぶのが最良かに基づき判断しています。(ネガアルファ法)
先読みの末端では、盤面の状態が終局もしくは終盤データベース(各盤面から終局まで完全に読み切って求めた評価値のデータベース)に登録されている状態であれば確定している評価値を、そうでなければ石の配置から予測した推計値を評価値として返す仕組みです。
そのため、終盤に近づけば近づくほど、最善手の推計の精度は高くなります。
@dsanno 様のCUIツールとの違いについて
オリジナルのCUIツールとは、以下の違いがあります。
- 評価値の表示形式
オリジナルでは各手番から見た評価値をそのまま出力していますが、本ツールでは、先手から見た評価値を正、後手から見た評価値を負として示すようにしています。
- 全手の評価値の出力
オリジナルでは最善手のみ評価値を返す仕組みですが、本ツールでは、着手可能な全手の評価値を計算します。
- 探索のマルチスレッド化
全手の探索に伴い、各手の探索をマルチスレッド化しています。(そのためスレッド数が着手可能数以下のマシンでは、若干処理に時間がかかることが懸念されます)
- 終盤データベースの活用
オリジナルの公開モジュールでは終盤データベースについては実装されておりませんが、Github上のソースでは終盤データベースを活用したソースがコミットされていましたので、こちらをもとに実装しています。
- クラス設計
C#での処理を高速化するため、クラス設計を大幅に見直しリファクタリングしています。
また他にも処理速度を向上されるため、関数等に様々な手を入れています。(例えばStackに格納する前に着手可能かどうかを判定して不要なPush,Popを減らす、オブジェクトコピー量を減らすため、不必要なメンバーや要素を持たせない等)おわりに
元記事にもありますが、探索において各盤面と評価値をメモ化することで探索の時間を減らすことができるため、今後この部分は時間があれば実装していきたいと考えています。(メモリ消費量は多くなりますが)
あとは、ツールを使って実験した結果、
- 自分がピッタリゴールできるときは、その手を選択する。
- 多く石があるポケットが横取りされる場合、防ぐ手を選択する。
- 相手の石の横取りができる場合は、その手を選択する。
- 相手の陣地に渡る石の数を少なくなる手を選択する。(そのため、極力右のポケットから選択する)
の優先順位でムーブをしていくと、勝率が高い気がします。
- 投稿日:2021-01-11T17:56:13+09:00
Prism コードサンプル学習:05-ViewInjection
Prism コードサンプル学習:05-ViewInjection
はじめに
以下の記事の続きです。
https://qiita.com/mngreen/items/d4164e0107fd5b69b1c905-ViewInjection
本サンプルではRegionManagerクラスを用いて、対象regionにViewを追加します。
<Window x:Class="ViewInjection.Views.MainWindow" xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation" xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml" xmlns:prism="http://prismlibrary.com/" Title="Shell" Height="350" Width="525"> <DockPanel LastChildFill="True"> <Button DockPanel.Dock="Top" Click="Button_Click">Add View</Button> <ContentControl prism:RegionManager.RegionName="ContentRegion" /> </DockPanel> </Window>/// <summary> /// Interaction logic for MainWindow.xaml /// </summary> public partial class MainWindow : Window { IContainerExtension _container; IRegionManager _regionManager; public MainWindow(IContainerExtension container, IRegionManager regionManager) { InitializeComponent(); _container = container; _regionManager = regionManager; } private void Button_Click(object sender, RoutedEventArgs e) { var view = _container.Resolve<ViewA>(); IRegion region = _regionManager.Regions["ContentRegion"]; region.Add(view); } }
- [Add View]ボタンを押下することで、ContentRegionにViewが追加されます。
- regionManager.Regionsプロパティにインデクサでアクセスすることで対象のregionを取得できます。
- このように対象のregionを取得できるのは添付プロパティであるRegionManager.RegionNameプロパティに値がセットされたタイミングでRegionを生成するメソッドが呼び出されるため。
- 正確にはそこで生成されたDelayedRegionCreationBehaviorがやってくれる
- region.Addメソッドでviewが追加されると巡り巡ってInnerAddメソッドが呼び出される。
- viewはItemMetadataクラスとしてラップされてItemMetadataCollectionに追加される。viewNameを合わせて付与される。
- ItemMetadataCollectionが変更されると、ViewsCollectionがItemMetadataCollectionによって生成されているため、そちらのハンドラ(ViewsCollection.SourceCollectionChangedメソッド)で処理される。これにより、ただregion.Addしているだけのように見えるが、CollectionChangedイベントが発火されてUIが更新される。
おわりに
今回はRegionManager, Regionクラスのソースコードを中心に読みました。
DependencyPropertyを利用してアタッチされたタイミングでRegionを生成するといった工夫をすることで、利用者側が便利になる工夫が見られました。
次回、06-ViewActivationDeactivationについて見ていこうと思います。
- 投稿日:2021-01-11T12:05:28+09:00
C#を使った必要十分なクリップボードの監視
目的
業務上、特定の場所のテキストを一定の法則で置き換えて更新する作業が発生した。
本来ならpyautoguiなどを使って自動化できないか考えるところだったが、
派遣開始してからの日が浅く、納期も短いために時間のかかることはできない。そのため、次善の策としてC#でクリップボードを監視・置き換えするアプリを作成した。
方法
インターネットで検索をかけると、このようなクリップボードの監視方法があるらしい。
ただ、僕は今の会社に無限にいるわけでもないので、もう少しシンプルな方法で実装しておいて、他人がメンテナンスできるようにしておいたほうが良いと思った。なので今回はシンプルにSystem.Windows.Forms.Clipboardクラスを使ってフォームアプリケーションとして作ることにした。
なお、Clipboardクラス自体は.Net Framework1.1から対応しているようなので、
今使用可能なWindowsならバージョン依存はなく動くはずである。UI
下の画像のようなUIを準備した。
数字の書かれているラベルはcountLabel、監視中と書かれているボタンは見た目をボタンにしたcheckEnablerという名前のチェックボックス、
変換後のテキストボックスはlastText、変換前のテキストボックスはnextTextと名付けた。
また、timer1という名前のタイマも適当な間隔を指定してある。コード
特に難しいことは考えず、一定周期でクリップボードにテキストデータが入っているかを確認し、
テキストデータが最後に取得したテキストデータと異なっているのであれば一定の条件で処理を行っている。数百回レベルの作業が予想されていたため、確認処理を行うたびにラベルのテキストと色を反転させて、
処理が行われているかどうかをわかりやすくした。
業務アプリだったら変換前・後のテキストをどこかに保存しておくのも有効だと思う。using System; using System.Drawing; using System.Windows.Forms; namespace ClipboardCheckApp { public partial class Form1 : Form { private int checkCount; public int clipboardCounter { get { return checkCount; } private set { checkCount = value; // 視認性の向上。クリップボードの操作を行うたびに背景とテキストの色が反転する。 if ((checkCount & 1) == 0) { countLabel.BackColor = SystemColors.ControlText; countLabel.ForeColor = SystemColors.Window; } else { countLabel.ForeColor = SystemColors.ControlText; countLabel.BackColor = SystemColors.Window; } countLabel.Text = checkCount.ToString(); } } public Form1() { InitializeComponent(); if (Clipboard.ContainsText()) { lastClipboard = Clipboard.GetText(); } } private void checkEnabler_CheckedChanged(object sender, EventArgs e) { if (checkEnabler.Checked) { checkEnabler.Text = "監視中"; } else { checkEnabler.Text = "監視停止中"; } timer1.Enabled = checkEnabler.Checked; } private string lastClipboard { get { return lastText.Text; } set { lastText.Text = value; } } private string nextClipBoard; private void timer1_Tick(object sender, EventArgs e) { // 適当な感覚でクリップボードを監視する。 if (Clipboard.ContainsText()) { nextClipBoard = Clipboard.GetText(); if (lastClipboard != nextClipBoard) { // クリップボードに対して何らかの処理を行う場所。 nextText.Text = nextClipBoard; lastClipboard = nextClipBoard.Replace("ham", "egg"); Clipboard.SetText(lastClipboard); clipboardCounter++; } } } } }とりあえず自分で動かしてみた限りでは問題なく動いた。