Основные принципы генератора ходов (Bitboard и 0x88)

Discussion in 'Машинное отделение' started by Chemer, 30 Nov 2006.

Page 2 of 8
  1. WinPooh
    Оффлайн

    WinPooh В.М. Staff Member

    Репутация:
    95
    Ага, особенно на почти пустой доске с двумя-тремя пешками у каждой стороны :)
     
    WinPooh, 17 May 2007
    #36
  2. NS
    Оффлайн

    NS Нефёдов Сергей баннер

    Репутация:
    3
    Винни, ходы дальнобойных фигур генерируются только при наличии этих фигур на доске, так что при двух-трех пешках у каждой стороны они генерироваться не будут.
     
    NS, 17 May 2007
    #37
  3. ProstoTak
    Оффлайн

    ProstoTak Старожил

    Репутация:
    1


    Пух, можешь смеятся но на этой позиции генератор даёт почти 7 миллионов ходов в секунду :) А в начальной позиции только 4.5 миллиона. Правда я не реализовал пока ещё рокировку.
     
    ProstoTak, 17 May 2007
    #38
  4. WildCat
    Оффлайн

    WildCat Коршунов Игорь Staff Member

    Репутация:
    0
    Ты заметил слово проще? Можешь предложить вариант попроще?

    На самом деле определять шах нужно зависимо от хода последней фигуры. Тогда это очень быстро. Сопоставимо с временем доступа к двумерному массиву.

    Определимть не оставляем ли мы своим ходом короля под шахом сложнее. Там возникает много технических нюансов. Я пока этот момент не оптимизировал. Просто делаем ход, а потом смотрим попали под шах или нет :) Тут тоже используются функции быстрого определения шаха.
     
    WildCat, 17 May 2007
    #39
  5. WildCat
    Оффлайн

    WildCat Коршунов Игорь Staff Member

    Репутация:
    0
    Это правильно. В позициях, где дальнобойные фигуры не блокированы, скорость должна заметно возрастать.
    Кстати, тебе обязательно нужно сделать список фигур. Без него о скорости лучше совсем уж не париться.
     
    WildCat, 17 May 2007
    #40
  6. WildCat
    Оффлайн

    WildCat Коршунов Игорь Staff Member

    Репутация:
    0
    Это правильно. В позициях, где дальнобойные фигуры не блокированы, скорость должна заметно возрастать.
    Кстати, тебе обязательно нужно сделать список фигур. Без него о скорости лучше совсем уж не париться.
     
    WildCat, 17 May 2007
    #41
  7. ProstoTak
    Оффлайн

    ProstoTak Старожил

    Репутация:
    1
    Список фигур - это те что на доске остались? И как его с пользой юзать?
     
    ProstoTak, 17 May 2007
    #42
  8. WinPooh
    Оффлайн

    WinPooh В.М. Staff Member

    Репутация:
    95
    Могу предложить очень много разных определений понятия "проще", на любой вкус :D
     
    WinPooh, 17 May 2007
    #43
  9. WildCat
    Оффлайн

    WildCat Коршунов Игорь Staff Member

    Репутация:
    0
    Что за странные вопросы. Сразу понятно, что быстрее пройтись по списку фигур, чем сканировать всю доску в их поиске.
     
    WildCat, 17 May 2007
    #44
  10. ProstoTak
    Оффлайн

    ProstoTak Старожил

    Репутация:
    1
    А что за странные ответы? Не хочешь не отвечай. Ну посмотри на любую тему на этом форуме. Каждая заканчивается офтопом типа вы все дураки я один умный. Ну может всё таки программеры должны быть не такими казлами как все остальные? Не задумывался над этим?
     
    ProstoTak, 18 May 2007
    #45
  11. NS
    Оффлайн

    NS Нефёдов Сергей баннер

    Репутация:
    3
    Нужно читать выборочно. :) Вот так:
    Что за странные вопросы. Сразу понятно, что быстрее пройтись по списку фигур, чем сканировать всю доску в их поиске.
    Только что при этом происходит с исполнением взятия вражеской пешки?
     
    NS, 18 May 2007
    #46
  12. WildCat
    Оффлайн

    WildCat Коршунов Игорь Staff Member

    Репутация:
    0
    ProstoTak, я тя не понял. Ты спросил - я ответил. Если че не понял - переспроси еще раз.
     
    WildCat, 18 May 2007
    #47
  13. WildCat
    Оффлайн

    WildCat Коршунов Игорь Staff Member

    Репутация:
    0
    А что с ним происходит?
     
    WildCat, 18 May 2007
    #48
  14. NS
    Оффлайн

    NS Нефёдов Сергей баннер

    Репутация:
    3
    Медленно.
    Я когда делал списки тормоза словил, только сейчас вспомнил что не из-за этого.
     
    NS, 18 May 2007
    #49
  15. WildCat
    Оффлайн

    WildCat Коршунов Игорь Staff Member

    Репутация:
    0
    Да нет, все нормально. Тормоза - это когда без списков.

    Списки можно такие - PieceList[цвет][тип][номер]. С ними никаких тормозов.
     
    WildCat, 18 May 2007
    #50
  16. NS
    Оффлайн

    NS Нефёдов Сергей баннер

    Репутация:
    3
    Тормоза я словил на медленном интерпретаторе :)
    Много строк получается на цикл с условием, да и массивы только одномерные в языке. В итоге на 1С Списки тормозят на исполнителе хода.
     
    NS, 18 May 2007
    #51
  17. ProstoTak
    Оффлайн

    ProstoTak Старожил

    Репутация:
    1
    Раз уж зашёл базар про интерпретаторы. На JavaScript генератор ходов никто не делал?
     
    ProstoTak, 18 May 2007
    #52
  18. NS
    Оффлайн

    NS Нефёдов Сергей баннер

    Репутация:
    3
    Я делал на встроенном языке 1С. Но это было давно, и генератор достаточно кривой. В семерке я от списков отказался, в восьмерке сделал на списках. Исходники открыты, но нужно искать в инете где выложен код, у меня исходников не осталось.
     
    NS, 18 May 2007
    #53
  19. WildCat
    Оффлайн

    WildCat Коршунов Игорь Staff Member

    Репутация:
    0
    Одномерность массивов никак помехой быть не может. Но ты конечно выбрал язык - 1С. Какой смысл после этого рассуждать о тормозах :)

    У меня, вроде, никаких сложных циклов с условием нету :)

    Вот функция удаления черной фигуры:
    Code:
    void DeleteBPiece(int type, int sq)
{
    BXOR(type, sq);
    Plist[type][Pole[sq].num] = Plist[type][Plist[type][0]—];
    Pole[Plist[type][Pole[sq].num]].num = Pole[sq].num;
    Material += PieceValue[type];
    if (type != bpawn) BPieces -= piece_value[type];
    TotalPieces--;
}
    У меня вообще почти все функции продублированы и за черных и за белых :)
     
    WildCat, 18 May 2007
    #54
  20. NS
    Оффлайн

    NS Нефёдов Сергей баннер

    Репутация:
    3
    Ты хранишь на поле порядковый номер фигуры в списке?
    А искать в списке при взятии быстрее не будет?
     
    NS, 18 May 2007
    #55
  21. WildCat
    Оффлайн

    WildCat Коршунов Игорь Staff Member

    Репутация:
    0
    Не знаю. Мне так больше нравится.
     
    WildCat, 18 May 2007
    #56
  22. WinPooh
    Оффлайн

    WinPooh В.М. Staff Member

    Репутация:
    95
    Я сейчас пробую написать на классических двусвязных списках, с указателями на предыдущий и последующий элемент для каждого поля.
     
    WinPooh, 18 May 2007
    #57
  23. NS
    Оффлайн

    NS Нефёдов Сергей баннер

    Репутация:
    3
    А это зачем?
    Просто область памяти (массив) с указателем.
    Добавление элемента - увеличили указатель, и записали элемент.
    Удаление - Записали последний элемент на место удаляемого и уменьшили указатель.
     
    NS, 18 May 2007
    #58
  24. WinPooh
    Оффлайн

    WinPooh В.М. Staff Member

    Репутация:
    95
    Надо ещё как-то уметь быстро находить удаляемый элемент. Сняли пешку с E2 - как будем искать элемент в середине отдельного массива-списка? Перебирать все подряд?

    У меня примерно так:

    Code:
    struct Sq
{
   PIECE piece;
   Sq* pnext;
   Sq* pprev;
};

