Отправляет email-рассылки с помощью сервиса Sendsay

Как сделать популярный сайт.

Рассылка закрыта

При закрытии подписчики были переданы в рассылку "Бизнес и карьера в интернете" на которую и рекомендуем вам подписаться.

Вы можете найти рассылки сходной тематики в Каталоге рассылок.

←   Октябрь 2012   →
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
Автор
Елена Иванова

Статистика

11.093 подписчиков
+1 за неделю
←   Все выпуски   →

Как сделать популярный сайт. ~~~~~ Алгоритмы шахматной игры ~~~~~


Добрый день,
уважаемые читатели рассылки
"Как сделать популярный сайт"
Выпуск 198.
~~~~~ Алгоритмы шахматной игры ~~~~~
Внимание! Если ваша почтовая программа не отображает корректно рисунки или тексты, то
Нажмите здесь :: http://kocby.ru/post/webmaster/text/issue198.html



Алгоритмы шахматной игры.

Если Вы не популярны,
Значит, Вас как бы и не существует...


Сделано в kocby.ru
Сегодня слегка копнем в сторону специализированного шахматного софта, проблем его создания, адаптации, алгоритмов шахматной игры и пр. Наш отечественный подход под влиянием Михаила Ботвинника больше тяготел к созданию программы, похожей на работу реального человеческого мозга. Это было очень интересно, но и очень трудно. Попробуйте создать алгоритм, как думает человек, хотя бы в самом общем виде! Очень трудная задача. Американцы пошли более простым путем под ярким названием "brute force" ("грубая сила"), здесь алгоритм простой и ясный, как 2*2=4. Описание данного алгоритма в общем виде. Предлагаю рассмотреть Chess Titans (Шахматные Титаны). Этот шахматный движок компании Oberon Games очень популярен благодаря тому, что включен компанией Microsoft в набор стандартных игр Windows 7. Приглашение к сотрудничеству: давайте, сделаем собственный онлайновый шахматный движок.
© Перепечатка разрешается с установкой ссылки на ресурс http://kocby.ru/.


Уважаемые коллеги!

В нашем последнем выпуске...

Как сделать популярный шахматный сайт. :: http://kocby.ru/post/webmaster/text/issue197.html

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

Сегодня слегка копнем в сторону специализированного шахматного софта, проблем его создания, адаптации, алгоритмов шахматной игры и пр.

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

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

Американцы пошли более простым путем под ярким названием "brute force" ("грубая сила"), здесь алгоритм простой и ясный, как 2*2=4, сейчас я вам его опишу в общем виде.

1
Берем текущую позицию (например, начальную, неважно) и даем ей некую числовую оценку, допустим от -1000 (мат белому королю) до +1000 (мат черному королю).
Если имеет место быть мат или другой случай явного завершения игры (например, пат, тогда оценка 0, т.е. ничья), то все расчеты завершаются. Если нет, подбиваем некий баланс.
Считаем силу белых. Есть ферзь (королева)? Плюсуем 10 очков. Есть пара ладьей? Даем за каждую по 5 очков. Одна ладья занимает открытую линию? Даем ей премию 1 очко. За коня даем 3 очка. Он прижат к краю? Штрафуем, например, минус 0.5. За каждую пешку даем по очку, а за перспективную пешку (например, которая дошла до предпоследней линии) еще премию.
Таким же образом, учитывая и материальную силу и особенности позиции, считаем силу черных, а затем вычитаем из силы белых силу черных и получаем некое число.

2
Теперь, если ход белых, делаем выборку всех легальных возможных ходов (в начальной позиции их, например, 20, а, вообще, среднее значение, где-то около сорока). Пробуем каждый код и делаем оценку также, как в п.1.

3
Теперь, на каждый ход белых, которые мы подобрали в п.2, подбираем все возможные ответы черных, и делаем оценку позиции также, как в п.1. Если я не ошибся, то таких оценок пока мы должны получить 400 штук (для начальной позиции, т.е. 20 возможных ходов белых, на каждый есть 20 ответов черных, 20*20=примерно 400).

