Автор |
Сообщение |
Kallisto |
|
Тема сообщения:
Отправлено: Май 09, 2007 - 06:12 AM
|
|
Зарегистрирован: Авг 18, 2003
Сообщений: 747
|
|
Сделал библиотеку для доступа к базам Каллисто. Теперь осталось "самое простое" - встроить ее в оболочку и отладить.
В качестве демонстрации работы с базами напишу код для SiDra. |
|
|
|
|
|
Kallisto |
|
Тема сообщения:
Отправлено: Май 08, 2007 - 12:52 PM
|
|
Зарегистрирован: Авг 18, 2003
Сообщений: 747
|
|
NS писал(а): Медленно, зато очень просто.
Вот это самая большая проблема интерфейсов - неуниверсальность.
Кто-то обязательно был бы недоволен потерей скорости на ровном месте, хоть и копеечным. А так, я надеюсь, что любой будет удовлетворен. |
|
|
|
|
|
NS |
|
Тема сообщения:
Отправлено: Май 08, 2007 - 12:43 PM
|
|
Зарегистрирован: Авг 22, 2006
Сообщений: 671
Откуда : Санкт-Петербург
|
|
Игорь, если бы ты сразу сделал поддержку доступа только через массив - то никакого обсуждения бы и не потребовалось
Можно было обойтись только одной функцией.
Медленно, зато очень просто. |
|
|
|
|
|
Kallisto |
|
Тема сообщения:
Отправлено: Май 08, 2007 - 12:39 PM
|
|
Зарегистрирован: Авг 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;
};
Если бы вы знали, сколько мне пришлось протратить усилий из-за того, что часто интерфейсы конфликтуют между собой, то не отнеслись бы к обсуждению столь индифферентно |
|
|
|
|
|
Kallisto |
|
Тема сообщения:
Отправлено: Май 04, 2007 - 06: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 |
|
|
|
|
|
Kallisto |
|
Тема сообщения:
Отправлено: Май 04, 2007 - 06:09 PM
|
|
Зарегистрирован: Авг 18, 2003
Сообщений: 747
|
|
NS писал(а): Что лучше - потерять в скорости доступа в 1000 раз, или сделать неполные ЭБ с десятипроцентным наполнением?
На первый взгляд кажется лучшим потерять в скорости доступа
Ведь важен не процент потеряных позиций, а то какие именно позиции мы теряем.
Kvadrat, я не думаю, что 4х4 намного полезней, чем другие 8-фигурные.
Важно не количество партий проходящих через какую-то конкретную таблицу, а способность этой таблицы настолько отличаться от ОФ, что это будет сказываться на результате партий. |
|
|
|
|
|
Kvadrat |
|
Тема сообщения:
Отправлено: Май 04, 2007 - 05:59 PM
|
|
Зарегистрирован: Дек 16, 2006
Сообщений: 405
|
|
У Plus600 безранговая 8-ка = 3.77 Gb
А почему вы не хотите рассмотреть такой класс как 4 на 4 простые? Большинство партий проходит через такое окончание. И в память, вероятно, оно влезет. |
|
|
|
|
|
NS |
|
Тема сообщения:
Отправлено: Май 04, 2007 - 05:54 PM
|
|
Зарегистрирован: Авг 22, 2006
Сообщений: 671
Откуда : Санкт-Петербург
|
|
С потерей инфы по половине позиций, а если сжать с потерей инфы по 90% позиций? Что лучше - потерять в скорости доступа в 1000 раз, или сделать неполные ЭБ с десятипроцентным наполнением?
Это не утверждение, это вопрос |
|
|
|
|
|
Kallisto |
|
Тема сообщения:
Отправлено: Май 04, 2007 - 05:51 PM
|
|
Зарегистрирован: Авг 18, 2003
Сообщений: 747
|
|
NS писал(а): У Чинука полная 8-ка несколько Гигов, но не факт что они хорошо сжали, и можно использовать неполные ЭБ.
Вот именно, что целиком они не влезут. Вряд ли можно будет существенно улучшить их сжатие. Они сжимали с потерей инфы по половине позиций. И занимались этим не только программисты Чинука. Так что не нужно излишних иллюзий |
|
|
|
|
|
NS |
|
Тема сообщения:
Отправлено: Май 04, 2007 - 05:47 PM
|
|
Зарегистрирован: Авг 22, 2006
Сообщений: 671
Откуда : Санкт-Петербург
|
|
У Чинука полная 8-ка несколько Гигов, но не факт что они хорошо сжали, и можно использовать неполные ЭБ. |
|
|
|
|
|
Kallisto |
|
Тема сообщения:
Отправлено: Май 04, 2007 - 05:41 PM
|
|
Зарегистрирован: Авг 18, 2003
Сообщений: 747
|
|
booot, так ты займешься генерацией больших баз?
Я так думаю, что 8-ка не влезет. Проблему можно решать кешированием и использованием доступа к базам, которых нет в памяти, только в узлах достаточно далеких от листьев.
Можно поинтересоваться, как с этим справляются чекерсные программисты.
А по интерфейсу замечания есть? |
|
|
|
|
|
NS |
|
Тема сообщения:
Отправлено: Май 04, 2007 - 05:23 PM
|
|
Зарегистрирован: Авг 22, 2006
Сообщений: 671
Откуда : Санкт-Петербург
|
|
Цитата: предположим, что мы уже сгенрили 8-ку и 9-ку
Сгенерили безранговую восьмерку и сжали. После этого считаем влезает ли сжатая восьмерка в память, и получаем что да, влезает |
|
|
|
|
|
booot |
|
Тема сообщения:
Отправлено: Май 04, 2007 - 05:14 PM
|
|
Зарегистрирован: Янв 11, 2006
Сообщений: 47
|
|
32-битного индекса хватит на все 7-ми фигурные таблицы (и меньше). Начиная с 8-ми фигур количество позиций в классе переваливает за возможности 32-битного числа. Но проблему вижу не в этом. Сгенерить 8-ку, а так же вероятно 9-ку - дело не очень сложной техники, подкрепленной солидной вычислительной мощью современных компьютеров. А вот как ее потом использовать максимально эффективно? Грузить всю таблицу в память можно себе позволить для 6-фигурки. С определенными ограничениями - часть 7-ми фигурки. Но начиная с 8-ми нужно придумывать нечто иное. Какой-то менеджер памяти, который будет по ходу перебора оперативно подгружать в память различные куски различных таблиц, следить за частотой их использования и по каким-то правилам замещать ранее подгруженные куски таблиц новыми. Предлагаю обсуждение общего формата ЭБ начать именно с этого вопроса: предположим, что мы уже сгенрили 8-ку и 9-ку |
|
|
|
|
|
Kallisto |
|
Тема сообщения:
Отправлено: Май 03, 2007 - 11:42 AM
|
|
Зарегистрирован: Авг 18, 2003
Сообщений: 747
|
|
Какое это имеет значение? Все равно индекс тем или иным способом надо расчитывать. Единственно, что движок должен будет учесть, что скорость доступа к сжатой базе меньше. А узнать о сжатости базы он сможет из формата базы. |
|
|
|
|
|
NS |
|
Тема сообщения:
Отправлено: Май 03, 2007 - 11:34 AM
|
|
Зарегистрирован: Авг 22, 2006
Сообщений: 671
Откуда : Санкт-Петербург
|
|
Почему это не имеет? Для лучшего сжатия близкие (похожие) позиции размещаются рядом, и должны иметь близкий индекс. Плюс, при неполных базах, например в базах с одинаковым числом шашек у обеих сторон, если храним позиции только с очередью хода стороны с наиболее продвинутой шашкой - вычисление индекса так-же меняется.
И вместо выигрыша в скорости от обращения по индексу получаем падение скорости на пересчет индекса в оболочке.
Или другой пример - в Чинуке таблицы разбивались по степени продвинутости наиболее продвинутой простой - так-же другой расчет индекса. |
|
|
|
|
|
|