14

Tic-Tac-Toe ボットを作成しているときに、「ツリー」を理解しようとして大きなブロックが発生しています。概念は理解できますが、実装する方法がわかりません。

そのような場合にツリーを生成する方法の例を誰かに見せてもらえますか? または、ツリーの生成に関する優れたチュートリアルですか? 難しい部分は部分ツリーを生成することだと思います。ツリー全体の生成を実装する方法は知っていますが、その一部は知りません。

4

5 に答える 5

15

三目並べボードの任意の時点で、考えられるすべての動きが分岐であると想像してください。ボードの現在の状態はルートです。一手は分岐。ここで (一度に 1 つずつ)、各ブランチが現在の状態になると仮定します。それぞれの可能な動きが新しいブランチになります。木の葉は、最後の動きが行われ、ボードがいっぱいになったときです。

ツリーが必要な理由は、ツリーが構築されたら、「WIN」シナリオであるリーフが最も多いブランチを特定する必要があるためです。考えられるすべての結果のブランチを構築し、勝利の総数を合計してから、最終的に最も多くの勝利を収める可能性がある動きを行います。

ツリーを次のようにします。

class Node {
public:
   std::list< Node > m_branches;
   BoardState m_board;
   int m_winCount;
}

std::list< Node > tree;

ここで、ツリー内のブランチのリストを反復処理し、ブランチごとに、そのブランチを反復処理します。これは、再帰関数を使用して実行できます。

int recursiveTreeWalk( std::list< Node >& partialTree)
{

   for each branch in tree
       if node has no branches
           calculate win 1/0;
       else
           recursiveTreeWalk( branch );

   partialTree.m_winCount = sum of branch wins;
}

// initial call
recursiveTreeWalk( tree )

非常に疑似コード。

于 2010-04-30T12:12:11.720 に答える
5

ツリーをメモリに保持する必要はないと思います。次のような再帰関数を実装するだけです。

Move getBestMove(Board state, boolean myTurn)

次に、勝ち、負け、または引き分けの状態に達するまで、単純に再帰します。

紙に描いた場合、コールスタックは時間の経過とともにツリーのように見えます。対戦相手が (間違いなく/ほとんどの場合) 負けるノードにつながる動きを返す必要があります (対戦相手も getBestMove を使用してプレイしますが)。

しかし、三目並べと同じくらい小さい状態空間の場合、最良の動きで完全なルックアップ テーブルを実行するだけで済みます。:-)

于 2010-04-30T12:07:16.160 に答える
4

このコードプロジェクトの記事は興味深いかもしれません:

MiniMax アルゴリズムで三目並べを解く

これは C# ですが、C++ に変更しても問題ありません。

この記事は、C++ で最初の Tic-Tac-Toe ゲームを実装しようとしたときにも役立ちました。

ミニマックスの説明

于 2010-04-30T12:29:55.980 に答える
0

メモリ内にツリーを生成したい場合 (これは必要ありません)、おそらく次のようなアルゴリズムを使用できます (疑似コード):

GenTree(State s):
  T <- empty tree  // T is a tree of States
  SetRoot(T, s)

  ForEach (s' in Successors(s)):
    AddChild(T, GenTree(s'))

  return T

// Call it
GenTree(currentMove)

どこ

Successors(s)  // returns a list of successor states of s
AddChild(p, n)  // adds n to the list of p's children
于 2010-04-30T12:24:44.647 に答える
0

Tic Tac Toe ゲームを実装することは、AI と検索スペースの観点から、おそらく最も簡単に解決できる問題です。

鍵となるのは、Minimax、反復的深化、深さ優先探索、およびアルファ ベータ プルーニングアルゴリズムを使用して問題にアプローチすることです。

これは、Python でのゲームの実装です。これは、わずか 200 行のコードでHuman vs. Human、 、Human vs. Computer、およびとしてゲームをプレイする機能を備えていますComputer vs. Computer。また、最適な動きに至るまでに到達/プルーニングされたノードの深さと数に関する統計も保持します。

現在の AI トピックとソリューションに関する基本的な知識を提供するedX.org人工知能コースを強くお勧めします。

于 2019-04-05T17:21:40.443 に答える