Алфа бета резитба в пулове (тестови случаи, за да се докаже ефективността) - алгоритъм, testcase, алфа-бета-резитба

Разработих паралелизирани пулове (английскис помощта на алфа бета резитба, за да се намери оптималното движение, което може да бъде направено от машината. Бих искал да знам дали увеличаването на дълбочината / нивото на дървото на играта и търсенето му с помощта на алфа бета резитба алгоритъм непременно развива най-добрия възможен ход?

Тичам на машина с ниско ниво и аз не съмможе да добавите дълбочина над 9.Аз проверих програмата си, като използвам следните тестови случаи, но ще получа еднакво възможно движение, като се има предвид дълбочината от 1 до 9, както следва.

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)

където тълкуванията са,

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

Изчислих евристичната стойност закато броят на парчетата на Машината, останали в дъската, извадени от броя на парчетата на играча на Опонента, тъй като царете имат по-мощни способности от пешки, евристиката преброява всеки крал като две нормални пешки, използвайки алфа бета търсенето. прилага.

Предполагам, че програмата ми работи добре, но е евристичностойностите, изчислени за листовите възли на играта дърво в крайна сметка не се промени, тъй като аз увеличаване на дълбочината до 9 (може да се промени, ако аз увеличаване на дълбочина още повече). Може ли някой да ми предостави някои тест случаи, с които мога да докажа ефективността в дълбочина 9?

Отговори:

вашият въпрос е доста отворен, но тук има няколко съвета.

1. Еуристичната стойност, изчислена за листовите възлине зависи от дълбочината на търсене, защото те са листови възли. Така че вашият коментар "стойностите, изчислени за листовите възли ... не се променят", няма много смисъл. Може би имате предвид, че стойността за коренния възел не се е променила.

2. Обикновено увеличаването на дълбочината на търсене води до по-добри ходове. Ако получите еднакво "най-добро" движение за всички дълбочини за търсене 1..9, тогава някъде има грешка.

3. Функцията за оценка е най-важнатачаст от алфа-бета решение за търсене. Нуждаете се от по-добра функция за оценяване от тази, която просто брои материала по опростен начин, особено ако не можете да си позволите дълбоко търсене.

4. Обикновено хората не използват обикновен алфа-бета, но неща като търсене на основни вариации, итеративно задълбочаване, нулево движение евристично и т.н., за да се увеличи практическата ефективност на алгоритъма.

5. Изградете собствени тестови касети, където знаете каквонай-добрият ход всъщност е и проверете дали алгоритъмът ви може да го намерите. Например ситуации в края на играта, където знаете, че един играч може да спечели в три хода.