Google
 

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

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

Login





 


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

Кто с нами

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


Новая тема   Ответить
Предыдущая тема Версия для печати Войти и проверить личные сообщения Следующая тема
Автор Сообщение
Kallisto
Тема сообщения:   СообщениеОтправлено: Май 09, 2007 - 04:12 AM



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

Сделал библиотеку для доступа к базам Каллисто. Теперь осталось "самое простое" - встроить ее в оболочку и отладить.

В качестве демонстрации работы с базами напишу код для SiDra.
 
 Профиль пользователя отправить личное сообщение Послать e-mail WWW  
Ответить с цитатой Наверх
Kallisto
Тема сообщения:   СообщениеОтправлено: Май 08, 2007 - 10:52 AM



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

NS писал(а):
Медленно, зато очень просто.

Вот это самая большая проблема интерфейсов - неуниверсальность.
Кто-то обязательно был бы недоволен потерей скорости на ровном месте, хоть и копеечным. А так, я надеюсь, что любой будет удовлетворен.
 
 Профиль пользователя отправить личное сообщение Послать e-mail WWW  
Ответить с цитатой Наверх
NS
Тема сообщения:   СообщениеОтправлено: Май 08, 2007 - 10:43 AM



Зарегистрирован: Авг 22, 2006
Сообщений: 671
Откуда : Санкт-Петербург
Игорь, если бы ты сразу сделал поддержку доступа только через массив - то никакого обсуждения бы и не потребовалось Smile

Можно было обойтись только одной функцией.

Медленно, зато очень просто.
 
 Профиль пользователя отправить личное сообщение  
Ответить с цитатой Наверх
Kallisto
Тема сообщения:   СообщениеОтправлено: Май 08, 2007 - 10:39 AM



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

Все, буду делать реализацию вот этого интерфейса:
Код:

struct EdBoard1
{
   // все поля идут по порядку a8, c8, и т.д. до g1
   unsigned char board[32];
};

struct EdBoard2
{
   unsigned char *wman;
   unsigned wman_cnt;

   unsigned char *wkings;
   unsigned wkings_cnt;

   unsigned char *bman;
   unsigned bman_cnt;

   unsigned char *bkings;
   unsigned bkings_cnt;
};

// интерфейсный класс для доступа к эндшпильным базам
struct EdAccess
{
   // возвращаемые значения

   const draw         =      0;
   const win          =  10000;
   const lose         = -10000;
   const db_not_found =  32000;

   // коды для обозначений шашек

   const white = 1;
   const black = 2;
   const empty = 4;
   const king  = 8;

   // флаги для доступа к базе

   const in_mem = 1;


   // загрузить базы
   // пока такие типы игр:
   //       russian
   //       russianlosers
   //       brazil
   //       brazillosers
   //       pool
   //       poollosers
   //       checkers
   //       checkerslosers

   unsigned Load(char *game_type) = 0;


   // получить тип базы

   char *GetBaseType() = 0;


   // оценка позиции (всегда ход белых)

   int GetResult(EdBoard1 *board, unsigned flags) = 0;
   int GetResult(EdBoard2 *board, unsigned flags) = 0;


   // получить указатель на таблицу по материалу

   unsigned GetTable(unsigned wm, unsigned wk, unsigned bm, unsigned bk) = 0;


   // получить указатель на таблицу по материалу и по наиболее продвинутой шашке

   unsigned GetTable(unsigned wm, unsigned wk, unsigned bm, unsigned bk, unsigned rank) = 0;


   // проверка загруженности таблицы целиком в память

   unsigned IsTableInMemory(unsigned table);

   
   // получить индекс в таблице

   unsigned __int64 GetIndex(EdBoard1 *board) = 0;
   unsigned __int64 GetIndex(EdBoard2 *board) = 0;

   
   // получить оценку по указателю на таблицу и индексу

   int GetResult(unsigned table, unsigned __int64 index, unsigned flags) = 0;


};

Если бы вы знали, сколько мне пришлось протратить усилий из-за того, что часто интерфейсы конфликтуют между собой, то не отнеслись бы к обсуждению столь индифферентно Smile
 
 Профиль пользователя отправить личное сообщение Послать e-mail WWW  
Ответить с цитатой Наверх
Kallisto
Тема сообщения:   СообщениеОтправлено: Май 04, 2007 - 04:15 PM



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