4
Для бешенной собаки 100 верст - не крюк, для современного персонального компьютера рассчитать 400 чисел по шагам 1-3 выше, есть пустяк. Но! Шаги 1-3 надо повторить хотя бы раз 10 и количество чисел растет в геометрической прогрессии. И тут важнейший фактор - быстродействие компьютера и наличие объемной оперативной памяти с быстрым доступом, хотя, конечно, качество оценки позиции тоже имеет большое значение.

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

Чтобы стало совсем понятно, представим, как такая программа сделает первый шаг для начальной позиции. Она выбирает все возможные ходы и отсортирует их в порядке от лучшего до худшего. В скобках укажем оценку позиции до совершения хода и после совершения хода. Коня я обозначаю буквой N, как это принято "у них".

(+0.21)e2-e4(+0.29)
(+0.21)d2-d4(+0.27)
(+0.21)Ng1-f3(+0.25)
(+0.21)c2-c4(+0.22)
(+0.21)b2-b4(+0.12)
(+0.21)g2-g3(+0.11)
(+0.21)b2-b3(+0.10)
(+0.21)e2-e3(+0.08)
(+0.21)d2-d3(+0.07)
(+0.21)a2-a3(+0.05)
(+0.21)c2-c3(+0.04)
(+0.21)h2-h3(+0.02)
(+0.21)h2-h4(-0.02)
(+0.21)a2-a4(-0.03)
(+0.21)f2-f4(-0.04)
(+0.21)Nb1-c3(-0.05)
(+0.21)f2-f3(-0.08)
(+0.21)Nb1-a3(-0.12)
(+0.21)Ng1-h3(-0.14)
(+0.21)g2-g4(-0.16)

Если вы читаете внимательно, то, наверное, у вас возник вопрос: как же в начальной позиции перед первым ходом можно получить оценку отличную от нуля (в нашем примере +0.21), если белые и черные фигуры и пешки находятся в абсолютно одинаковом положении? Тут не все так просто. Очередность хода тоже имеет некоторый вес (иногда очень большой, иногда маленький), вот этот вес и сказался.

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

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

Теперь, для развлечения и научного эксперимента, представим, что за белых играет программа с условным названием "мазохист" (т.е. делает максимально плохие ходы), а за черных программа с условным названием "всегда лучший ход" (т.е. всегда выбирает наилучший ход).

Получаем в результате стыковки двух указанных выше программ такую вот партию из двух ходов.

1. {(+0.21)} g4 {(-0.16)} e5
2. {(-0.55)} f4 {(-1000.00)} Qh4#

Кстати, это партия есть абсолютный рекорд по краткости, а возможно и по красоте.

Разработок шахматных движков по алгоритму выше сделано уже много разными компаниями.

Предлагаю рассмотреть Chess Titans (Шахматные Титаны). Этот шахматный движок компании Oberon Games очень популярен благодаря тому, что включен компанией Microsoft в набор стандартных игр Windows Vista и Windows 7.
Chess Titans (Шахматные Титаны), шахматный движок включен компанией Microsoft в набор стандартных игр для Windows 7

Реализована система из десяти уровней сложности игрока-компьютера. Первый уровень сложности, по мнению обозревателя от ресурса Genius Prophecy Chess, предназначен для новичков, десятый может оказаться сложным даже для лучших игроков.

Протестируем этот движок на практике, естественно, на самом мощном десятом уровне, чтобы убедиться, что он сложный даже для меня ;-)
Протестируем Chess Titans (Шахматные Титаны) на самом мощном десятом уровне.

Выбираем черные фигуры, чтобы дать Титанам преимущество первого хода. Отключаем графические ненужные эффекты, чтобы ресурсы компьютера не тратились на всякую ерунду, а сам компьютер подбираем весьма мощный (по меркам 2012-го года).
Компьютер для тестовой шахматной игры с Титанами подбираем весьма мощный (по меркам 2012-го года).

Обратите внимание, что такие критичные для качественной шахматной игры параметры как скорость процессора и быстрота доступа к памяти близки к идеальным. Добавлю, что используется Windows 7, 64-х разрядная с 4г памяти.

Сразу сильно разочаровало, что Титаны не ведут протокол партии. Это, конечно, серьезная недоработка. Сейчас уже устаканился стандарт PGN, и все шахматные движки, вьюверы, онлайновые платформы для игры между людьми и пр. должны использовать автоматическое ведение протокола партии в формате PGN (прошу не путать с графическими файлами PNG, я сам все время путаю).

