不完全な情報を持つカードゲームのMiniMAX検索を使用してください
https://stackoverflow.com//questions/12666119
-
11-12-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
コンピュータプログラムをコンピュータプログラムに再生するために、MiniMAX検索（アルファベータ剪定）、またはむしろNegaMax検索を使用したい。
カードゲームは実際に4人のプレーヤーで構成されています。そのため、MiniMAXなどを使用できるようにするために、「その他」に対して「ME」にゲームを簡素化します。各「移動」の後、ゲーム自体から現在の状態の評価を客観的に読むことができます。 4人のプレーヤーがすべてカードを置いたら、最も高いがそれらすべてを勝ち、カードの価値観数がカウントされます。
他の3人のプレーヤー間のカードの配信方法が正確にどのように分布があるかわからないので、私はあなたがあなたのものではないカードを使ってすべての可能な分布（ "世界"）をシミュレートする必要があると思いました。あなたは12枚のカードを持っています、他の3人のプレーヤーは合計36のカードを持っています。
だから私のアプローチはこのアルゴリズムです。ここで、playerは、プログラムが移動する必要があるかもしれない3つのコンピュータプレーヤーを象徴する1から3の間の数字です。 -playerは対戦相手、すなわち他のすべてのプレーヤーを一緒に立ちます。
private Card computerPickCard(GameState state, ArrayList<Card> cards) {
int bestScore = Integer.MIN_VALUE;
Card bestMove = null;
int nCards = cards.size();
for (int i = 0; i < nCards; i++) {
if (state.moveIsLegal(cards.get(i))) { // if you are allowed to place this card
int score;
GameState futureState = state.testMove(cards.get(i)); // a move is the placing of a card (which returns a new game state)
score = negamaxSearch(-state.getPlayersTurn(), futureState, 1, Integer.MIN_VALUE, Integer.MAX_VALUE);
if (score > bestScore) {
bestScore = score;
bestMove = cards.get(i);
}
}
}
// now bestMove is the card to place
}
private int negamaxSearch(int player, GameState state, int depthLeft, int alpha, int beta) {
ArrayList<Card> cards;
if (player >= 1 && player <= 3) {
cards = state.getCards(player);
}
else {
if (player == -1) {
cards = state.getCards(0);
cards.addAll(state.getCards(2));
cards.addAll(state.getCards(3));
}
else if (player == -2) {
cards = state.getCards(0);
cards.addAll(state.getCards(1));
cards.addAll(state.getCards(3));
}
else {
cards = state.getCards(0);
cards.addAll(state.getCards(1));
cards.addAll(state.getCards(2));
}
}
if (depthLeft <= 0 || state.isEnd()) { // end of recursion as the game is finished or max depth is reached
if (player >= 1 && player <= 3) {
return state.getCurrentPoints(player); // player's points as a positive value (for self)
}
else {
return -state.getCurrentPoints(-player); // player's points as a negative value (for others)
}
}
else {
int score;
int nCards = cards.size();
if (player > 0) { // make one move (it's player's turn)
for (int i = 0; i < nCards; i++) {
GameState futureState = state.testMove(cards.get(i));
if (futureState != null) { // wenn Zug gültig ist
score = negamaxSuche(-player, futureState, depthLeft-1, -beta, -alpha);
if (score >= beta) {
return score;
}
if (score > alpha) {
alpha = score; // alpha acts like max
}
}
}
return alpha;
}
else { // make three moves (it's the others' turn)
for (int i = 0; i < nCards; i++) {
GameState futureState = state.testMove(cards.get(i));
if (futureState != null) { // if move is valid
for (int k = 0; k < nCards; k++) {
if (k != i) {
GameState futureStateLevel2 = futureState.testMove(cards.get(k));
if (futureStateLevel2 != null) { // if move is valid
for (int m = 0; m < nCards; m++) {
if (m != i && m != k) {
GameState futureStateLevel3 = futureStateLevel2.testMove(cards.get(m));
if (futureStateLevel3 != null) { // if move is valid
score = negamaxSuche(-player, futureStateLevel3, depthLeft-1, -beta, -alpha);
if (score >= beta) {
return score;
}
if (score > alpha) {
alpha = score; // alpha acts like max
}
}
}
}
}
}
}
}
}
return alpha;
}
}
}
これは正常に動作しているようですが、1の深さ（depthLeft=1）はすでに平均で50,000の移動（カード）を計算する必要があります。もちろん、これは多すぎる！
だから私の質問は次のとおりです。
- 実装はまったく正しいですか？このようなゲームをシミュレートできますか？不完全な情報に関しては、特に？
- スピードやワークロードでアルゴリズムを改善する方法は？ 例えば、良い結果を維持しながら、スピードを向上させるために、可能な限り50％のランダムセットへの可能な移動のセットを減らすことができます。
- 私は UCTアルゴリズムを見つけました（多分）。このアルゴリズムを知っていますか？あなたはそれを実装するのを手伝ってくれますか？
解決
ミニマックス検索あなたが実装したように検索すると、非常に不確実性があるゲームのための間違ったアプローチです。他のプレイヤーの間でカードの配布がわからないので、検索は実際のカードの実際の分布を考えることができなかったゲームを探索する時間の指数を費やすでしょう。
他のプレイヤーの手についての情報がほとんどまたはまったく情報がない場合は、より良いアプローチがプレイのために良いルールから始めることになるだろうと思います。のようなもの：
- あなたがラウンドで最初に遊ぶならば、あなたはラウンドに勝つチャンスがほとんどないのであなたの最低カードをプレイします。
- あなたがラウンドで遊ぶならば、ラウンドに勝つための最低のカードをプレイします。ラウンドに勝つことができない場合は、最低カードをプレイしてください。
最初は最初に検索に迷惑をかけず、これらの規則で遊ぶだけでなく、他のすべてのプレイヤーもこれらのヒューリスティックを使用すると仮定しています。プログラムが最初と最後のカードを観察するように各ラウンドプレイのプレイヤーは、各プレイヤーが保持する可能性が高いカードに関する情報の表を構築することができます。例えば。 9はこのラウンドに勝っただろうが、プレイヤー3はそれを再生しなかったので、カード9以上を持っていなければならない。各プレイヤーの手について情報が集められるので、検索スペースは最終的には、可能なゲームのミニマックス検索が次のカードに関する有用な情報をプレイするための有用な情報を生み出す可能性があるポイントに制約されます。
他のヒント
受け入れられた答えが本当に入っていない詳細を明確にしたい。
多くのカードゲームでは、あなたがそれらのすべてを生成する代わりにあなたの対戦相手が持つことができる未知のカードをサンプリングすることができます。短いスーツのような情報と、このサンプリングを行う際には、それぞれの可能な手の可能性を和らげる際には、遊びに与えられた特定のカードを保持する確率（各手が独立して解決する可能性のある世界である）を考慮に入れることができます。それから、完璧な情報検索を使って各手を解く。これらの世界のすべての上の最善の動きは、多くの人全体で最高の動きです - いくつかの警告。
ポーカーのようなゲームでは、これはうまく機能しません - ゲームはすべて隠された情報についてです。あなたの手の説明を隠してください。
しかし、トリックベースのカードゲームのようなゲームでは、これは非常によく機能します - 特に新しい情報が常に明らかにされているので。本当に良いプレーヤーは、とにかく全員が持っているものの良い考えを持っています。だから、合理的に強力なスカットと橋梁プログラムはこれらの考えに基づいています。
基礎となる世界を完全に解決できるのは、それは最善ですが、できない場合は、MiniMAXまたはUCTを使用して各世界で最良の動きを選択できます。このプロセスをまとめてミックスしようとするハイブリッドアルゴリズム（ISMCTS）もあります。ここでのクレームに注意してください。簡単なサンプリングアプローチはコードが簡単です - より複雑なものの前に簡単なアプローチを試す必要があります。
これは、不完全な情報へのサンプリングアプローチがうまく機能してきたときにいくつかの情報を与える研究論文があります：
ゲームツリー検索における完璧な情報モンテカルロサンプリングの成功を理解する（この論文はサンプリングアプローチがうまくいくときに分析します。）
状態評価、推論、およびトリックベースのカードゲームの検索の改善< / a>（この論文では、SKATのサンプリングの使用について説明します）
href="htps://www.jair.org/media/820/live-820-1957-jair.pdf" real="noreferrer">計算上の挑戦的なゲームの不完全な情報（この論文では橋のサンプリングについて説明します）
href="https://pure.york.ac.uk/portal/files/130141666/CowlingPowleywhitehouse2012.pdf" REL="noreferrer">情報セットモンテカルロツリー検索（このペーパーのマージサンプリングとUCT / Monte Carlo Tree Tree Search First Referenceの問題を回避します。）
承認された答えにおけるルールベースのアプローチの問題は、初期ルールを作成するのに必要なものを超えて計算資源を利用することができないということです。さらに、ルールベースのアプローチは、書くことができる規則の力によって制限されます。検索ベースのアプローチは、コンビナトリアル検索の力を使用して、プログラムの作者よりもはるかに強いプレイを生み出すことができます。