На всякий случай приведу слова Мартина Фиерца, когда он генерил 7vs1 базу для поддавков (для крепков он посчитал такие базы излишними):
Цитата:
and my code to compute the binomial coefficient of n and k (I hope that's what it's called in English; it's = n!/(k!*(n-k)!) ) promptly overflowed past the size that a 32-bit integer can hold, and my database builder crashed when computing the 7-1-piece database
 
 Профиль пользователя отправить личное сообщение Послать e-mail WWW  
Ответить с цитатой Наверх
Kallisto
Тема сообщения:   СообщениеОтправлено: Май 04, 2007 - 04:09 PM



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

NS писал(а):
Что лучше - потерять в скорости доступа в 1000 раз, или сделать неполные ЭБ с десятипроцентным наполнением?

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

Kvadrat, я не думаю, что 4х4 намного полезней, чем другие 8-фигурные.
Важно не количество партий проходящих через какую-то конкретную таблицу, а способность этой таблицы настолько отличаться от ОФ, что это будет сказываться на результате партий.
 
 Профиль пользователя отправить личное сообщение Послать e-mail WWW  
Ответить с цитатой Наверх
Kvadrat
Тема сообщения:   СообщениеОтправлено: Май 04, 2007 - 03:59 PM



Зарегистрирован: Дек 16, 2006
Сообщений: 405

У Plus600 безранговая 8-ка = 3.77 Gb
А почему вы не хотите рассмотреть такой класс как 4 на 4 простые? Большинство партий проходит через такое окончание. И в память, вероятно, оно влезет.
 
 Профиль пользователя отправить личное сообщение  
Ответить с цитатой Наверх
NS
Тема сообщения:   СообщениеОтправлено: Май 04, 2007 - 03:54 PM



Зарегистрирован: Авг 22, 2006
Сообщений: 671
Откуда : Санкт-Петербург
С потерей инфы по половине позиций, а если сжать с потерей инфы по 90% позиций? Что лучше - потерять в скорости доступа в 1000 раз, или сделать неполные ЭБ с десятипроцентным наполнением?
Это не утверждение, это вопрос Smile
 
 Профиль пользователя отправить личное сообщение  
Ответить с цитатой Наверх
Kallisto
Тема сообщения:   СообщениеОтправлено: Май 04, 2007 - 03:51 PM



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

NS писал(а):
У Чинука полная 8-ка несколько Гигов, но не факт что они хорошо сжали, и можно использовать неполные ЭБ.

Вот именно, что целиком они не влезут. Вряд ли можно будет существенно улучшить их сжатие. Они сжимали с потерей инфы по половине позиций. И занимались этим не только программисты Чинука. Так что не нужно излишних иллюзий Smile
 
 Профиль пользователя отправить личное сообщение Послать e-mail WWW  
Ответить с цитатой Наверх
NS
Тема сообщения:   СообщениеОтправлено: Май 04, 2007 - 03:47 PM



Зарегистрирован: Авг 22, 2006
Сообщений: 671
Откуда : Санкт-Петербург
У Чинука полная 8-ка несколько Гигов, но не факт что они хорошо сжали, и можно использовать неполные ЭБ.
 
 Профиль пользователя отправить личное сообщение  
Ответить с цитатой Наверх
Kallisto
Тема сообщения:   СообщениеОтправлено: Май 04, 2007 - 03:41 PM



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

booot, так ты займешься генерацией больших баз?

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

Можно поинтересоваться, как с этим справляются чекерсные программисты.

А по интерфейсу замечания есть?
 
 Профиль пользователя отправить личное сообщение Послать e-mail WWW  
Ответить с цитатой Наверх
NS
Тема сообщения:   СообщениеОтправлено: Май 04, 2007 - 03:23 PM



Зарегистрирован: Авг 22, 2006
Сообщений: 671
Откуда : Санкт-Петербург
Цитата:
предположим, что мы уже сгенрили 8-ку и 9-ку

Сгенерили безранговую восьмерку и сжали. После этого считаем влезает ли сжатая восьмерка в память, и получаем что да, влезает Smile
 
 Профиль пользователя отправить личное сообщение  
Ответить с цитатой Наверх
booot
Тема сообщения:   СообщениеОтправлено: Май 04, 2007 - 03:14 PM



Зарегистрирован: Янв 11, 2006
Сообщений: 47

32-битного индекса хватит на все 7-ми фигурные таблицы (и меньше). Начиная с 8-ми фигур количество позиций в классе переваливает за возможности 32-битного числа. Но проблему вижу не в этом. Сгенерить 8-ку, а так же вероятно 9-ку - дело не очень сложной техники, подкрепленной солидной вычислительной мощью современных компьютеров. А вот как ее потом использовать максимально эффективно? Грузить всю таблицу в память можно себе позволить для 6-фигурки. С определенными ограничениями - часть 7-ми фигурки. Но начиная с 8-ми нужно придумывать нечто иное. Какой-то менеджер памяти, который будет по ходу перебора оперативно подгружать в память различные куски различных таблиц, следить за частотой их использования и по каким-то правилам замещать ранее подгруженные куски таблиц новыми. Предлагаю обсуждение общего формата ЭБ начать именно с этого вопроса: предположим, что мы уже сгенрили 8-ку и 9-ку Smile
 
 Профиль пользователя отправить личное сообщение WWW ICQ 
Ответить с цитатой Наверх
Kallisto
Тема сообщения:   СообщениеОтправлено: Май 03, 2007 - 09:42 AM



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

Какое это имеет значение? Все равно индекс тем или иным способом надо расчитывать. Единственно, что движок должен будет учесть, что скорость доступа к сжатой базе меньше. А узнать о сжатости базы он сможет из формата базы.
 
 Профиль пользователя отправить личное сообщение Послать e-mail WWW  
Ответить с цитатой Наверх
NS
Тема сообщения:   СообщениеОтправлено: Май 03, 2007 - 09:34 AM



Зарегистрирован: Авг 22, 2006
Сообщений: 671
Откуда : Санкт-Петербург
Почему это не имеет? Для лучшего сжатия близкие (похожие) позиции размещаются рядом, и должны иметь близкий индекс. Плюс, при неполных базах, например в базах с одинаковым числом шашек у обеих сторон, если храним позиции только с очередью хода стороны с наиболее продвинутой шашкой - вычисление индекса так-же меняется.

И вместо выигрыша в скорости от обращения по индексу получаем падение скорости на пересчет индекса в оболочке.

Или другой пример - в Чинуке таблицы разбивались по степени продвинутости наиболее продвинутой простой - так-же другой расчет индекса.
 
 Профиль пользователя отправить личное сообщение  
Ответить с цитатой Наверх
Показать:     
Перейти к:  
Время в формате GMT + 3
Новая тема   Ответить
Предыдущая тема Версия для печати Войти и проверить личные сообщения Следующая тема
PNphpBB2 © 2003-2007 
 
Page created in 0.762857913971 seconds.