7-men EGTB Bounty - Приз за создание 7-фигурного генератора

Тема в разделе "Машинное отделение", создана пользователем Kirr, 18 апр 2011.

  1. Skipper_NORTON Учаcтник

    • Участник
    Рег.:
    14.12.2007
    Сообщения:
    512
    Симпатии:
    1
    Репутация:
    0
    Оффлайн
    SSD - будущее. И по цене они в будущем станут дешевле
  2. MS Михаил Семионенков

    • Команда форума
    Рег.:
    10.02.2006
    Сообщения:
    5.808
    Симпатии:
    1.435
    Репутация:
    118
    Оффлайн
    Ну, лет 10 для больших объёмов винты не смогут заменить. А включить в архитектуру SSD для кэша - святое дело прямо сегодня.
  3. Skipper_NORTON Учаcтник

    • Участник
    Рег.:
    14.12.2007
    Сообщения:
    512
    Симпатии:
    1
    Репутация:
    0
    Оффлайн
    "SSD сумасшествие продолжается...." так начинается одна статья.

    Скорость чтения и записи самых быстрых SSD дисков достигает 740 Мегабайт в секунду!! Это что-то невероятное... SSD винчестеры почти полностью "забивают" интерфейс SATA-3.

    Для сравнения: скорость чтения у обычных HDD-винчестеров, достигает 70 мегабайт в секунду. Т.е. SSD винчестеры позволяют читать и писать на них в 10 раз быстрее!

    А скорость рандомного доступа - 0,1 миллисекунды, т.е. по этому параметру, SSD-винчестеры быстрее чем HDD в 100 раз!!

    По емкости они НЕНАМНОГО уступают HDD - самые объемные HDD сейчас 3 терабайта, а SSD - почти 1 терабайт. (960 ГБ).


    Раньше отставание было намного больше. Т.е. очевидно, что SSD скоро обойдут HDD по всем показателям. И HDD уйдут в историю.

    А если поставить 5 таких SSD-винчестеров, в один компьютер, то получим суммарную скорость чтения или записи
    740 * 5 = 3,7 Гигабайта в секунду! Т.е. в оперативную память будет заливаться с дисков по 3,7 гигабайта в секунду. Больше SSD винчестеров подключать уже нет смысла, если их юзать "по полной" - т.к. мы "упремся" уже в скорость шины, и пропускную способность PCI (до 4 гигабайт в секунду).

    Если запустить мой генератор на таком SSD-винчестере, самом быстром и продвинутом, то суммарно скорость расчета может возрасти ~ в 10 раз по сравнению с HDD. А если в один комп поставить 5 таких SSD-винчестеров, и на каждом запустить мой генератор, то можем получить 50-кратное увеличение общей производительности. (я уже не рискну тут какие то прогнозы точно делать, но видимо, хотя генератор сейчас упирается именно в скорости чтения в HDD, будет в будущем упираться в производительность самого мощного процессора, как собственно, и должно быть)

    Очевидно, что SSD - это пока лучшее что мы имеем. RAID из 5-ти таких SSD-винчестеров даст нам чтение файлов со скоростью до 3,7 гигабайта в секунду! Это можно прочитать за 1 секунду сразу несколько фильмов.
  4. Skipper_NORTON Учаcтник

    • Участник
    Рег.:
    14.12.2007
    Сообщения:
    512
    Симпатии:
    1
    Репутация:
    0
    Оффлайн
    Еще в апреле читал, что вышли SSD-винчестеры со скоростью линейного чтения 550 мегабайт/сек.
  5. MS Михаил Семионенков

    • Команда форума
    Рег.:
    10.02.2006
    Сообщения:
    5.808
    Симпатии:
    1.435
    Репутация:
    118
    Оффлайн
    Правильно ли я понимаю, что один комп с 8Г памяти 1Т "флэш" построит таблицы лет за 5?
  6. Skipper_NORTON Учаcтник

    • Участник
    Рег.:
    14.12.2007
    Сообщения:
    512
    Симпатии:
    1
    Репутация:
    0
    Оффлайн
    Нет, чтобы построить все 7-фигурные за 3-5 лет, нужно распараллеливать вычисления. Просто одновременно запускать много генераторов, чтобы каждый строил что-то свое. Памяти каждый будет кушать в среднем 5 ГБ, и всего потребуется на N компьютерах по M винчестерах на каждом, N*M запущенных одновременно генераторов, и
    N*M* 5 ГБ оперативной памяти в сумме.
    Насколько нужно распараллеливать (сколько одновременно запускать генераторов), чтобы посчитать за 5 лет, я точно не знаю.
  7. Killster Учаcтник

    • Участник
    Рег.:
    12.05.2011
    Сообщения:
    75
    Симпатии:
    0
    Репутация:
    0
    Оффлайн
    Только стоит винт на 3 тб 4000 рублей, а SSD на терабайт - 80000

    P.S. Хотя за границей есть вот такой монстр: http://www.newegg.com/Product/Product.aspx?Item=N82E16820227724

    Если будете покупать - не забудьте про доставку - она в этом магазине достаточно дорогая. :whistling:
  8. Skipper_NORTON Учаcтник

    • Участник
    Рег.:
    14.12.2007
    Сообщения:
    512
    Симпатии:
    1
    Репутация:
    0
    Оффлайн
    NS, поделитесь секретом, как вы ВООБЩЕ достигаете 20 полуходов в глубину? И как получается у вас бранчинг-фактор около двух? Такой фактор не получится, даже при идеальном альфа-бета, при самой точной сортировке ходов (если ВСЕГДА будем угадывать лучший ход из каждого узла). Мой Фритц 8 достигал в глубину 17 полуходов, судя по выводимой информации, со стандартным контролем времени (в средних позициях. имеется в виду не форсированный поиск с одними взятиями и т.д., а по основному у него было 17).

    Может, вы не всё считаете, и у вас какие то мудрёные способы для определения веток, которые можно ВООБЩЕ не считать? Хотел бы найти где нибудь хотя бы одно внятное описание алгоритмов хоть одной программы (на словах), за счет чего им удалось добиться, чтобы бранчинг фактор стал равен двум. Если есть ссылки на инфу, напишите, плиз. Я написал хороший анализатор эндшпилей, а вот в обычной шахматной программе пока не достиг больших высот, т.к. мало по времени этим занимался. :)
  9. NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    Рег.:
    02.05.2006
    Сообщения:
    6.743
    Симпатии:
    32
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    Skipper_NORTON, у всех такой бренчинг Фактор. В шашках у меня около полутора, в шахматах даже у Анечки около двух. Алгоритмы везде описаны - в шахматах это хорошие сортировки, Null Move, LMR - этого достаточно чтоб получить бренчинг фактор меньше двух.
  10. NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    Рег.:
    02.05.2006
    Сообщения:
    6.743
    Симпатии:
    32
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    У Всех естественно современных сильных программ. Во время Фрица восьмого LMR еще не было, Null Move был не настолько продвинут, и сортируют сейчас лучше чем тогда.
  11. Skipper_NORTON Учаcтник

    • Участник
    Рег.:
    14.12.2007
    Сообщения:
    512
    Симпатии:
    1
    Репутация:
    0
    Оффлайн
    Посоветуйте что-нибудь, самое лучшее.

    хорошие сортировки, Null Move - недостаточно, чтобы получить бренчинг фактор меньше двух.
  12. Skipper_NORTON Учаcтник

    • Участник
    Рег.:
    14.12.2007
    Сообщения:
    512
    Симпатии:
    1
    Репутация:
    0
    Оффлайн
    Хорошие сортировки - всего лишь оптимизируют чистый альфа-бета, и даже при самой лучшей оптимизации - там бренчинг-фактор должен быть равен примерно 6 (корень квадратный из 36 - среднее количество ходов в позиции, и бренчинг-фактор, который был бы при полном переборе, без альфа-бета).

    Значит, с помощью альфа-бета и наилучшей сортировке - удасться добиться чтобы бренчинг фактор был равен 6. Null Move - позволит за то же время, рассчитать на 1 полуход глубже, в лучшем случае, но опять же, не должен стать причиной бренчинг-фактора равного двум. Бренчинг-фактор равен двум, может быть достигнут, только если вы многие ветки ВООБЩЕ считать не будете, на основании каких-то данных.
  13. NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    Рег.:
    02.05.2006
    Сообщения:
    6.743
    Симпатии:
    32
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    Хеш, хорошие сортировки, Null Move, LMR - других алгоритмов влияющих на бренчинг фактор нет в современных шахматных программах. И этого достаточно чтоб он стал меньше двух, даже не смотря на то что есть продления.

    Без пустого хода и LMR бренчинг фактор меньше шести, вы забываете про Кеш перекрестных позиций.
    Пустой ход дает выигрыш конечно больше чем один полуход, ибо это СЕЛЕКТИВНЫЙ метод. Так же как и LMR.
    Пустой ход дает выигрыш в глубине примерно в полтора раза, остальное добивает LMR.
  14. Skipper_NORTON Учаcтник

    • Участник
    Рег.:
    14.12.2007
    Сообщения:
    512
    Симпатии:
    1
    Репутация:
    0
    Оффлайн
    Возьмем идеальное дерево перебора, имеющее в каждом узле 36 потомков. Если ничего не отсекается, кроме того, что должно отсекаться при чистом альфа-бета, посчитайте сколько позиций вы вынуждены будете перебрать чтобы посчитать на глубину 20 полуходов? Точно такое же, как если бы вы перебирали полным перебором, без альфа-бета отсечений, на глубину 10 полуходов. Это же известный факт, что идеальный альфа-бета позволяет увеличить глубину ровно в 2 раза. Это количество позиций равно 36 в 10-й степени.
    Точнее, 3 656 158 440 062 976. 3 квадриллиона. Это идеальный альфа-бета, с лучшей сортировкой ходов и бренчинг-фактором, равным 6.

    Теперь посчитаем. сколько позиций вы переберете до глубины 20 полуходов, с бренчинг-фактором равным двум.
    2 в степени 20.
    Это примерно 1 миллион позиций, точнее, 1 048 576.

    Теперь разделим 1 048 576 на 3 656 158 440 062 976.

    И получим, что вы считаете всего лишь 0,00000002 % позиций.
    А НЕ СЧИТАТЕ 99,99999998 % позиций, которые следовало бы считать, исходя из ЧИСТОГО альфа-бета, с самой оптимальной сортировкой ходов.

    И неужели, из этих пропущенных, необсчитанных, 99,99999998 % позиций - не найдутся те, в которых было бы что-то важное?

    Вот какую часть позиций вы считаете, когда говорите, что "просчитали на глубину 20 полуходов". Эти 20 полуходов - чистая фикция.
  15. NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    Рег.:
    02.05.2006
    Сообщения:
    6.743
    Симпатии:
    32
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    Skipper_NORTON, вы специально рубите свой проект на корню, демонстрируя полное непонимание современных шахматных алгоритмов?
  16. Skipper_NORTON Учаcтник

    • Участник
    Рег.:
    14.12.2007
    Сообщения:
    512
    Симпатии:
    1
    Репутация:
    0
    Оффлайн
    NS, что я не правильно написал? Я вам привел среднее количество позиций, которые вы должны просчитать полным перебором, с одними только альфа-бета отсечениями. Где-то похожая тема уже была, и все согласились, что то что пишут программы, что якобы они просчитали "на 20 полуходов", это фикция - движки не считают там подавляющее большинство позиций, просто отсекая их. Чистый альфа-бета выдает результат, такой же, какой был бы при полном переборе, а вот отсечение веток, вообще не считая их, может привести к ошибке, т.е. движок просто не видит какой то комбинации, которая БЛИЖЕ той глубины, которую он пишет, что якобы посчитал.
  17. NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    Рег.:
    02.05.2006
    Сообщения:
    6.743
    Симпатии:
    32
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    Даже расчет процента позиций - глупость. Через бренчинг фактор можно рссчитать число "действительных, нормальных ходов в среднем" рассматриваемый современными шахматными программами. Это около четырех (бренчинг-фактор 2, но у нас альфа-бета), но это не значит что мы рассматриваем в каждой позиции только четыре хода, это значит что "плохие" ветви рассматриваются на меньшую глубину. И вы опять забываете про перекрестные позиции.
  18. Skipper_NORTON Учаcтник

    • Участник
    Рег.:
    14.12.2007
    Сообщения:
    512
    Симпатии:
    1
    Репутация:
    0
    Оффлайн
    Когда вы не можете привести конкретно предложение, что я неправильно написал - вам остается только демонстрировать полное непонимание того, что хочет сказать собеседник.

    Еще раз. Я понимаю, что вы рассматриваете не все ходы, а только 4, которые вам кажутся хорошими, но в любом случае, такое поведение может привести к ошибке, т.е. могут быть отсечены варианты, которые как раз сильно изменили бы оценку. И я сам видел тому примеры у сильнейших программ. Вот что я и хочу донести.
  19. NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    Рег.:
    02.05.2006
    Сообщения:
    6.743
    Симпатии:
    32
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    Глубина современных программ, если не считать отсечений в конце (которые не влияют на бренчинг-фактор) - это практически "честная" глубина, то есть сила примерно такая-же, которой бы достигли программы без сокращений считающие на ту-же глубину. Ибо большинство сокращений происходят после откровенной отдачи материала либо бессмысленных ходов.
  20. NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    Рег.:
    02.05.2006
    Сообщения:
    6.743
    Симпатии:
    32
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    Мы сейчас рассуждаем не о возможных ошибках в результате сокращений, а о том что ЭБ в памяти позволяют обращаться к ним на значительно большей глубине без потери в скорости перебора.
  21. Skipper_NORTON Учаcтник

    • Участник
    Рег.:
    14.12.2007
    Сообщения:
    512
    Симпатии:
    1
    Репутация:
    0
    Оффлайн
    Согласен. Но часто в жизни бывают крутые комбинации, с жертвой ферзя и т.д. фигур, которые программе покажутся бессмысленными, и она сократит поиск, и ведь эта жертва может привести к результату гораздо позже.

    Потому я и спросил у вас - есть конкретно. полное описание лучших алгоритмов - что они отсекают?
    Т.е. четкие принципы, критерии, правила.
  22. NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    Рег.:
    02.05.2006
    Сообщения:
    6.743
    Симпатии:
    32
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    Я же вам сказал - сортировки, NullMove, LMR.
  23. Skipper_NORTON Учаcтник

    • Участник
    Рег.:
    14.12.2007
    Сообщения:
    512
    Симпатии:
    1
    Репутация:
    0
    Оффлайн
    сортировки и NullMove были известны задолго до того, как был достигнут бренчинг-фактор равный двум. Значит, только LMR так сильно повлиял?
  24. Skipper_NORTON Учаcтник

    • Участник
    Рег.:
    14.12.2007
    Сообщения:
    512
    Симпатии:
    1
    Репутация:
    0
    Оффлайн
    Я занимался ретроанализом, и оптимизациями, связанными с аппаратным уровнем, кэширование данных и т.д.
    С альфа-бета, NullMove и т.д. я работал мало. У меня пока не было цели написать программу, играющую на гроссмейстерском уровне, а для моего генератора эндшпильных баз - LMR не нужен. :)
  25. Skipper_NORTON Учаcтник

    • Участник
    Рег.:
    14.12.2007
    Сообщения:
    512
    Симпатии:
    1
    Репутация:
    0
    Оффлайн
    Кстати, чисто по человечески - если в каждой позиции из 36 ходов, в среднем только 4 заслуживают рассмотрения, а остальные можно ненамного углубившись, отсечь - то дерево перебора до глубины 20, действительно, на 99,999... %
    состоит из всякого бреда, который можно и не считать.
    И что я не неправильно сказал?
    Чистая математика.
  26. NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    Рег.:
    02.05.2006
    Сообщения:
    6.743
    Симпатии:
    32
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    NullMove широко известен с 93-94 года, и на нем был достигнут Бренчинг-фактор около трех, трех с небольшим в 94-ом году (Гениус 3, Фриц 3), и с улучшением ОФ и сортировок его эффективность питихоньку улучшалась. LMR позволил уменьшить бренчинг-фактор до двух и меньше.
  27. NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    Рег.:
    02.05.2006
    Сообщения:
    6.743
    Симпатии:
    32
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    Да, дерево перебора практически на 100% состоит из мусора. Если не применять отсечений и сокращений.
    "Не так" вы сказали выше - например про пустой ход который дает выигрыш в один полуход, и про то что NullMove и LMR не могут дать бренчинг-фактор меньше двух.
  28. NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    Рег.:
    02.05.2006
    Сообщения:
    6.743
    Симпатии:
    32
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    NullMove - селективный метод - мы пропускаем ход, даем сопернику сделать второй ход подряд, и если после этого перебором на сокращенную глубину мы получаем отсечку по бете - значит в позиции у соперника нет угроз, и мы можем сразу сделать отсечку, либо после перебора на еще более сокращенную глубину (верификация) - чтоб убедиться что в позиции нет цуцванга.

    LMR - метод основанный на хороших сортировках и статистике ходов.
    Если после первых ходов из списка не получилось отсечь по бете, то на остальных ходах (нетактических ходах с плохой статистикой) мы сокращаем глубину перебора. Тоже возможна верификация - если нас не отсекли по альфе, то считаем на полную глубину.
  29. Skipper_NORTON Учаcтник

    • Участник
    Рег.:
    14.12.2007
    Сообщения:
    512
    Симпатии:
    1
    Репутация:
    0
    Оффлайн
    А вот и нет. Я писал, что NullMove и сортировка (обычная, для альфа-бета) не могут дать бренчинг-фактор меньше двух. Вы еще и невнимательно читаете, как оказывается. Про LMR я не писал.

    Я попросил - дайте ссылки на точную информацию, что именно ОТСЕКАЕТСЯ, т.е. какие бессмысленные варианты - что служит поводом не рассматривать какую то ветку а быстро отсечь ее? Ну скажем ферзь взял пешку, и вскоре его побили и т.п. Вы же в ответ только пару слов говорите, и гугли, рассматривая сотни страниц пока что-то найдешь. Если у вас есть подробная информация, то можно ссылочку?
  30. miptus Заслуженный

    • Заслуженный
    • Участник
    Рег.:
    11.02.2006
    Сообщения:
    1.159
    Симпатии:
    72
    Репутация:
    4
    Оффлайн
    Про LMR на английском можно здесь: http://www.glaurungchess.com/lmr.html
  31. Skipper_NORTON Учаcтник

    • Участник
    Рег.:
    14.12.2007
    Сообщения:
    512
    Симпатии:
    1
    Репутация:
    0
    Оффлайн
    miptus

    Ну это уже поподробнее... Спасибо. Но хотелось бы еще более подробно. С четкими критериями. На много страниц. Это лучше, чем самому изобретать то, что уже изобретено (велосипед), и добиваться того, чего добилось все человечество за 40 лет развития шахматных алгоритмов. :) Человечество не догнать, если не изучать то, что достигнуто. Слишком неравные силы. :)
  32. WinPooh В.М.

    • Команда форума
    Рег.:
    13.02.2006
    Сообщения:
    8.097
    Симпатии:
    1.486
    Репутация:
    56
    Адрес:
    Москва
    Онлайн
    В случае LMR - не отсекается, а сокращается. Почувствуйте разницу.

    Отсекается: ход плохой -> вместо того, чтобы считать на 10 полуходов, не считаем его совсем.
    Сокращается: ход плохой -> вместо того, чтобы считать на 10 полуходов, считаем его на 9.

    Даже если что-то и пропустили, на следующей итерации этот ход будет просчитан на 10 полуходов (а другие, может быть - на 11).
  33. Skipper_NORTON Учаcтник

    • Участник
    Рег.:
    14.12.2007
    Сообщения:
    512
    Симпатии:
    1
    Репутация:
    0
    Оффлайн
    Я могу конечно и сам перегуглить весь интернет, изучить сотни страниц, чтобы найти то, что возможно, некоторые программисты и так знают - что вот это - лучшее описание. Поэтому и прошу ссылку с подробной информацией.
  34. WinPooh В.М.

    • Команда форума
    Рег.:
    13.02.2006
    Сообщения:
    8.097
    Симпатии:
    1.486
    Репутация:
    56
    Адрес:
    Москва
    Онлайн
    О сокращениях LMR можно думать как о "зеркальном" продлении - мы делаем продление во всех ходах, кроме данного.
    Очевидно, никаких "отсечений" при этом не происходит. Если я раздал всем своим друзьям, кроме одного, по 100 рублей - это не значит, что я у этого одного 100 рублей отнял :)
  35. Skipper_NORTON Учаcтник

    • Участник
    Рег.:
    14.12.2007
    Сообщения:
    512
    Симпатии:
    1
    Репутация:
    0
    Оффлайн
    Это я все знаю... Сам сокращал :) Критерии нужны. Точные. И такие чтобы программа не могла например, что то пропустить, (скажем комбинацию с жертвой ферзя).

Поделиться этой страницей