Google
 

Сайт Андрея Иванова

Андрей Иванов - все секреты шашек и шашистов

Login





 


 Забыли пароль?
 или новый пользователь? Зарегистрируйся!

Кто с нами

Пользователей:  На сайте
Пользователей:  Пользователей: 0
Гостей:  Гостей: 1
Всего:  Всего: 1
Пользователей:  Зарегистрированные
No members connected


Новая тема   Ответить
Предыдущая тема Версия для печати Войти и проверить личные сообщения Следующая тема
Автор Сообщение
Kallisto
Тема сообщения: Re: Стандартная проверка корректности генератора ходов  СообщениеОтправлено: Авг 23, 2006 - 11:10 PM



Зарегистрирован: Авг 18, 2003
Сообщений: 747

Аврора считает, что дамкой a1 можно сбить простые b2 и g7 4-мя способами.

NS писал(а):
AlexanderS писал(а):
Kallisto писал(а):
10 - 22450628

хмм... у меня - 22 450 647 Confused

Похоже что одинаковые взятия, но при разном порядке снятия шашек с доски - считаются за действительно разные взятия...

Это у всех так.
 
 Профиль пользователя отправить личное сообщение Послать e-mail WWW  
Ответить с цитатой Наверх
NS
Тема сообщения: Re: Стандартная проверка корректности генератора ходов  СообщениеОтправлено: Авг 23, 2006 - 09:08 PM



Зарегистрирован: Авг 22, 2006
Сообщений: 671
Откуда : Санкт-Петербург
AlexanderS писал(а):
Kallisto писал(а):
10 - 22450628

хмм... у меня - 22 450 647 Confused

Похоже что одинаковые взятия, но при разном порядке снятия шашек с доски - считаются за действительно разные взятия...
 
 Профиль пользователя отправить личное сообщение  
Ответить с цитатой Наверх
AlexanderS
Тема сообщения:   СообщениеОтправлено: Май 26, 2006 - 04:28 PM



Зарегистрирован: Авг 29, 2002
Сообщений: 845
Откуда : Якутск
Kallisto писал(а):
А остальные совпадают?

До 10 совпадают, дальше у меня записей нет
 
 Профиль пользователя отправить личное сообщение WWW ICQ 
Ответить с цитатой Наверх
Kallisto
Тема сообщения:   СообщениеОтправлено: Май 26, 2006 - 06:55 AM



Зарегистрирован: Авг 18, 2003
Сообщений: 747

А остальные совпадают?

Можно в качестве тестовой использовать какую-либо специальную позицию, в которой проявляются все тонкости шашечных правил.

Но по-моему и начальной вполне достаточно.
 
 Профиль пользователя отправить личное сообщение Послать e-mail WWW  
Ответить с цитатой Наверх
AlexanderS
Тема сообщения: Re: Стандартная проверка корректности генератора ходов  СообщениеОтправлено: Май 25, 2006 - 10:44 PM



Зарегистрирован: Авг 29, 2002
Сообщений: 845
Откуда : Якутск
Kallisto писал(а):
10 - 22450628

хмм... у меня - 22 450 647 Confused
 
 Профиль пользователя отправить личное сообщение WWW ICQ 
Ответить с цитатой Наверх
AlexanderS
Тема сообщения: Re: Стандартная проверка корректности генератора ходов  СообщениеОтправлено: Май 25, 2006 - 10:41 PM



Зарегистрирован: Авг 29, 2002
Сообщений: 845
Откуда : Якутск
где-то сохранял эти данные, не могу найти

думается при такой постановке в шашки проблемы в генераторе вряд ли обнаружатся - основная их часть скорее всего будет при множественных дамочных взятиях, в частности - турецкий удар, а на глубине 14 вряд ли много таких позиций встретится.
 
 Профиль пользователя отправить личное сообщение WWW ICQ 
Ответить с цитатой Наверх
Kallisto
Тема сообщения: Стандартная проверка корректности генератора ходов  СообщениеОтправлено: Май 25, 2006 - 06:07 PM



Зарегистрирован: Авг 18, 2003
Сообщений: 747

В шахматном программировании есть одна методика проверки корректности генератора ходов, называемая Perft. Организуется полный перебор всех ходов, и подсчитывается число позиций на разных ярусах дерева перебора. Все корректные генераторы ходов должны выдавать одинаковые числа.

Вот эти числа для шашек, посчитанные Каллисто:

1 - 7
2 - 49
3 - 302
4 - 1469
5 - 7482
6 - 37986
7 - 190146
8 - 929905
9 - 4570667
10 - 22450628
11 - 110961169
12 - 545059387
13 - 2675994747
14 - 13138899366

Хотелось бы сверится с другими программами (может у меня еще остались ошибки в генераторе?). Организовать подсчет позиций для определенной глубины перебора очень легко. Вот примерный код на Си:

Код:


double PerftNodes = 0; // количество позиций может переполнить целочисленные переменные

void Perft(int depth)
{
   Move moves[MAX_MOVES_CNT]; // массив для хранения ходов

   int cnt = GenerateMoves(); // генерация ходов

   if (depth == 1)
   {
      // достигли нужной глубины
      // теперь можно посчитать позиции не делая ходов
      PerftNodes += cnt;
      return;
   }
   depth--;
   for (int i = 0; i < cnt; i++) {
      MakeMove(moves[i]);
      Perft(depth);
      UnmakeMove(moves[i]);
   }
}


Если интересно, вот числа для чекерса:

1 - 7
2 - 49
3 - 302
4 - 1469
5 - 7361
6 - 36768
7 - 179740
8 - 845931
9 - 3963680
10 - 18391564
11 - 85242128
12 - 388623673
13 - 1766623630
14 - 7978439499
 
 Профиль пользователя отправить личное сообщение Послать e-mail WWW  
Ответить с цитатой Наверх
Показать:     
Перейти к:  
Время в формате GMT + 3
Новая тема   Ответить
Предыдущая тема Версия для печати Войти и проверить личные сообщения Следующая тема
PNphpBB2 © 2003-2007 
 
Page created in 0.91049909591675 seconds.