struct Position
{
   Sq base[14];
   Sq board[65];
};
    В массиве base хранятся указатели на начала списков для каждой фигуры.
     
    WinPooh, 18 May 2007
    #59
  25. NS
    Оффлайн

    NS Нефёдов Сергей баннер

    Репутация:
    3
    Теперь понял :)
     
    NS, 18 May 2007
    #60
  26. ProstoTak
    Оффлайн

    ProstoTak Старожил

    Репутация:
    1
    Провёл кое какую оптимизацию. Скорость увеличилась на 4-5%. Это стоящая оптимизация или не стоило и возиться? Вообще какое мнение у программерского народа на этот счёт? Какой прирость в процентах считается существенным?
     
    ProstoTak, 18 May 2007
    #61
  27. NS
    Оффлайн

    NS Нефёдов Сергей баннер

    Репутация:
    3
    В 2 раза 70 пунктов, в 1.05 раза это 5 пунктов Эло прибавки силы.
    Но ускоряя например на 50% генератор ходов получишь общей прибавки производительности только 10-15%. Так что это пустая трата времени.
     
    NS, 18 May 2007
    #62
  28. ProstoTak
    Оффлайн

    ProstoTak Старожил

    Репутация:
    1
    Ну в данном конкретном случае переделка программы заняла минут 10, так что не такие уж и затраты. :) Но спасибо конечно за популярное обьяснение. Особенно про 50% и 10-15%.
     
    ProstoTak, 18 May 2007
    #63
  29. WildCat
    Оффлайн

    WildCat Коршунов Игорь Staff Member

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

    Нужно профайлером померять сколько времени тратится на генератор ходов, а потом уже решать стоит ли думать о его оптимизации.
     
    WildCat, 18 May 2007
    #64
  30. ProstoTak
    Оффлайн

    ProstoTak Старожил

    Репутация:
    1
    Я в своих первобытных движках для теста на скорость оценочную функцию сводил к выдаче просто случайного числа. Таким образом всё затраты времени ложились на генератор и перебор. Но даже при этом результаты были катострофические. Что-то типа 6 полуходв за 3 минуты удавалось прокопать. Наверное дело не только в генераторе, но то что это не пустяк я точно знаю.
     
    ProstoTak, 18 May 2007
    #65
  31. NS
    Оффлайн

    NS Нефёдов Сергей баннер

    Репутация:
    3
    Минимаксом чтоли перебираешь?
     
    NS, 18 May 2007
    #66
  32. ProstoTak
    Оффлайн

    ProstoTak Старожил

    Репутация:
    1
    Ну тогда да. Сейчас пока до перебора не дошёл. Хочу всё таки генератор сначала лучший в мире :) забацать.
     
    ProstoTak, 18 May 2007
    #67
  33. WildCat
    Оффлайн

    WildCat Коршунов Игорь Staff Member

    Репутация:
    0
    На какой машине? Crafty на Атлоне 2200 мГ нужно около полуминуты (если правильно помню). Так что твой результат не очень плох. А моей проге секунд 15.
     
    WildCat, 18 May 2007
    #68
  34. NS
    Оффлайн

    NS Нефёдов Сергей баннер

    Репутация:
    3
    У тебя генератор/исполнитель в два раза быстрее чем у Крафти?
     
    NS, 18 May 2007
    #69
  35. WildCat
    Оффлайн

    WildCat Коршунов Игорь Staff Member

    Репутация:
    0
    Ну это же на 32-битной машине :)
     
    WildCat, 18 May 2007
    #70
Page 2 of 8