W jaki sposób silniki szachowe minimax mogą przycinać alfa-beta bez osiągania ostatecznych pozycji?

Question

view on stackexchange narkive permalink

Aby obliczyć daleko do przodu, silniki szachowe minimax muszą wykonywać przycinanie alfa-beta, w którym nie obliczają pozycji, które oczywiście wygrywają lub oczywiście przegrywają. Bez przycinania silniki musiałyby poradzić sobie z ponad miliardem pozycji w pierwszych 4 ruchach / 8 warstwach gry.

Moje pytanie brzmi: w jaki sposób silniki minimax wykonują przycinanie alfa-beta bez oceny końcowych pozycji ? Skąd silnik wie, czy pozycja została całkowicie wygrana / przegrana bez obliczania tak głębokiego, jak to tylko możliwe? Na przykład:

1. e4 e5 2. Sf3 d6 3. Gc4 Gg4 4. Sc3 Sc6 5. h3 Bh5 6. Sxe5 Gxd1

W tym momencie, Dwa ruchy białych od mata. Zakładając, że silnik nie był świadomy obecności partnera prawnego, czy nie zastosowałby przycinania alfa-beta i po prostu przestałby w tym momencie obliczać, zakładając, że pozycja jest wygrana dla czarnych?

Jestem świadomy ciszy wyszukiwanie, w którym silnik nie przestanie obliczać, dopóki pozycja nie zostanie uznana za „cichą”. Na tej pozycji białe są w stanie grać Gxf7 +, a król czarnych jest w niebezpieczeństwie, więc ta pozycja nie kwalifikowałaby się jako spokojna pozycja.

Ale jeśli silnik musi wyszukiwać ciszę za każdym razem, gdy musi podjąć decyzję czy wykonać przycinanie Alpha-Beta i przestać dalej kalkulować, czy to nie pokonuje celu przycinania w pierwszej kolejności? Ponieważ musisz obliczyć z wyprzedzeniem, aby sprawdzić, czy nie musisz obliczać z wyprzedzeniem.

EDYCJA: Istnieją dwie odpowiedzi na to pytanie, które uważam za bardzo przydatne. Spójrz na odpowiedź SmallChess, aby uzyskać informacje na temat problemów z ograniczeniem głębokości obliczeń silników. Zobacz odpowiedź RemcoGerlicha, aby uzyskać doskonały opis tego, czym jest przycinanie Alpha-Beta. Kiedy pisałem to pytanie, tak naprawdę nie wiedziałem, co to jest.

Answer 1

view on stackexchange narkive permalink

Jeśli silnik szachowy nie jest świadomy mata, będzie szczęśliwy, wykonując ruchy jako czarne. Kiedy zobaczy mata, będzie już za późno. Koniec gry. 1-0.

Na szczęście twój scenariusz jest dość prosty. Dobry silnik powinien mieć wystarczającą głębokość, aby zobaczyć mata. Iteracyjny algorytm pogłębiania najpierw głębokości pozwoli na wyszukiwanie z rosnącymi limitami głębokości: d, d + 1, d + 2, d + 3 ... Uważam, że każdy przyzwoity silnik szachowy powinien sobie z tym poradzić, nie jest to bardzo głębokie wyszukiwanie .

Chociaż twój przykład jest prosty, przycinanie powoduje problemy z pozycją taktyczną. Spójrz na artykuł Chessbase:

https://en.chessbase.com/post/houdini5tacticalmode

... Załóżmy, że jest skomplikowana sytuacja, w której po prostu czujesz, że musi być taktyka. Możesz mieć rację, ale czasami nawet potworne silniki mogą na początku to przeoczyć ...

„Tryb taktyczny” to fantastyczne określenie na zastosowanie przycinania pasywnego.

Answer 2

view on stackexchange narkive permalink

Mylisz kilka koncepcji.

Przycinanie alfa-beta

Przycinanie alfa-beta nie jest ”tam, gdzie nie obliczaj pozycji, które oczywiście wygrywają lub przegrywają. ”

To przycinanie gałęzi, gdzie nie ma znaczenia, jaka jest ich ocena, ponieważ kolejny ruch jest już wystarczająco dobry, aby wiedzieć, że ten kierunek nie pracy.

Na przykład pozycja otwarcia. Powiedzmy, że silnik próbuje znaleźć najlepszy ruch startowy i najpierw zbadał 1.d4 (używając dowolnej metody) i stwierdził, że daje +0,15 dla koloru białego.

Teraz zaczyna oceniać 1.e4. Istnieje wiele różnych odpowiedzi. Najpierw próbuje 1 ... e6. To daje +0,2. W porządku. Następnie próbuje 1 ... c5. To daje +0,1.

Ale czekaj! Oznacza to, że czarne mogą zrobić co najmniej +0,1, więc niezależnie od wyniku wszystkich innych możliwych ruchów, 1.e4 musi skończyć gorzej niż 1.d4. Więc inne odpowiedzi na 1.e4 nigdy nie są obliczane.

Ta sztuczka działa również rekurencyjnie głębiej w drzewie. To przycinanie alfa beta. Dla tego samego drzewa przenoszenia znajduje taką samą ocenę, jak normalne wyszukiwanie minimaksów, ale jest szybsze.

Przycinanie

Istnieje również bardziej ogólne przycinanie heurystyczne możliwe porusza się. Heurystyka oznacza, że ​​silnik zgaduje , który ruch prawdopodobnie nie ma znaczenia. To kompromis między możliwością głębszego wyszukiwania a błędnym odgadnięciem od czasu do czasu. Duża różnica w przycinaniu alfa-beta polega na tym, że przycina się tylko gałęzie, które są absolutnie pewne, że nie mają znaczenia, podczas gdy to zgadywanie.

Inne

Reszta Twoje pytanie dotyczy problemu gdzie się zatrzymać - o uśpieniu, efektach horyzontu (ocena zła, ponieważ silnik nie był w stanie spojrzeć wystarczająco głęboko) i tak dalej, ale te są niezwiązane z alfa -beta wyszukiwania. Musisz o tym pomyśleć przy każdej metodzie wyszukiwania.

Answer 3

view on stackexchange narkive permalink

To nie jest odpowiedź, ale przykład pytania:

  [FEN ""] [Wydarzenie "?"] [Witryna "Bled"] [Data "1961"] [Okrągły "? "] [Biały" T. Petrosian "] [czarny" L. Pachman "] [startply" 40 "] 1. Nf3 c5 2. g3 Nc6 3. Bg2 g6 4. OO Bg7 5. d3 e6 6. e4 Nge7 7. Re1 OO 8. e5 d6 9. exd6 Qxd6 10. Nbd2 Qc7 11. Nb3 Nd4 12. Bf4 Qb6 13. Ne5 Nxb3 14. Sc4! Hb5 15. axb3 a5 16. Bd6! Gf6 17. Hf3! Kg7 18. Re4 Rd8 19. Hxf6 +! Kxf6 20. Be5 + Kg5 21. Gg7! *  

W tym przypadku większość komputerów badałaby tylko ruchy wymuszające, a nie rozważałaby „cichego” zwycięskiego ruchu. Ponieważ biały jest materiałem w dół, większość komputerów wyeliminowałaby Bg7 jako przegrywający ruch i podążając za drzewem, odrzuciłaby 19. Hxf6 + !.