0

次のゲームをシミュレートしようとしています: ゲームは 2 人のプレーヤーでプレイされます。頂点と辺を持つグラフがあるとします。ターンごとに 1 つのエッジを削除できます。頂点を分離するとポイントが得られ、別のエッジを削除できます。エッジがなくなるまでプレイし、その時点で最も多くのポイントを持つプレイヤーがゲームに勝ちます。

グラフを配列で表します。これは、別のプログラムによって生成された別のファイルから読み取ったものです。たとえば、次のようなものです。

0 1 1 0
1 0 1 1
1 1 0 0
0 1 0 0

プレイヤー 1 は 4/0 で勝つことができますが、プレイヤー 2 も勝つことができます。最良の結果はプレイヤー 1 の 1/3 です。

編集: 「プレイヤーは 4/0 でどのように勝つことができますか?」:

A--B--D 
| /
c

A--B--D
|
C

A  B--D
|
C

ご覧のように、真ん中の端が取り除かれると、最初のプレーヤーは 4 ポイントを獲得します。それ以外の場合、他のプレーヤーは 4 ポイントを獲得します。

私は各プレイヤーにとって最良の結果を得ることができますが、他のプレイヤーは毎ターン自分の最良のターンを選択しません。私はそれを試すのに多くの時間を費やしましたが、いつも同じ問題が発生します。

編集: 私は今、これを解決するのにかなり近づいていると思います (また、私は常に考えてきました)、ターンごとに 2 つのスコアを保存する必要があるだけです。現在のプレーヤーのスコアが受け入れられます。そうすれば、プレイヤーが 4/0 の動きを無視できるようになるはずです..

編集:私は提案を実装しようとしましたが、残念ながら私は再び立ち往生しています. 高すぎる奇妙な出力が得られるか、関数は単に答えとして -2 を返しますが、他の大きなグラフでは機能しません。私はそれを修正するために多くのことを試みましたが、うまくいきません。以下のコードは私が今試しているものですが、残念ながらどちらも機能しません:

int Matrix::getTurn (bool** array) {
   if (edges == 0) 
      return 0;
    for (int i=0; i<edges; i++) {
        for (int j=0; j<edges; j++) {
            if (array[i][j] == true) {
                array[i][j] = false;
                array[j][i] = false;
                score = getScore (array, i, j);

                if (score > 0)
                   score += getTurn (array);
                else score -= getTurn (array);

                if (score > maxScore)
                   maxScore = score;

                array[i][j] = true;
                array[j][i] = true;
            }
        }
    }
   return maxScore;
}

maxScore と score はクラスのメンバー変数です。誰か修正が必要な部分を指摘してもらえませんか?

別の編集、まだ機能していませんが、エラーがまったく表示されません。それは1を出力し続けます、それはmaxScoreを変更しなかったようです... Takkenは残っているエッジの数です。配列の境界を使用してみましたが、違いはありません..

int Matrix::berekenZet (bool** array) {
   if (takken == 0)
      return 0;
   int maxScore = 0, score = 0;
    for (int i=0; i<takken; i++) {
        for (int j=0; j<takken; j++) {
            if (array[i][j] == true) {
                array[i][j] = false;
                array[j][i] = false;
                takken -= 1;
                score = berekenScore (array, i, j);

                if (score > 0)
                   score += berekenZet (array);
                 else score -= berekenZet (array);

                if (score > maxScore)
                   maxScore = score;

                array[i][j] = true;
                array[j][i] = true;
                takken += 1;
                score = 0;
            }
        }
    }
   return maxScore;
}

前もって感謝します。

4

1 に答える 1

1

Minimaxアルゴリズムの何らかの形式を実装しようとしているようです。これは、両方のプレーヤーが自分自身で最善の手を打つと仮定して、プレーヤーにとって可能な最高のスコアを見つけます。

しかし、あなたのコードにはいくつかの奇妙なことがあります: スコア変数が多すぎてmaxScore、関数の途中で無条件に割り当てられ (そのため古い値が失われます)、スコアがゼロ以外の値を受け取る方法がわかりません。

これを疑似コードで実装します。この関数getScore(graph)は、そのターンのプレーヤーに可能な限り最高のスコアを返します (両方のプレーヤーが自分のスコアを最大化するためにプレイすると仮定します)。ここで、「スコア」とは、プレーヤーのポイントから他のプレーヤーのポイントを差し引いたものを意味します。ミニマックスのネガマックスバリアントを使用しています。これは、あるプレーヤーの +x のスコアが別のプレーヤーの -x のスコアと同じであるという事実を利用して、2 回書く必要がないようにします。両方のプレイヤーがまったく同じ動きをすることができるので、誰の番であるかを追跡する必要さえありません。

int getScore(graph):
    if no possible moves:
        return 0
    maxScore = -infinity
    for each possible move:
        make the move
        score = the score directly obtained by this move
        if the player gets another turn:
            score += getScore(graph)
        else:  //opponent turn - subtract opponent's best score from player score
            score -= getScore(graph)
        maxScore = max(maxScore, score)
        undo the move
    return maxScore
于 2013-03-28T16:59:08.037 に答える