Ścinanie alfa beta w warcabach (przypadki testowe w celu potwierdzenia skuteczności) - algorytm, testcase, przycinanie alfa-beta

Opracowałem zrównoleglone warcaby (angielskiszkice) gra z wykorzystaniem przycinania alfa beta w celu znalezienia optymalnego ruchu, który może wykonać maszyna. Chciałbym wiedzieć, czy zwiększenie głębokości / poziomu drzewa gry i przeszukanie go za pomocą algorytmu przycinającego beta alfa niekoniecznie ewoluuje w najlepszy możliwy sposób?

Biegnę na maszynie niskiego poziomu, a ja niemogę dodać więcej niż 9.Sprawdziłem mój program przy użyciu następujących przypadków testowych, ale mam ten sam możliwy ruch, biorąc pod uwagę głębokość od 1 do 9 w następujący sposób.

case 1
+B+B+B+B
B+B+B+B+
+B+B+B+B
O+O+O+O+
+O+O+O+O
A+A+A+A+
+A+A+A+A
A+A+A+A+           output: (5, 0) => (4, 1)

case 2
+B+B+B+B
O+O+B+B+
+O+O+B+B
O+B+O+O+
+O+O+O+O
A+A+A+O+
+O+O+O+O
O+O+O+O+           output: (5, 2) => (4, 3)

case 3
+O+O+O+O
O+O+O+O+
+B+O+O+O
O+O+O+O+
+B+B+O+O
O+A+A+O+
+O+O+O+O
O+O+A+A+           output: (5, 2) => (3, 4)

case 4
+k+O+O+O
O+B+O+O+
+O+O+O+B
O+O+O+B+
+O+O+B+O
O+O+O+O+
+O+O+O+O
A+A+A+A+           output: (0, 1) => (2, 3)

case 5
+B+B+B+B
O+O+O+O+
+O+O+O+O
O+O+O+O+
+B+B+K+O
O+A+O+O+
+O+O+O+O
A+A+O+A+           output: (5, 2) => (3, 0)

case 6
+k+O+O+O
B+O+O+O+
+O+O+O+O
O+O+O+O+
+O+O+O+O
O+O+O+O+
+O+O+O+O
O+O+O+O+           output: (0, 1) => (1, 2)

gdzie są interpretacje,

O- Empty dark square
+- Empty white square
A- Machine"s pawn
B- Opponent"s pawn
k- Machine"s king
K- Opponent"s king

Obliczyłem heurystyczną wartość dlawęzeł liści drzewa gry jako liczba kawałków Maszynu pozostawionych na planszy, odejmowanych przez liczbę elementów przeciwnika, ponieważ królowie mają większą moc niż pionki, heurystyka liczy każdego króla jako dwa normalne pionki, za pomocą których szuka się alfa-beta stosowany.

Domyślam się, że mój program działa dobrze, ale jest heurystycznywartości obliczone dla węzłów liści drzewa gry ostatecznie się nie zmieniły, ponieważ zwiększam głębokość do 9 (może się to zmienić, jeśli zwiększam głębokość jeszcze bardziej). Czy ktoś może podać mi kilka przypadków testowych, za pomocą których mogę udowodnić wydajność na głębokości 9?

Odpowiedzi:

twoje pytanie jest dość otwarte, ale tutaj kilka wskazówek.

1. Wartość heurystyczna obliczona dla węzłów liścinie zależy od głębokości wyszukiwania, ponieważ są to wierzchołki liści. Zatem twoje "wartości obliczone dla węzłów liści ... nie zmieniły" nie mają większego sensu, może masz na myśli to, że wartość węzła głównego nie uległa zmianie.

2. Normalnie zwiększenie głębokości wyszukiwania prowadzi do lepszych ruchów. Jeśli otrzymasz taki sam "najlepszy" ruch dla wszystkich głębokości wyszukiwania 1..9, to gdzieś jest błąd.

3. Funkcja oceny jest najważniejszafragment rozwiązania do wyszukiwania alfa-beta. Potrzebujesz lepszej funkcji oceny niż ta, która po prostu liczy materiał w uproszczony sposób, szczególnie jeśli nie możesz pozwolić sobie na głębokie wyszukiwanie.

4. Zwykle ludzie nie używają zwykłej alfa-beta, ale takie rzeczy jak wyszukiwanie wariacyjne, iteracyjne pogłębianie, heurystyka typu null-move itd. Zwiększają praktyczną efektywność algorytmu.

5. Skonstruuj własne przypadki testowe, w których wiesz conajlepszym ruchem jest i sprawdź, czy twój algorytm może go znaleźć. Na przykład sytuacje w grach końcowych, w których wiesz, że jeden gracz może wygrać w trzech ruchach.