Угоза мата.

Discussion in 'Машинное отделение' started by NS, 14 Jul 2006.

  1. TopicStarter Overlay

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

    • Заслуженный
    • Ветеран
    • Старожил
    Member Since:
    02.05.2006
    Message Count:
    6.811
    Likes Received:
    96
    Репутация:
    3
    Location:
    Санкт-Петербург
    Оффлайн
    Сделал продление, но угоза мата находится только в nonPV ветвях (так как определяется методом пустого хода, а в PV я его не использую).
    И возникает парадокс - в nonPV ветви программа считает дальше, чем в PV.
    Обычно признак угрозы в Хеш пишут? Или как обходят это недоразумение?
    NS, 14 Jul 2006
    #1
  2. TopicStarter Overlay

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

    • Заслуженный
    • Ветеран
    • Старожил
    Member Since:
    02.05.2006
    Message Count:
    6.811
    Likes Received:
    96
    Репутация:
    3
    Location:
    Санкт-Петербург
    Оффлайн
    Засунул в Хеш, выцепил там всё-таки свободный бит.
    Еще вопрос - почему многие делают продление только на угрозе мата в один ход?
    У меня, ежели продливаю на любой угрозе мата - сильного замедления нет...
    NS, 14 Jul 2006
    #2

  3. WildCat Коршунов Игорь

    • Команда форума
    Member Since:
    04.05.2006
    Message Count:
    3.599
    Likes Received:
    4
    Репутация:
    0
    Location:
    Гомель
    Оффлайн
    У меня любая угроза мата продляется. И в PV тоже, т.к. делаю пустой ход.
    Ты можешь делать в PV пустой ход, но не для отсечения варианта, а только для определения угрозы мата. Это на скорости перебора никак не скажется.
    WildCat, 15 Jul 2006
    #3
  4. TopicStarter Overlay

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

    • Заслуженный
    • Ветеран
    • Старожил
    Member Since:
    02.05.2006
    Message Count:
    6.811
    Likes Received:
    96
    Репутация:
    3
    Location:
    Санкт-Петербург
    Оффлайн
    ОК. Спасибо. в следующей версии попробую добавить метод пустого хода в PV без отсечения.
    То есть добавлю метод пустого хода в PV с маленькой бетой - чтоб только определить угрозу мата.
    NS, 15 Jul 2006
    #4
  5. TopicStarter Overlay

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

    • Заслуженный
    • Ветеран
    • Старожил
    Member Since:
    02.05.2006
    Message Count:
    6.811
    Likes Received:
    96
    Репутация:
    3
    Location:
    Санкт-Петербург
    Оффлайн
    Еще вопрос - как быстрее сортировать?
    Я сделал сортировку шелла в два прохода (h1=4,h2=1) - быстрее массив из 20- 40 элементов (все ходы) наверно ничего не отсортирует?
    NS, 16 Jul 2006
    #5

  6. WildCat Коршунов Игорь

    • Команда форума
    Member Since:
    04.05.2006
    Message Count:
    3.599
    Likes Received:
    4
    Репутация:
    0
    Location:
    Гомель
    Оффлайн
    Почему с маленькой бетой?

    С сортировками надо эксперементировать. У меня все ходы не сортируются. Только когда нужен следующий, выбирается лучший среди оставшихся.
    WildCat, 16 Jul 2006
    #6
  7. TopicStarter Overlay

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

    • Заслуженный
    • Ветеран
    • Старожил
    Member Since:
    02.05.2006
    Message Count:
    6.811
    Likes Received:
    96
    Репутация:
    3
    Location:
    Санкт-Петербург
    Оффлайн
    beta=(-mate+1)
    Search(Mate-1,Mate) =>
    Search(-(-Mate+1),-(-Mate+1)+1) - маленькая бета (или большая - вопрос терминологии) :) Ищем угрозу мата.
    А если сделать Search(-beta,-beta+1) - может не найти мат, так как опровергаться может не только матом, но например и сильным взятием.
    Насчет сортировки - у меня раньше так и было сделано - вытягивались ходы из хеша, потом сортировались только взятия, потом вытягивались киллеры. А потом наверно будет быстрее оставшиеся ходы всё-таки отсортировать...
    И еще одна непонятка -
    Хьят на форуме сказал, что плохие взятия лучше смотреть после хороших ходов...
    Но я не могу понять - как ход QxP может быть хуже просто хода Ферзем???
    NS, 16 Jul 2006
    #7

  8. bankuss Александр

    • Заслуженный
    • Участник
    • Старожил
    Member Since:
    24.05.2006
    Message Count:
    1.084
    Likes Received:
    38
    Репутация:
    6
    Оффлайн
    NS
    смотря какой ход ферзем, например под бой пешки.
    это всяко хуже чем взятие пешки.
    bankuss, 17 Jul 2006
    #8

  9. WinPooh В.М.

    • Команда форума
    Member Since:
    13.02.2006
    Message Count:
    9.492
    Likes Received:
    3.122
    Репутация:
    95
    Location:
    Москва
    Оффлайн
    Встречный вопрос: какой процент времени, по данным профайлера, в функции поиска занимает у тебя сортировка ходов? У меня эта величина колеблется где-то в районе 1-2%. При том, что использую стандартный qsort. Так что даже не знаю, стоит ли пытаться в этом месте оптимизировать, или отложить на потом.
    WinPooh, 17 Jul 2006
    #9

  10. WildCat Коршунов Игорь

    • Команда форума
    Member Since:
    04.05.2006
    Message Count:
    3.599
    Likes Received:
    4
    Репутация:
    0
    Location:
    Гомель
    Оффлайн
    Взятие защищенной пешки ферзем почти всегда очень плохой ход.

    У меня ходы сортируются не в начале, а в процессе просмотра ходов.
    WildCat, 17 Jul 2006
    #10
  11. TopicStarter Overlay

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

    • Заслуженный
    • Ветеран
    • Старожил
    Member Since:
    02.05.2006
    Message Count:
    6.811
    Likes Received:
    96
    Репутация:
    3
    Location:
    Санкт-Петербург
    Оффлайн
    У меня тоже самое. В генераторе сортируются только взятия - но я это тоже вытащу из генератора. Чтоб узнать, что пешка защищена - нужен SEE, а я его еще не написал. :) \Хьят говорит что SEE ускоряет в два раза (по сравненению с MVV/LVA) - это правда?
    NS, 17 Jul 2006
    #11

  12. WildCat Коршунов Игорь

    • Команда форума
    Member Since:
    04.05.2006
    Message Count:
    3.599
    Likes Received:
    4
    Репутация:
    0
    Location:
    Гомель
    Оффлайн
    Когда я сделал SEE, то был очень рад тому насколько он помагает.
    Я с его помощью сортировал ходы + отсекал лишние ходы в ФВ. Мне он прибавляет больше, чем один ply.

    Ты меня второй раз не понял:

    Search(...)
    {
    ...
    GenMoves();
    ScorеMoves(); // - оценки для ходов, будем рассматривать ходы в очередности невозрастания их оценок
    // SortMoves(); - у меня такой функции нет!!!
    ...

    for (по всем ходам)
    {
    GetBestMove(); // - здесь ищется очередной ход, который будем рассматривать
    ...
    }
    ...
    }
    WildCat, 17 Jul 2006
    #12
  13. TopicStarter Overlay

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

    • Заслуженный
    • Ветеран
    • Старожил
    Member Since:
    02.05.2006
    Message Count:
    6.811
    Likes Received:
    96
    Репутация:
    3
    Location:
    Санкт-Петербург
    Оффлайн
    Я понял, Но так медленнее!!!!
    Я говорю о (для случая если в хеше номер хода) -
    Сначала Генератор ходов,
    Потом вытягивание хода из Хеша,
    Потом сортировка взятий (при генерации отдельная запись взятий/ вытягивание взятий в начало - не замедляет быстродействие - но на взятиях как раз сортировка вместо Поиска взятия с большей оценкой наверно ничего не даст) Но это всё для случая, когда плохие взятия смотрим до первого тихого хода.
    Смотрим взятия - после этого очень большая вероятность, что опровергающего хода нет - поэтому просто поиск ходов по убыванию оценки будет медленным (O(n^2)), поэтому можно заполнить массив оценками и вытянуть один сильнейший ход и если он неопровергающий, то уже отсортировать все ходы.
    То есть сортируем сразу после того, как решили что вероятность найти опровергающий ход весьма мала.
    Хотя это наверно уже прибавка долей процента к быстродейтвию :)
    NS, 17 Jul 2006
    #13

  14. WinPooh В.М.

    • Команда форума
    Member Since:
    13.02.2006
    Message Count:
    9.492
    Likes Received:
    3.122
    Репутация:
    95
    Location:
    Москва
    Оффлайн
    SEE имеет смысл делать на верхних уровнях дерева, недалеко от корня - где порядок ходов дороже всего.
    В поиске ФВ вполне можно ограничиться и простым MVV/LVA. Хотя говорят, что от него может быть большая польза при отсечениях в ФВ.
    WinPooh, 17 Jul 2006
    #14
  15. TopicStarter Overlay

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

    • Заслуженный
    • Ветеран
    • Старожил
    Member Since:
    02.05.2006
    Message Count:
    6.811
    Likes Received:
    96
    Репутация:
    3
    Location:
    Санкт-Петербург
    Оффлайн
    Попробую сегодня вечером сделать (я о SEE) - о результатах напишу :)))
    NS, 17 Jul 2006
    #15

  16. WildCat Коршунов Игорь

    • Команда форума
    Member Since:
    04.05.2006
    Message Count:
    3.599
    Likes Received:
    4
    Репутация:
    0
    Location:
    Гомель
    Оффлайн
    Ты хочешь найти пару проценов улучшения в части проги, которая выполняется не больше 2%. В итоге, в лучшем случае, поимеешь десятые процента ускорения. Стоит ли это обсуждать? Алгоритм сортировки значения не имеет (для нашей задачи).

    Вот SEE это уже более интересно.
    WildCat, 17 Jul 2006
    #16
  17. TopicStarter Overlay

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

    • Заслуженный
    • Ветеран
    • Старожил
    Member Since:
    02.05.2006
    Message Count:
    6.811
    Likes Received:
    96
    Репутация:
    3
    Location:
    Санкт-Петербург
    Оффлайн
    Да я уже понял :)
    Если даст ускорение в 2 раза на начальной позиции - тогда выложу новую версию.
    А существуют ли модификации SEE? Или только один, самый простой способ - Запоминяем бои на полях, и при взятии на поле начинаем просматривать отсортированный список взятий?
    Отсекать по SEE в ФВ мне страшно, поэтому пока делать осечение не буду - только сортировка.
    NS, 17 Jul 2006
    #17

  18. WildCat Коршунов Игорь

    • Команда форума
    Member Since:
    04.05.2006
    Message Count:
    3.599
    Likes Received:
    4
    Репутация:
    0
    Location:
    Гомель
    Оффлайн
    А меня хлебом не корми, дай только поотсекать что-нибудь :)

    В SEE сортировать список не нужно. Можно строить таким образом, чтобы он был уже отсортированным. А потом, когда будем добавлять фигуру стоящую за той, которую только что рассматривали, добавляем ее в нужную позицию списка.

    Хотя и здесь необходимость высокоэффективного алгоритма спорна.
    WildCat, 17 Jul 2006
    #18
  19. TopicStarter Overlay

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

    • Заслуженный
    • Ветеран
    • Старожил
    Member Since:
    02.05.2006
    Message Count:
    6.811
    Likes Received:
    96
    Репутация:
    3
    Location:
    Санкт-Петербург
    Оффлайн
    То есть сквозные взятия тоже добавляем....
    А что делать если возникнет отсечение в позиции. где невозможно взятие из-за связанной фигуры? Программа ведь зевнет? или нет?
    NS, 17 Jul 2006
    #19

  20. WildCat Коршунов Игорь

    • Команда форума
    Member Since:
    04.05.2006
    Message Count:
    3.599
    Likes Received:
    4
    Репутация:
    0
    Location:
    Гомель
    Оффлайн
    Зевнет где-то в глубине ветки. При большей глубине перебора уже увидит эту связку.

    Находить в SEE связки для обычной программы очень расточительно. Не так часто они оказываются значимыми. Но если в проге есть данные о связках, то лучше их использовать.
    WildCat, 17 Jul 2006
    #20
  21. TopicStarter Overlay

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

    • Заслуженный
    • Ветеран
    • Старожил
    Member Since:
    02.05.2006
    Message Count:
    6.811
    Likes Received:
    96
    Репутация:
    3
    Location:
    Санкт-Петербург
    Оффлайн
    Я говорю об остечении по SEE в ФВ.
    В вариантах отcечение по SEE это конечно хорошо :)
    А простые ходы (не взятия) по SEE имеет смысл проверять, для сокращения глубины перебора?
    NS, 17 Jul 2006
    #21
  22. TopicStarter Overlay

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

    • Заслуженный
    • Ветеран
    • Старожил
    Member Since:
    02.05.2006
    Message Count:
    6.811
    Likes Received:
    96
    Репутация:
    3
    Location:
    Санкт-Петербург
    Оффлайн
    Еще насчет LMR....
    Повторный перебор (с полной глубиной) идет только если есть превышение по бете...
    А не лучше ли делать повторный перебор и при улучшении лучшей (возвращаемой) оценки?
    Ведь это означает, что предыдущие (несокращаемые) ходы были хуже текущего хода!!!!
    NS, 17 Jul 2006
    #22

  23. WildCat Коршунов Игорь

    • Команда форума
    Member Since:
    04.05.2006
    Message Count:
    3.599
    Likes Received:
    4
    Репутация:
    0
    Location:
    Гомель
    Оффлайн
    Я делаю повторный перебор, если оценка больше альфы. Не понял почему во Фрукте больше беты.

    >Я говорю об остечении по SEE в ФВ.

    Я вроде тоже об этом.

    >В вариантах отcечение по SEE это конечно хорошо smile
    До ФВ? Я такого не имел в виду.

    >А простые ходы (не взятия) по SEE имеет смысл проверять, для сокращения глубины перебора?
    Может быть имеет смысл при оставшейся глубине менее или равной двум. Только тут нет смысла разделять ходы на зятия и простые.
    При большей глубине с сокращением плохих ходов справляется пустой ход. Вряд ли его стоит усиливать, т.к. это уже будет очень опасно.
    WildCat, 17 Jul 2006
    #23
  24. TopicStarter Overlay

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

    • Заслуженный
    • Ветеран
    • Старожил
    Member Since:
    02.05.2006
    Message Count:
    6.811
    Likes Received:
    96
    Репутация:
    3
    Location:
    Санкт-Петербург
    Оффлайн
    У меня же LMR, причем явно работает и прибавляет силы.
    А плохой ход (по SEE) может быть с хорошей историей.
    И его (плохой ход по SEE) можно исключить из подсчета произведенных хороших ходов (у меня изменена схема LMR на просмотр 4 хороших ходов до сокращений), и просматривать после Хороших ходов по истории, и причем с пониженной глубиной.
    //
    У Фрукта LMR используется только в nonPV ветвях (соответственно Альфа практически равна бете, и видимо у него просто небольшая ошибка, но 1 сотая пешки наверно не критично), а я предлагаю делать первый запуск на сокращаемых ходах с окном не (Вета-1,Beta), а (ЛучшаяОценка,ЛучшаяОценка+1) - и если оценка полученная больше лучшей, тогда уже запуск с окном (Альфа, Бета)
    Из-за меньшей верхней границы будет происходить более быстрое отсечение в случае опровержения (а ход обычно будет опровергнут, так как он плохой), плюс вдобавок не будем пропускать хорошие ходы, которые по истории попали в плохие.
    ЗЫ (границы не инвентировал, но идея наверно и так понятна)
    NS, 17 Jul 2006
    #24
  25. TopicStarter Overlay

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

    • Заслуженный
    • Ветеран
    • Старожил
    Member Since:
    02.05.2006
    Message Count:
    6.811
    Likes Received:
    96
    Репутация:
    3
    Location:
    Санкт-Петербург
    Оффлайн
    То есть - делаем сортировку ВСЕХ ходов (включая тихие) по SEE, а внутри этой сортировки, с одинаковым значением по SEE уже сортируем по Истории - так наверно будет более хорошее упорядочивание?
    NS, 17 Jul 2006
    #25

  26. WinPooh В.М.

    • Команда форума
    Member Since:
    13.02.2006
    Message Count:
    9.492
    Likes Received:
    3.122
    Репутация:
    95
    Location:
    Москва
    Оффлайн
    Не зевнёт. Просто стормозит. Совсем чуть-чуть.
    Если, конечно, мы говорим только о сортировке, а не об отсечениях.
    WinPooh, 17 Jul 2006
    #26
  27. TopicStarter Overlay

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

    • Заслуженный
    • Ветеран
    • Старожил
    Member Since:
    02.05.2006
    Message Count:
    6.811
    Likes Received:
    96
    Репутация:
    3
    Location:
    Санкт-Петербург
    Оффлайн
    Не, речь идет об отсечениях по SEE в ФВ.
    NS, 17 Jul 2006
    #27

  28. WildCat Коршунов Игорь

    • Команда форума
    Member Since:
    04.05.2006
    Message Count:
    3.599
    Likes Received:
    4
    Репутация:
    0
    Location:
    Гомель
    Оффлайн
    С идеей сортировать тихие ходы по SEE стоит попробовать. У меня тихие ходы сортируются просто по истории.
    Не могу вспомнить проверял ли я эту идею или нет. Скорее всего проверял, но никаких видимых плюсов не было и я убрал. Может быть вместе с LMR будет работать лучше.

    >а я предлагаю делать первый запуск на сокращаемых ходах с окном не (Вета-1,Beta), а (ЛучшаяОценка,ЛучшаяОценка+1) - и если оценка полученная больше лучшей, тогда уже запуск с окном (Альфа, Бета)

    Не очень понятно. (ЛучшаяОценка,ЛучшаяОценка+1) - такое окно будет отсекать ходы гораздо хуже.
    Вообще, при просмотре всех остальных ходов (кроме первого), должно быть (alpha, alpha + 1), если у нас что-то похожее на PVS.
    Видимо чего-то не понял.
    WildCat, 18 Jul 2006
    #28
  29. TopicStarter Overlay

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

    • Заслуженный
    • Ветеран
    • Старожил
    Member Since:
    02.05.2006
    Message Count:
    6.811
    Likes Received:
    96
    Репутация:
    3
    Location:
    Санкт-Петербург
    Оффлайн
    Это меня сколбасило. Да, действительно будет отсекать медленней. :)
    Так что эта идея (с окном ЛучшаяОценка, ЛучшаяОценка+1) отменяется :)
    NS, 18 Jul 2006
    #29
  30. TopicStarter Overlay

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

    • Заслуженный
    • Ветеран
    • Старожил
    Member Since:
    02.05.2006
    Message Count:
    6.811
    Likes Received:
    96
    Репутация:
    3
    Location:
    Санкт-Петербург
    Оффлайн
    Кстати, у меня есть IID в nonPV ветвях при достаточно большом Depth.
    И при большой глубине улучшения от него есть.
    При достаточно большой глубине можно находить по очереди лучшие ходы, и пытаться перебирать их на полную глубину. После, допустим, четырех таких ходов - очень большая вероятность, что позиция плохая, и все остальные ходы можно перебирать на сокращенную глубину.
    NS, 18 Jul 2006
    #30

Share This Page