If you're looking for game tree as it's used in game theory (not combinatorial game theory), please see Extensive-form game. In combinatorial game theory, a game tree is a directed graph whose nodes are positions in a game and whose edges are moves. The complete game tree for a game is the game tree starting at the initial position and containing all possible moves from each position; the complete tree is the same tree as that obtained from the extensive-form game representation.

PropertyValue
dbpedia-owl:abstract
  • If you're looking for game tree as it's used in game theory (not combinatorial game theory), please see Extensive-form game. In combinatorial game theory, a game tree is a directed graph whose nodes are positions in a game and whose edges are moves. The complete game tree for a game is the game tree starting at the initial position and containing all possible moves from each position; the complete tree is the same tree as that obtained from the extensive-form game representation. The diagram shows the first two levels, or plies, in the game tree for tic-tac-toe. We consider all the rotations and reflections of positions as being equivalent, so the first player has three choices of move: in the center, at the edge, or in the corner. The second player has two choices for the reply if the first player played in the center, otherwise five choices. And so on. The number of leaf nodes in the complete game tree is the number of possible different ways the game can be played. For example, the game tree for tic-tac-toe has 26,830 leaf nodes. Game trees are important in artificial intelligence because one way to pick the best move in a game is to search the game tree using the minimax algorithm or its variants. The game tree for tic-tac-toe is easily searchable, but the complete game trees for larger games like chess are much too large to search. Instead, a chess-playing program searches a partial game tree: typically as many plies from the current position as it can search in the time available. Except for the case of "pathological" game trees (which seem to be quite rare in practice), increasing the search depth (i.e. , the number of plies searched) generally improves the chance of picking the best move. Two-person games can also be represented as and-or trees. For the first player to win a game, there must exist a winning move for all moves of the second player. This is represented in the and-or tree by using disjunction to represent the first player's alternative moves and using conjunction to represent all of the second player's moves.
  • El árbol de juego es un grafo dirigido de tipo árbol en que cada nodo representa una posible elección para uno de los jugadores. Cualquier sucesión de jugadas puede representarse por un camino conexo dentro del árbol de juego. Si el juego acaba siempre después de un número finito de pasos, entonces el árbol tiene un número finito de nodos.
  • ゲーム木（ゲームき、Template:Lang-en-short）は、組合せゲーム理論において、ゲームの盤面を有向グラフ（一方通行の枝を持つグラフ）のノード（節点・頂点、英語：node）で表し、手をエッジ（枝・辺、英語：edge）で表したものである。完全ゲーム木とは、ゲームの最初から指せる全ての手を含んだゲーム木である。なお、組合せゲーム理論ではない通常のゲーム理論の「ゲームの木」については展開型ゲームを参照。 右図は、三目並べのゲーム木の最初の2レベル（あるいは2手）までを示したものである。ここでは、盤面を回転させたり反転させて同じになるものは等価としているため、最初の1手は3種類（中心、角、角と角の間）しかない。2手目は、1手目が中心の場合は2種類、そうでない場合は5種類ある。 完全ゲーム木の葉ノードの数をゲーム木複雑性と呼び、そのゲームが最終的にどれだけの異なる盤面で終わるかを示している。三目並べのゲーム木複雑性は 26,830 である。 ゲーム木は人工知能で重要であり、最良の手はゲーム木を探索することで得られ、ミニマックス法などのアルゴリズムを使用する。三目並べのゲーム木は小さいので探索も容易だが、チェスなどの完全ゲーム木は大きすぎて全体を探索することができない。その場合は代わりに部分ゲーム木を使う。部分ゲーム木は、一般に現在の盤面から指せる手を時間内に探索できるぶんだけ含んだものである。 2人で対戦するゲームはAND/OR木で表現することもできる。先手が勝つには、後手がどういう手を指しても先手が勝つ手が存在しなければならない。これをAND/OR木では、先手の指せる手を論理和で表し、後手のさせる手を論理積で表す。
  • Partia danej gry może być zapisana jako kolejne, naprzemienne ruchy obu graczy. Drzewo gry - reprezentacja umożliwiająca opisanie sytuacji możliwych do osiągnięcia po kolejnych ruchach graczy. Węzły drzewa to przedstawienie poszczególnych sytuacji na planszy. Przy każdym węźle musi być określona informacja, który z graczy powinien wykonać ruch. Poziom 0 to poziom gracza, kolejny poziom jest poziomem przeciwnika, itd. Gałęzie przedstawiają wszystkie możliwe ruchy graczy. Liczba liści (węzłów stopnia 1) w kompletnym drzewie gry jest nazywana złożonością gry. Jest to liczba możliwych różnych sposobów rozegrania gry. Przykładowo, złożoność klasycznej gry w "kółko i krzyżyk" jest równa 26830. Drzewa gry są ważne w sztucznej inteligencji, ponieważ jednym ze sposobów wybrania najlepszego ruchu w grze jest przeszukanie drzewa gry przy użyciu algorytmu minimax lub jego wariantów. Drzewo gry dla "kółka i krzyżyka" jest łatwe do przeszukania, lecz kompletne drzewa gry dla większych gier są na to zbyt duże. Zamiast tego, programy grające np. w szachy przeszukują częściowe drzewa gry tak daleko, na ile pozwala im określony z góry dostępny czas. Mając kompletne drzewo danej gry, można "rozwiązać" grę - to znaczy znaleźć sekwencję ruchów, które prowadzą zawsze jednego z graczy do zwycięstwa, bądź gwarantują osiągnięcie remisu.
  • 遊戲樹是指組合博弈理論中用來表達一個賽局中各種後續可能性的樹，一個完整的遊戲樹（complete game tree）回有一個起始節點，代表賽局中某一個情形，接著下一層的子節點是原來父節點賽局下一步的各種可能性，依照這規則擴展直到賽局結束。遊戲樹相同於擴展形式的博弈理論中的樹。 遊戲樹中形成的葉節點代表各種遊戲結束的可能情形，例如井字遊戲會有26,830個葉節點。 File:Tic-tac-toe-game-tree. svg 一個井字遊戲的遊戲樹範例 遊戲樹在人工智慧的應用相當重要，若要尋找某賽局中最佳的步法的一個方式，是利用極小化極大演算法在遊戲樹中搜尋最佳解，例如在井字遊戲中電腦可以很快速地找到最佳解並做出決策，但是對於象棋、圍棋這一類大型的博弈遊戲，列出完整遊戲樹可能使電腦計算能力難以應付，因此對這類遊戲通常會採用部分的遊戲樹（partial game tree）來進行搜尋，典型的部分遊戲樹通常是限制遊戲樹的層數，並剔除不佳的步法（例如自殺），一般而言搜尋的層數越多，能走出較佳步法的機會也越高。 若是兩人遊戲，除了可以用遊戲樹表達之外，也可以用And–or tree表示。
