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

SSD - будущее. И по цене они в будущем станут дешевле

"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 секунду сразу несколько фильмов.

Еще в апреле читал, что вышли SSD-винчестеры со скоростью линейного чтения 550 мегабайт/сек.

Нет, чтобы построить все 7-фигурные за 3-5 лет, нужно распараллеливать вычисления. Просто одновременно запускать много генераторов, чтобы каждый строил что-то свое. Памяти каждый будет кушать в среднем 5 ГБ, и всего потребуется на N компьютерах по M винчестерах на каждом, N*M запущенных одновременно генераторов, и
N*M* 5 ГБ оперативной памяти в сумме.
Насколько нужно распараллеливать (сколько одновременно запускать генераторов), чтобы посчитать за 5 лет, я точно не знаю.

Только стоит винт на 3 тб 4000 рублей, а SSD на терабайт - 80000

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

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

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

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

Skipper_NORTON, у всех такой бренчинг Фактор. В шашках у меня около полутора, в шахматах даже у Анечки около двух. Алгоритмы везде описаны - в шахматах это хорошие сортировки, Null Move, LMR - этого достаточно чтоб получить бренчинг фактор меньше двух.

У Всех естественно современных сильных программ. Во время Фрица восьмого LMR еще не было, Null Move был не настолько продвинут, и сортируют сейчас лучше чем тогда.

Посоветуйте что-нибудь, самое лучшее.

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

Хорошие сортировки - всего лишь оптимизируют чистый альфа-бета, и даже при самой лучшей оптимизации - там бренчинг-фактор должен быть равен примерно 6 (корень квадратный из 36 - среднее количество ходов в позиции, и бренчинг-фактор, который был бы при полном переборе, без альфа-бета).

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

Хеш, хорошие сортировки, Null Move, LMR - других алгоритмов влияющих на бренчинг фактор нет в современных шахматных программах. И этого достаточно чтоб он стал меньше двух, даже не смотря на то что есть продления.

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

Возьмем идеальное дерево перебора, имеющее в каждом узле 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 полуходов - чистая фикция.

Skipper_NORTON, вы специально рубите свой проект на корню, демонстрируя полное непонимание современных шахматных алгоритмов?

NS, что я не правильно написал? Я вам привел среднее количество позиций, которые вы должны просчитать полным перебором, с одними только альфа-бета отсечениями. Где-то похожая тема уже была, и все согласились, что то что пишут программы, что якобы они просчитали "на 20 полуходов", это фикция - движки не считают там подавляющее большинство позиций, просто отсекая их. Чистый альфа-бета выдает результат, такой же, какой был бы при полном переборе, а вот отсечение веток, вообще не считая их, может привести к ошибке, т.е. движок просто не видит какой то комбинации, которая БЛИЖЕ той глубины, которую он пишет, что якобы посчитал.

Даже расчет процента позиций - глупость. Через бренчинг фактор можно рссчитать число "действительных, нормальных ходов в среднем" рассматриваемый современными шахматными программами. Это около четырех (бренчинг-фактор 2, но у нас альфа-бета), но это не значит что мы рассматриваем в каждой позиции только четыре хода, это значит что "плохие" ветви рассматриваются на меньшую глубину. И вы опять забываете про перекрестные позиции.

Когда вы не можете привести конкретно предложение, что я неправильно написал - вам остается только демонстрировать полное непонимание того, что хочет сказать собеседник.

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

Глубина современных программ, если не считать отсечений в конце (которые не влияют на бренчинг-фактор) - это практически "честная" глубина, то есть сила примерно такая-же, которой бы достигли программы без сокращений считающие на ту-же глубину. Ибо большинство сокращений происходят после откровенной отдачи материала либо бессмысленных ходов.

Мы сейчас рассуждаем не о возможных ошибках в результате сокращений, а о том что ЭБ в памяти позволяют обращаться к ним на значительно большей глубине без потери в скорости перебора.

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

Потому я и спросил у вас - есть конкретно. полное описание лучших алгоритмов - что они отсекают?
Т.е. четкие принципы, критерии, правила.

Я же вам сказал - сортировки, NullMove, LMR.

сортировки и NullMove были известны задолго до того, как был достигнут бренчинг-фактор равный двум. Значит, только LMR так сильно повлиял?

Я занимался ретроанализом, и оптимизациями, связанными с аппаратным уровнем, кэширование данных и т.д.
С альфа-бета, NullMove и т.д. я работал мало. У меня пока не было цели написать программу, играющую на гроссмейстерском уровне, а для моего генератора эндшпильных баз - LMR не нужен.

Кстати, чисто по человечески - если в каждой позиции из 36 ходов, в среднем только 4 заслуживают рассмотрения, а остальные можно ненамного углубившись, отсечь - то дерево перебора до глубины 20, действительно, на 99,999... %
состоит из всякого бреда, который можно и не считать.
И что я не неправильно сказал?
Чистая математика.

NullMove широко известен с 93-94 года, и на нем был достигнут Бренчинг-фактор около трех, трех с небольшим в 94-ом году (Гениус 3, Фриц 3), и с улучшением ОФ и сортировок его эффективность питихоньку улучшалась. LMR позволил уменьшить бренчинг-фактор до двух и меньше.

Да, дерево перебора практически на 100% состоит из мусора. Если не применять отсечений и сокращений.
"Не так" вы сказали выше - например про пустой ход который дает выигрыш в один полуход, и про то что NullMove и LMR не могут дать бренчинг-фактор меньше двух.

NullMove - селективный метод - мы пропускаем ход, даем сопернику сделать второй ход подряд, и если после этого перебором на сокращенную глубину мы получаем отсечку по бете - значит в позиции у соперника нет угроз, и мы можем сразу сделать отсечку, либо после перебора на еще более сокращенную глубину (верификация) - чтоб убедиться что в позиции нет цуцванга.

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

А вот и нет. Я писал, что NullMove и сортировка (обычная, для альфа-бета) не могут дать бренчинг-фактор меньше двух. Вы еще и невнимательно читаете, как оказывается. Про LMR я не писал.

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

Про LMR на английском можно здесь: http://www.glaurungchess.com/lmr.html

miptus

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

Я могу конечно и сам перегуглить весь интернет, изучить сотни страниц, чтобы найти то, что возможно, некоторые программисты и так знают - что вот это - лучшее описание. Поэтому и прошу ссылку с подробной информацией.

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