Должен сказать, что моему возмущению по поводу отсутствия протокола игры не было предела. Мало того, что я долго терплю ужасный и непонятный факт: в стандарт Виндов не входит двухпанельный навигатор типа Total Commander, Norton Commander или Far! Так теперь еще новый удар - шахматный движок без протокола! Как это понять? Солидная компания и такие ляпы.

Ладно, я не гордый. Я могу и вручную вести протокол. Это несложно. PGN - это есть текстовый файл с несложными тегами, понять его гораздо проще, чем HTML или XML.

Вот что он собой представляет в данном конкретном случае:


Данный текст можно смотреть в любом шахматном вьювере, например, в моем:
http://usa2017.com/chess/viewer/
Скопируйте текст в окошке выше, затем вставьте в поле "Content of the PGN file" и нажмите длинную кнопку "Show the game"

Таким же образом можно посмотреть любую шахматную партию, записанную в формате PGN.

Мы поступим еще проще. Тестовую партию с Титанами посмотрим прямо на этой страничке (при условии, если вы разрешаете вашему браузеру юзать фреймы).

Во время игры я боялся, что сделаю грубую ошибку, что-то зевну. Обычно программы играют тупо, но аккуратно, грубых ошибок не прощают и сами, обычно, явно не ошибаются. В отличие от программ, человек играет интересно, но зато часто ошибается. Поэтому, многие любят играть именно с людьми, это интереснее, больше эмоций и т.д.

С большой неохотой я сделал 6... Qb6 - этот ход требовала позиция, но разменять ферзей, значит, резко уменьшить шансы на победу, а ничью я не хотел.

После 22-го хода позиция была у меня чуть лучше, как мне кажется, я бы ее оценил как (-0.30). Тут вдруг подарок судьбы, странный ход Титанов 23. a4?

Мне кажется, что удалось вскрыть фундаментальный дефект программы. Она знает о правиле "взятие на проходе", но при оценке позиции почему-то его не учитывает!

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

Еще заметил странную любовь Титанов давать шахи, неважно, полезные или бесполезные. Очевидно, при оценке позиции значимость шаха была переоценена.

Основной вывод. Конечно, на таком мощном компьютере, на самом сложном уровне я ожидал более высокого качества игры.

Во время тестирования Титанов появилась идея. Давайте, совместными усилиями сделаем собственный шахматный движок. Я - эксперт и постановщик, вы - кодировщик. Код открытый (GNU), в результате получим на выходе некий онлайновый сервис. Используем языки: PHP (серверный), JavaScript (на рабочей станции) можно со стандартными библиотеками типа jQuery. Ну и MySQL, понятное дело.

Требования следующие. Готовность работать за бесплатно, на чистом энтузиазме. Хорошие знания указанных языков, опыт программирования. В шахматы должны уметь играть, но плохо. Два хороших шахматиста в одной команде - слишком много, драка будет. Но шахматные правила должны знать, тем более они совсем простые.

Что это вам даст? Хороший интересный реализованный проект в вашем портфолио может найти хорошую работу в компаниях типа Microsoft, Google и пр. Шахматы - это вещь серьезная, популярная и уважаемая. Это не стрелялка и не пыхтелка какая-ниюудь.

Есть интерес, пишите, обсудим все детали подробнее.

Вот, кажется, и все.

Спасибо за внимание.

~~~~~ Обратная связь ~~~~~

У вас есть два способа реагирования на данный выпуск.

На форуме...

"Как сделать популярный сайт" на форуме :: http://kocby.ru/b/viewforum.php?f=5

Написать лично мне.

Данные для связи на контактной страничке :: http://kocby.ru/contact.html

Ниже дан мой работающий емейл, но доставка через форму на указанном урле надежнее, ее вероятность является почти 100%.
::::::::::::::::::::::::
::: Vladimir Abramov :::
::: va@sumat.ru ::::::::
::: http://sumat.ru/ :::
::::::::::::::::::::::::

### Конец выпуска.

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Информационная безопасность YII - высокопроизводительный веб фреймворк на PHP. Как сделать популярный сайт. Думаем. Пробуем. Критикуем. Анализируем. Уроки Фотошопа онлайн Функция getJSON. Теория и пример использования.
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~


В избранное