9MenのモリスゲームにゲームAIを実装しようとしています。
これまでのところ、ボードは次のように表されています。
public class board
{
public node []gNode = null;
... // so the table has 24 nodes, for 9 men morris game:
gNode = new node[24];
...
int evaluateBoard(); // evaluates the current board (tokens)
}
さて、すべてのノードは次のように表されます。
public class node
{
node() // constructor
{ ... }
// setting current node's neighbours (maximum 4 neighbours)
void setNeighbours(int left, int right, int top, int bottom)
{ ... }
short gOccupiedByTeam = renderer.TEAM_NOTEAM; // info if this node is occupied by a token (and a wich team this token belongs to)
short []gNeighbourId = null; // info about this node neighbours (can be max. 4 in a 9Men's morris game)
short gInternalID = -1; // board's IDs (from 0..23)
short gTokenID = -1; // this node can be occupied by a token. (from 0 .. 8) -see below the token class.
short gNodeScore = -1; // a dummy node score.
vector3 gLocation = null; // 3d coordinates for this node.
}
トークンは次のよう になります。
public class token
{
token(vector3 startpos, short nodeId) // Constructor.
{ ... }
public physx gPhysX = null; // 3d coordinates , velocity , accel. for this Token.
public boolean bIsAlive = false; // is this token alive ? (or eliminated?)
public boolean bFormsMill = false; // does it form a Mill?
public short gNodeID = -1; // "link" this token with a gNodeID (when placing a token on current board). See above the node class. This represents a link ID to that node.
public short gTokenMill1 = -1; // used when this token forms a mill (with gTokenMill1 token!)
public short gTokenMill2 = -1; // same.
}
そして、これが私が立ち往生している私のアルファベータ剪定アルゴリズムの実装です:
public int getBestMove(board board, int depth, int alpha, int beta, boolean bIsPlayer)
{
// if depth reached, return current's board's Evaluation (a score).
if (depth == 0) return board.evaluateBoard(bIsPlayer);
// is it Player's turn ? (max?)
if (bIsPlayer)
{
// QUESTIONS:
// retrevie all possible "boards" below ! (all new possible token moves)
// 1. here i should generate a new board with 1st possible move (for player token1) ?? ... then a second new board with 2nd possible move still for token1 ? .. and so on until no possible moves for token1?
// (remembering that a token can move in 4 available spots - wich are a neighbour?)
//
// 2. the problem is that if i generate 4 new boards as per token 1 above let's say, then it will "eat" lot of memory for all 18 tokens and a function recursion depth of 5 for example, right ?
// 3. how do i fix point 2?
ArrayList<board> possible_boards = board.getAllPossibleBoards();
// 4. ok, some possible boards were generated, loop thru them starting with the first one and calling recursively this function, is it right ?
for(board iterator: possible_boards)
{
alpha = Math.max(alpha, getBestMove(iterator, depth - 1, alpha, beta, !bIsPlayer));
if (beta < alpha)
{
break;
}
}
// 5. how do i return best move to main calling function ? (wich token is it best move from all of these board's moves ?
return alpha;
}
else
{
ArrayList<board> possible_boards = board.getAllPossibleBoards();
for(board iterator: possible_boards)
{
beta = Math.min(beta, getBestMove(iterator, depth - 1, alpha, beta, !bIsPlayer));
if (beta < alpha)
{
break;
}
}
return beta;
}
}
OK、これがこれまでの私の機能です。正しい道を進んでいてもわからない??!
私の機能で何が問題になっていますか？
上記の質問に答えてください (getBestMove() 関数の 1 から 5)。
事前に感謝し、私の言語の間違いを避けてください（私の英語はあまり上手ではありません）
saeednさん、お返事ありがとうございます!!
私は誰も私に答えないだろうと思っていました:)。何が起こっているのかを理解するのに本当に役立ちます。
そのため、 CheckWinner( bool )は、現在のプレイヤーがこの深さで非常に優れたアドバンテージ (勝ったり、対戦相手をブロックするなどの非常に優れた動きなど) を持っているかどうかを確認し、そうであれば、現在のプレイヤーにBIGスコアを返します。これはすべて、プレーヤーも対戦相手も毎ターン勝利（大きなスコア）を試みないためですよね？
それ以外の場合、depth =0 の場合は、現在選択されているボードの評価 (スコア) を返します ( int evaluateBoard() )。
この後、1 つのボードを生成する必要があります (1 つのトークンの可能な移動を使用)。
while( board.generateNextPossibleBoard(nextBoard) ) // board generated and stored in "nextBoard". Also check if it is a valid board or no more boards to generate further.
OK、新しく生成されたボードがあるので、再帰して、より良いボード (より良いSCOREを持つボード) が見つかった場合は、現在のボードを selectedBoard に保存します。そうでない場合は、カットオフして戻ります (ツリーをさらに下にチェックしないでください)。
ありがとうございます！