Опитвам се да внедря оптимална игра на шашки в C.
За да намеря оптималния ход на дъската за проверка, която може да бъде направена от машината, аз генерирах a n-arry дърво на играта използване (GLib) в C въз основа на съвременното състояние на пулта чрез фиксиране на дълбочината.
И, евристична стойност се изчислява за всички листни възли вдървото на играта, което се определя като броя на парчетата от машината, останали в дъската, извадени от броя на парчетата на опонента на играча, тъй като кралете имат по-мощна способност от пешки, евристичният счита всеки крал за две нормални пешки, използвайки които се прилага алфа бета търсене ,
По-вероятно е това увеличаване на дълбочината на дървото на играта най-накрая ще произведе оптимизиран ход, ако се опитам да увелича дълбочината, която отнема много време, за да генерира дървото и да извърша евристичното търсене.
Идеята ми е да генерирайте първото ниво на дървото независимо и разпределете дочерните възли сред наличните процесори за по-нататъшно изпълнение с помощта на MPI?
Възможно ли е? Ако да, как бих могъл да паралелизирам създаването на дървета и евристичното търсене с помощта на MPI?
И ако това не е ефективно, моля, предложете ми някои други начини за това как мога да го прилагам. Благодаря.
Отговори:
0 за отговор № 1Е, може да бъде паралелно, въпросът е,колко подобрение очаквате да получите. Вероятно генерирате синовете на първоначално състояние в цикъл - на първо ниво това може да бъде паралелно, като се раздели създаването на n синове сред k конци. Тъй като тези задачи ще бъдат доста изчислителни (рекурсивно създавайки по-нататъшни подпространства), те трябва да бъдат сравнително ефективни.
Въпреки това, тъй като има вероятност да имате разклонениефактор на дървото, по-голям от броя на ядрата (или подобен), дори ако паралелизацията ви е линейно ефективна (и няма да бъде), ще можете да генерирате само един слой повече.
Използвате ли алфа-бета подрязване? Вярвам, че това би донесло много по-голяма полза от този вид паралелни неща.