dbpedia-owl:thumbnail
dbpedia-owl:wikiPageExternalLink
dcterms:subject
rdfs:comment
  • El árbol de juego es un grafo dirigido de tipo árbol en que cada nodo representa una posible elección para uno de los jugadores. Cualquier sucesión de jugadas puede representarse por un camino conexo dentro del árbol de juego. Si el juego acaba siempre después de un número finito de pasos, entonces el árbol tiene un número finito de nodos.
  • ゲーム木（ゲームき、Template:Lang-en-short）は、組合せゲーム理論において、ゲームの盤面を有向グラフ（一方通行の枝を持つグラフ）のノード（節点・頂点、英語：node）で表し、手をエッジ（枝・辺、英語：edge）で表したものである。完全ゲーム木とは、ゲームの最初から指せる全ての手を含んだゲーム木である。なお、組合せゲーム理論ではない通常のゲーム理論の「ゲームの木」については展開型ゲームを参照。 右図は、三目並べのゲーム木の最初の2レベル（あるいは2手）までを示したものである。ここでは、盤面を回転させたり反転させて同じになるものは等価としているため、最初の1手は3種類（中心、角、角と角の間）しかない。2手目は、1手目が中心の場合は2種類、そうでない場合は5種類ある。 完全ゲーム木の葉ノードの数をゲーム木複雑性と呼び、そのゲームが最終的にどれだけの異なる盤面で終わるかを示している。三目並べのゲーム木複雑性は 26,830 である。 ゲーム木は人工知能で重要であり、最良の手はゲーム木を探索することで得られ、ミニマックス法などのアルゴリズムを使用する。三目並べのゲーム木は小さいので探索も容易だが、チェスなどの完全ゲーム木は大きすぎて全体を探索することができない。その場合は代わりに部分ゲーム木を使う。部分ゲーム木は、一般に現在の盤面から指せる手を時間内に探索できるぶんだけ含んだものである。 2人で対戦するゲームはAND/OR木で表現することもできる。先手が勝つには、後手がどういう手を指しても先手が勝つ手が存在しなければならない。これをAND/OR木では、先手の指せる手を論理和で表し、後手のさせる手を論理積で表す。
  • 遊戲樹是指組合博弈理論中用來表達一個賽局中各種後續可能性的樹，一個完整的遊戲樹（complete game tree）回有一個起始節點，代表賽局中某一個情形，接著下一層的子節點是原來父節點賽局下一步的各種可能性，依照這規則擴展直到賽局結束。遊戲樹相同於擴展形式的博弈理論中的樹。 遊戲樹中形成的葉節點代表各種遊戲結束的可能情形，例如井字遊戲會有26,830個葉節點。 File:Tic-tac-toe-game-tree. svg 一個井字遊戲的遊戲樹範例 遊戲樹在人工智慧的應用相當重要，若要尋找某賽局中最佳的步法的一個方式，是利用極小化極大演算法在遊戲樹中搜尋最佳解，例如在井字遊戲中電腦可以很快速地找到最佳解並做出決策，但是對於象棋、圍棋這一類大型的博弈遊戲，列出完整遊戲樹可能使電腦計算能力難以應付，因此對這類遊戲通常會採用部分的遊戲樹（partial game tree）來進行搜尋，典型的部分遊戲樹通常是限制遊戲樹的層數，並剔除不佳的步法（例如自殺），一般而言搜尋的層數越多，能走出較佳步法的機會也越高。 若是兩人遊戲，除了可以用遊戲樹表達之外，也可以用And–or tree表示。
  • If you're looking for game tree as it's used in game theory (not combinatorial game theory), please see Extensive-form game. In combinatorial game theory, a game tree is a directed graph whose nodes are positions in a game and whose edges are moves. The complete game tree for a game is the game tree starting at the initial position and containing all possible moves from each position; the complete tree is the same tree as that obtained from the extensive-form game representation.
  • Partia danej gry może być zapisana jako kolejne, naprzemienne ruchy obu graczy. Drzewo gry - reprezentacja umożliwiająca opisanie sytuacji możliwych do osiągnięcia po kolejnych ruchach graczy. Węzły drzewa to przedstawienie poszczególnych sytuacji na planszy. Przy każdym węźle musi być określona informacja, który z graczy powinien wykonać ruch. Poziom 0 to poziom gracza, kolejny poziom jest poziomem przeciwnika, itd. Gałęzie przedstawiają wszystkie możliwe ruchy graczy.
rdfs:label
  • Game tree
  • Árbol de juego
  • ゲーム木
  • Drzewo gry
  • 遊戲樹
owl:sameAs
foaf:depiction
foaf:page
is dbpedia-owl:knownFor of
is dbpedia-owl:wikiPageRedirects of
is dbpprop:knownFor of
is owl:sameAs of
is foaf:primaryTopic of