Tic-Tac-Toe プログラムを作成しています。私はそれでミニマックスを使用する予定です。考えられるすべてのゲーム シーケンス用のスペースを備えたツリーを作成しましたが、それを埋める方法を探しています。私は現在このタイプを持っています：
typedef struct name
{
char grid [3] [3];
struct name * child [9];
} node;
ここに示されているように、グリッドを埋める方法を探しています。すべての可能な組み合わせが存在することを確認するために、グリッドを埋めるにはどうすればよいですか? 私の計画は、プレイヤーが取ることができるすべての動きをゲームに認識させ、勝つためにどの手順を実行するかを決定することです (まだ決定の部分を理解する必要がありますが、ツリーのグリッドを埋めることができるまでそれを保持しています) .
私には再帰の最有力候補のように聞こえます...
ベース3の位置をエンコードします。未使用のグリッドを作成し0ます。「X」のグリッドa 1; および「O」の付いたグリッド2。したがって、使用できる完全なグリッドの絶対最大数は3 ^ 9 = 19683です（これらの一部は無効な三目並べ表現です）
それで、あなたが「020112021」を扱っているとしましょう。その子は次のとおりです。
020112021 /* father */ (4759 base 10)
=========
020112022 father + 1 (1 base 3)
0201120x1 /* invalid */ father + 3 (10 base 3)
020112121 father + 9 (100 base 3)
02011x021 /* invalid */ father + 27 (1000 base 3)
020122021 father + 81 (10000 base 3)
020212021 father + 243
021112021 father + 729
0x0112021 /* invalid */ father + 2187
120112021 father + 6561 (100000000 base 3)
ここから先に進む方法がわかると思います。
再帰をリストにするのは難しいため、疑似コード:
function descend(X_or_O, board)
for square in board
If square isn't empty: continue
new_board = Fill in square with X_or_O.
Check for a winner (if yes, return)
newer_board = descend(opposite of X_or_O, new_board)
tack newer_board onto the tree.
clear out square
forいくつかのループとifステートメントでそれを行うことができるはずです。
編集: 上記のリンクが切れた場合に備えて、1989 年 10 月のScientific Americanの Tinkertoy Computer の説明への参照です。これは、 The Tinkertoy Computer and Other Machinations と同じ著者による他の SA アミューズメント記事と共に編集および公開されています。このマシンを構築した人 (およびギャル) は、アルファベータ検索を回避するだけでなく、ボードを簡単に計算できるものに圧縮するのに十分賢かった. ティンカートイズ製。
これは再帰の典型的なケースです。
typedef struct name
{
char grid [3] [3];
struct name * child [9];
} node;
node * new_grid(node *parent) {
node *n = calloc(1, sizeof(node));
if (parent)
memcpy(n->grid, parent->grid, sizeof(grid));
}
// is n a winner based on the move just made at x,y?
int winner(const node *n, int x, int y) {
return (n->grid[x][0] == n->grid[x][1] == n->grid[x][2]) ||
(n->grid[0][y] == n->grid[1][y] == n->grid[2][y]) ||
((x == y) && (n->grid[0][0] == n->grid[1][1] == n->grid[2][2])) ||
((2-x == y) && (n->grid[0][2] == n->grid[1][1] == n->grid[2][0]));
}
void fill(node *n, char c) {
int x, y, children;
node *child;
for (x = 0; x < 3; x++) {
for (y = 0; y < 3; y++) {
if (n->grid[x][y])
continue;
child = n->child[children++] = new_grid(n);
child->grid[x][y] = c;
// recurse unless this is a winning play
if (!winner(child, x, y))
fill(child, c == 'x' ? 'y' : 'x');
}
}
}
int main(void) {
node *start = new_grid(0);
fill(start);
}
ここに実用的なソリューションがあります。Pythonで実装されていますが、役立つと思います。
ゲーム ツリーはbuild_tree関数によって再帰的に構築され、リストのリストとして実装されます。
このbuild_tree関数は、ボード (ツリーのノード) と、順番にプレイする駒を入力パラメーターとして受け取り、その駒をボードに適用した結果として考えられるすべての新しいボードを作成します。次に、これらの新しいボードごとにbuild_tree関数を再度呼び出しますが、今度はプレイする番の駒を変更します。ボードが終了する (空の四角がない) 場合、再帰は終了します。
これは、1x3 ボードの結果のツリーです。
[(0, 0, 0), [[('x', 0, 0), [[('x', 'o', 0), [('x', 'o', 'x')] ], [('x', 0, 'o'), [('x', 'x', 'o')]]]], [(0, 'x', 0), [[('o') ', 'x', 0), [('o', 'x', 'x')], [(0, 'x', 'o'), [('x', 'x', ' o')]]]], [(0, 0, 'x'), [[('o', 0, 'x'), [('o', 'x', 'x')]], [(0, 'o', 'x'), [('x', 'o', 'x')]]]]]]
空の四角は「0」で示されます。
三目並べゲームの場合は、3x3 ボードにするために に変更blank_board = (0,0,0)してください。blank_board = (0,0,0,0,0,0,0,0,0)
def change_piece(piece):
if piece == 'x': return 'o'
return 'x'
def is_terminal(board):
"""Check if there are any empty square in the board"""
for square in board:
if square == 0:
return False
return True
def build_tree(node, piece):
"""Build the game tree recursively.
The tree is implemented as a list of lists.
"""
child_nodes = []
for index, value in enumerate(node):
if value == 0:
new_node = list(node)
new_node[index] = piece
new_node = tuple(new_node)
if not is_terminal(new_node):
child_nodes.append(build_tree(new_node,change_piece(piece)))
else:
child_nodes.append(new_node)
if child_nodes:
return [node,child_nodes]
return
if __name__ == "__main__":
blank_board = (0,0,0)
game_tree = build_tree(blank_board,'x')
print(game_tree)