miniaturadaimagem|306x306px|Os dois primeiros turnos de um jogo da velha dispostos em uma árvore de jogo Sob o contexto da teoria combinatória dos jogos, árvore de jogo é um grafo que representa as possibilidades de um jogo com informações perfeitas. Também chamada de árvore de busca, ela analisa o jogo adversário a fim de determinar qual jogada pode levar a vitória.
Definição A árvore de jogo, ou árvore de busca, pode ser descrita como uma técnica para analisar o jogo adversário, a fim de determinar qual estratégia o jogador deve tomar para vencer o jogo, além de alertar sobre as possíveis vantagens e armadilhas cada jogada pode oferecer. Na teoria de jogos, a árvore de jogo é um grafo cujos nós são as posições — como a disposição das peças em um tabuleiro de xadrez — e as flechas são os movimentos — tal qual a movimentação de uma peça. Ao final do jogo, haveria uma árvore com todas as possibilidades que os jogadores tiveram em cada rodada. Por exemplo, no jogo da velha, há um total de 255 168 escolhas.
Uma partida, então, é qualquer caminho da raiz até o final, que seria uma folha. Na prática, é incomum a geração da árvore que representa o jogo de forma integral, logo, opta-se por construir gerações parciais e, a partir delas, determinar uma estratégia.
Algoritmos e computadores Tradicionalmente, as estratégias de busca apresentam árvores de jogos que descrevem todos os estados possíveis a partir de um estado inicial dado. Constituídos de nós, esses são associados a uma determinada profundidade, que aumenta em uma unidade de um nó para um nó filho.
A árvore de jogo, sobretudo a árvore de jogo parcial, é utilizada por algoritmos para determinar a melhor estratégia para a situação atual. Para as inteligências artificiais, há programas que utilizam de uma profundidade fixa de jogadas, até a qual todas as possibilidades são consideradas, enquanto outras buscam por uma árvore de jogo mais informadas, contudo, com menor profundidade.
Exemplos Em um jogo eletrônico, as árvores de jogos também podem ser utilizadas. À título de exemplo, os capítulos do jogo da Quantic Dream Detroit: Become Human são dispostos em fluxogramas, apresentando escolhas e tomadas de decisões realizadas pelo jogador, de forma similar à arvore de jogo na teoria de jogos.
Categoria:Árvores (teoria dos grafos) Categoria:Teoria dos jogos Categoria:Teoria dos grafos