B * - B*

Na ciência da computação , B * (pronuncia-se "B estrela") é um algoritmo de busca de melhor primeiro gráfico que encontra o caminho de menor custo de um determinado nó inicial para qualquer nó de meta (de um ou mais objetivos possíveis). Publicado pela primeira vez por Hans Berliner em 1979, está relacionado ao algoritmo de pesquisa A * .

Resumo

O algoritmo armazena intervalos para nós da árvore em oposição a estimativas de valor de ponto único. Em seguida, os nós folha da árvore podem ser pesquisados ​​até que um dos nós de nível superior tenha um intervalo que seja claramente "o melhor".

Detalhes

Avaliações de intervalo em vez de estimativas

Os nós folha de uma árvore B * recebem avaliações que são intervalos em vez de números únicos. O intervalo deve conter o valor verdadeiro desse nó. Se todos os intervalos anexados aos nós folha satisfizerem essa propriedade, então B * identificará um caminho ideal para o estado de objetivo.

Processo de backup

Para fazer backup dos intervalos dentro da árvore, o limite superior de um pai é definido como o máximo dos limites superiores dos filhos. O limite inferior de um pai é definido como o máximo do limite inferior dos filhos. Observe que diferentes filhos podem fornecer esses limites.

Término da busca

B * expande os nós sistematicamente para criar "separação", que ocorre quando o limite inferior de um filho direto da raiz é pelo menos tão grande quanto o limite superior de qualquer outro filho direto da raiz. Uma árvore que cria separação na raiz contém uma prova de que o melhor filho é pelo menos tão bom quanto qualquer outro filho.

Na prática, pesquisas complexas podem não terminar dentro dos limites práticos de recursos. Portanto, o algoritmo é normalmente aumentado com critérios de encerramento artificiais, como tempo ou limites de memória. Quando um limite artificial é atingido, você deve fazer um julgamento heurístico sobre qual movimento selecionar. Normalmente, a árvore forneceria evidências extensas, como os intervalos dos nós de raiz.

Expansão

B * é um processo best-first, o que significa que é muito eficiente atravessar a árvore, descendo repetidamente para encontrar uma folha para expandir. Esta seção descreve como escolher o nó a ser expandido. (Nota: Se a árvore é residente na memória ou não, é uma função da eficiência geral da implementação, incluindo como ela pode ser mapeada e / ou gerenciada por meio de memória real ou virtual.)

Na raiz da árvore, o algoritmo aplica uma de duas estratégias, chamadas provar-best e disprove-rest. Na estratégia provar melhor, o algoritmo seleciona o nó associado ao limite superior mais alto. A esperança é que a expansão desse nó aumente seu limite inferior mais alto do que o limite superior de qualquer outro nó.

A estratégia refutar-resto seleciona o filho da raiz que tem o segundo limite superior mais alto. A esperança é que, ao expandir esse nó, você possa reduzir o limite superior para menos do que o limite inferior do melhor filho.

Seleção de estratégia

Observe que a aplicação da estratégia refutar-rest não tem sentido até que o limite inferior do nó filho que tem o limite superior mais alto seja o mais alto entre todos os limites inferiores.

A descrição do algoritmo original não deu nenhuma orientação adicional sobre qual estratégia selecionar. Existem várias alternativas razoáveis, como expandir a escolha que tem a árvore menor.

Seleção de estratégia em nós não-raiz

Uma vez que um filho da raiz tenha sido selecionado (usando provar-best ou disprove-rest), o algoritmo desce para um nó folha selecionando repetidamente o filho que tem o limite superior mais alto.

Quando um nó folha é alcançado, o algoritmo gera todos os nós sucessores e atribui intervalos a eles usando a função de avaliação. Em seguida, é necessário fazer backup dos intervalos de todos os nós usando a operação de backup.

Quando as transposições são possíveis, a operação de backup pode precisar alterar os valores dos nós que não estavam no caminho de seleção. Nesse caso, o algoritmo precisa de ponteiros dos filhos para todos os pais para que as alterações possam ser propagadas. Observe que a propagação pode cessar quando uma operação de backup não altera o intervalo associado a um nó.

Robustez

Se os intervalos estiverem incorretos (no sentido de que o valor da teoria do jogo do nó não está contido no intervalo), então B * pode não ser capaz de identificar o caminho correto. No entanto, o algoritmo é bastante robusto para erros na prática.

O programa Maven (Scrabble) possui uma inovação que melhora a robustez do B * quando erros de avaliação são possíveis. Se uma pesquisa for encerrada devido à separação, o Maven reinicia a pesquisa após ampliar todos os intervalos de avaliação em um pequeno valor. Esta política alarga progressivamente a árvore, eventualmente apagando todos os erros.

Extensão para jogos de dois jogadores

O algoritmo B * se aplica a jogos determinísticos de soma zero com dois jogadores. Na verdade, a única mudança é interpretar "melhor" em relação ao lado que se move naquele nó. Portanto, você pegaria o máximo se o seu lado estivesse se movendo e o mínimo se o oponente estivesse se movendo. Da mesma forma, você pode representar todos os intervalos da perspectiva do lado a ser movido e, em seguida, negar os valores durante a operação de backup.

Formulários

Andrew Palay aplicou B * ao xadrez. As avaliações de endpoint foram atribuídas por meio de pesquisas de movimento nulo. Não há nenhum relatório sobre o desempenho desse sistema em comparação com os mecanismos de pesquisa de poda alfa-beta executados no mesmo hardware.

O programa Maven (Scrabble) aplicou a pesquisa B * a jogos finais. As avaliações de endpoint foram atribuídas usando um sistema de planejamento heurístico.

O algoritmo de busca B * foi usado para calcular a estratégia ótima em um jogo de soma de um conjunto de jogos combinatórios.

Veja também

• Ramificação e limite

Referências

• Berliner, Hans (1979). "The B * Tree Search Algorithm. A Best-First Proof Procedure" . Inteligência Artificial . 12 (1): 23–40. doi : 10.1016 / 0004-3702 (79) 90003-1 .
• Russell, SJ; Norvig, P. (2003). Inteligência Artificial: Uma Abordagem Moderna . Upper Saddle River, NJ: Prentice Hall. p. 188. ISBN 0-13-790395-2.
• Sheppard, Brian (2002). "Scrabble de campeonato mundial de calibre" . Inteligência Artificial . 134 (1–2): 241–275. doi : 10.1016 / S0004-3702 (01) 00166-7 .