|
TProcura
Biblioteca em C++ para testes paramétricos de algoritmos, e coleção de algoritmos de procura e otimização
|
A procura efetuada anteriormente, explora todas as possibilidades, independentemente de serem realmente relevantes para a estratégia final ou não. No caso de se saber que numa linha alternativa, as brancas obtiveram um valor de 10, e atualmente está-se a ver uma linha em que as pretas já têm hipótese de optar por uma linha com 10 ou menos, então é completamente indiferente continuar a explorar as restantes alternativas, já que as brancas não irão escolher esta linha quando podem optar por uma que lhe garante um valor final de 10. Pode-se portanto cortar o resto da linha. Este corte chama-se corte alfa, dado que o valor de alfa é a melhor alternativa das brancas, e foi esse valor que foi utilizado de forma a suportar o corte. Se o raciocínio inverso fosse feito, chamar-se-ia corte beta.
Os valores iniciais de alfa/beta, dado que de início nem as brancas nem as pretas têm alternativas, são a derrota/vitória. Vamos fixar esses valores em -1000 (ganham as pretas) e 1000 (ganham as brancas), e repetir a procura anterior com os cortes alfa/beta:
|
Geração |
Estado |
Nível / Valor |
Pai |
Expansão |
|||||||||
| 1 |
|
N2 1 |
0 | 1 MAX -1000/+1000 |
|||||||||
| 2 |
|
N1 1 |
1 | 4 MIN 1/+1000 |
|||||||||
| 3 |
|
N1 -1 |
1 | 3 MIN 1/+1000 |
|||||||||
| 4 |
|
N1 1 |
1 | 2 MIN -1000/+1000 |
|||||||||
| 5 |
|
N0 1 |
4 | -1000/+1000 | |||||||||
| 6 |
|
N0 2 |
4 | -1000/1 | |||||||||
| 7 |
|
N0 -1 |
3 | 1/+1000 (corte alfa) |
|||||||||
| 8 |
|
N0 1 |
2 | 1/+1000 (corte alfa) |
Ficheiro de Excel, passo a passo:
Inicialmente o valor de alfa/beta é de -1000/+1000. Na expansão do estado 4, este valor é mantido, ainda não há qualquer alternativa, tal como no estado 5. O estado 6 já é gerado, considerando que as pretas têm uma alternativa que é o estado 5, com valor 1. Este valor no entanto não teve nenhuma consequência, dado que o nível de profundidade era baixo, não tendo resultado em cortes.
A expansão do estado 3, já é feita com o conhecimento da expansão do estado 4, onde as brancas podem optar obtendo 1. Portanto o valor de alfa é atualizado para 1. O primeiro estado expandido é o estado 7, que tem o valor -1. Ora como as brancas têm uma alternativa melhor ou igual, que vale 1, seria irrelevante gerar os restantes sucessores, dado que já se sabe ser preferível a opção das brancas pela alternativa. O corte alfa significa não gerar os restantes sucessores, e retorna imediatamente, mas desta vez com o valor -1 e não -2 como na procura exaustiva.
Na expansão do estado 2, o valor de alfa mantêm-se a 1, sendo gerado o estado 8 com o valor igual à melhor alternativa das brancas, o valor 1. Continuar explorando os restantes sucessores seria inconsequente para o valor final a retornar, dado que se as pretas encontrassem um estado melhor (portanto mais baixo), as brancas escolheriam a alternativa, pelo que pode-se dar também o corte alfa, e prescindir da geração dos restantes sucessores. O valor a retornar é neste caso 1.
A estratégia calcula-se da mesma forma, neste caso é 1,4,5, tendo que se ter em atenção que apenas o valor dos primeiros estados com o valor do estado, é que têm o seu valor correcto, os restantes podem ter o valor incorreto devido a cortes. Seria incorreto considerar válida a estratégia: 1,2,8, já que o estado 2 embora tenha o mesmo valor que o estado pai 1, existe um estado irmão expandido/gerado primeiro com o valor igual, que é o estado 4, pelo que o valor do estado 2 pode não ser o correcto. Na realidade sabemos que não é realmente o correcto, do exemplo anterior o valor desse estado seria -1.