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

Требования к номеру позиции следующие:
1) Одно расположение - один номер. т.е. однозначное соответствие
2) Любому расположению фигур должен быть номер (я взял в пределах 6 фигур пока)
3) Номера идут подряд

Итого получилось 1000 различных комбинаций от 2 до 6 фигур, перемножая каждую на кол-во вариантов расстановки (помните о 64*63*...?) посчитано 8971869488 позиций. Диапазон каждого класса, и соответсвующие ему фигуры я внес в БД. Из-за переменного кол-ва фигур, и особенно пешек (у которых уменьшенное кол-во полей), сложно находить по номеру позиции её фигуры, кроме как через БД.

Так-же путем долгих вычислений найдено, что доска симметричная по горизонтали. Благодаря этому можно рассчитывать только половину позиций каждого класса. Т.е. в любом классе все позиции, где первая фигура стоит на клетке >= 32 не используются в расчетах. В дальнейшем, при отображении возможно пригодится давать зеркальным позициям какой-то признак, и отображать в удобном виде.

Немного доработав БД я получил 1002 класс суммарно на 10 + 32*63 + 4485934744 = 4485936770 позиций. Десять позиций первого класса являются служебными. Второй класс отображает позиции голых королей. О них я чуть не забыл среди этих расчетов. Жаль только кол-во позиций не умещается в 32-ух битах (2^32 = 4.3 млрд, а нужно 4.5 млрд), и дружба с длинной арифметикой практически гарантированна.

Служебные номера позиций будут использоваться в полях, для записи лучшего хода за белых и черных соответственно.
0 - невозможная позиция
1 - неанализированная позиция
2 - очевидная ничья
3 - получен пат
4 - получен мат

P.S. На данный момент полностью посчитаны позиции только для 6 фигур, поэтому именно это число взято как базовое. 4.5 миллиарда записей, даже с размером по одному байту уже даст 4.5 Гб. При текущей структуре БД потребовалось бы 14,4 байта на запись, т.е. 65 Гб. Хм, краски начинают сгущатся.

P.S.S. Если не забыть посчитать королей - то выходит уже 7941534749357 позиций (~7.2 ТерраШтук).

Шахматы (ч.3). Расчет позиций
vatolkin
Теперь немного о том, как делать расчеты. Не знаю как делают другие, но имхо лучше найти все матовые позиции, а после искать все позиции из которых можно перейти к ним. Разумеется в любой позиции лучший ход - это ход, которым можно поставить мат. После этого, для каждой позиции, из которой мат следует за 1 ход ищем соседей - это будут позиции из которых противник сможет пойти в такую позицию, при которой получит мат в один ход. Если будет хоть одна позиция, в которой любой ход ведёт к поражению за 1 ход - записываем его как поражение в 2 хода, и из таких позиций (а их будет не много) ищем соседей, т.е. хода за доминирующую сторону, при которых будет победа в два хода (т.е. позиции из которых можно перейти в такое расположение фигур, при котором противник все-равно получит мат следующим ходом). Потом продолжаем аналогично для 3, 4, 5-и ходовых матовых комбинаций. По сути нужно будет продолжать расчеты до тех пор, пока будут находится новые выигрышные комбинации. Пусть даже из позиции Х есть ход, начинающий 100-ходовую победную комбинацию - его нужно внести в БД.

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

Шахматы (ч.2)
vatolkin
Самое сложное в такой системе - хранить информацию, так как ожидается что её действительно будет много.

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

Лучше всего конечно хранить позицию в цифрах, так как последние легко друг с другом комбинировать. Скажем можно записывать положение каждой фигуры с помощью 6 бит (2^6 = 64), после все биты фигур складывать вместе (наподобие конкатенации строк), и записывать в виде единого числа. Единственный недостаток - необходимость изменять размер этого числа в зависимости от кол-ва фигур. Да и выкидывать множество позиций, из-за того что две фигуры не могут располагаться на одной клетке тоже не хочется.

Практически идеальным решением будет записывать фигуры в виде "переменной системы исчисления". Так первая фигура берется как остаток от деления исходной позиции на 64. Потом делим то что осталось на 64, предварительно отняв остаток. Теперь определяем вторую фигуру - для неё берем остаток на 63, само число позиции так-же уменьшаем на этот остаток, и делим на 63. Легко понять, что таким образом можно подставлять любые числа отображающие "степень свободы" фигур, и получить минимальное число, из которого их потом можно "распаковать".

Теперь есть ньюанс с пешками - они не могут находится на многих из клеток доски - на первой и последней горизонтали. Поэтому им будет только 64-8-8 = 48 степеней свободы. Опять-же для простоты их будем учитывать первыми на доске, так как пешка будет отнимать степени свободы у любых других фигур, а вот наоборот - не всегда. Скажем конь в клетке А1 не уменьшает кол-во клеток, на которые можно поставить пешку.

В конечном счете, для записи позиции фигур из двух королей и пешки понадобится число от нуля до:
48*63*62 = 187488

Для позиции ферзя и двух королей - от нуля до:
64*63*62 = 249998

Теперь о нумерации клеток. Лучше будет нумеровать клетки таким образом, чтобы упростить дальнейшие расчеты. Для этого полезно считать не Pos = x*8 + y, а наоборот Pos = y*8 + x, где х и у как и в школе означают горизонтальную и верт. позицию (нумерация от нижнего левого угла). Это поможет легко просчитывать движения пешек, так как ход белой пешки на 1 вперед увеличивает её позицию на 1, а не две клетки - аналогично на 2. У черных будет так-же, но с уменьшением.

Теперь о БД, в ней конечно нам нужно сделать огромную таблицу, в которой по номеру позиции мы будем находить лучший ход в этой ситуации за черных или за белых. Здесь лучший ход можно записать либо как номер позиции, в которую лучше всего перейти с помощью хода черных/белых (да здравствует теория графов!), либо записать ход, которым это следует сделать. В первом случае получим переменную длинну поля (как и номер позиции), и возможность быстро переджойнивать таблицу саму на себя. Во втором - фиксированную длину полей (скажем 64x63 = 12 бит для указания хода). Так-же пригодились бы дополнительные поля, для указания конечного результата, полученного в результате лучших ходов со стороны обеих сторон. При расчетах это будут практически обязательные данные.

Продолжение следует ...

Шахматы (ч.1)
vatolkin
Все началось примерно пол-года назад, когда мой, тогда ещё напарник, мне не рассказал, что кто-то уже расшифровал шахматы. И теперь компьютер может идеально играть в них.

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

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

Как программист - я увидел в этом вызов. 300 ГБ вполне найдется на моём компьютере, и для продолжения расчетов я с удовольствием докуплю дисков. Возможно получится придумать позже и распределенный алгоритм, чтобы не только повторить уже имеющиеся расчеты, но и продвинутся значительно дальше.

(no subject)
vatolkin
Что-то мне не нравится мой блог, пора бы его толком переделать.

Так как работаю я программистом, и люблю всякое разное программить - то логичнее и писать об этом.

В общем, дальше в блоге будут примерно следующие темы:

1) наблюдашки и размышлизмы
2) интересные Веб-технологии (PHP, CSS, JS, Jquery и пр.)
3) оригинальные решения
4) авторские проэкты

По мере наполнения добавлю ссылки на "разделы", и прегруппирую их. Если будут пожелания - добавлю в блог ещё тем.

(no subject)
vatolkin
плоды вечернего стихоплетства по аське на тему зимнего отдыха:

Перед тобой, по стойке строгой
Еще не опробованы дорогой
Немного вытянув носки
Стоят не кто-нибудь - ОНИ

Пусть знаешь ты, сомненья - муки
и из-за дрожи станет не до скуки
но затаи дыханье до поры
и ты несешься на санях с горы!

Винда работает лучше чем wine
vatolkin
Волей судьбы у меня нынче два компа стоят, на втором из которых установлена винда, чтобы играть в игры. Монитор при этом один, так что обычный комп с линуксом выполняет привычную ему роль маршрутизатора (ноутбуки всегда через его AD-HOC wi-fi выходят в мир).

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

Итак, основные причины, почему виндой неудобно пользоваться, когда привыкнешь к линуксу:
1) У винды нет консоли. Нет нет, не называйте виндовый эмулятор доса консолью, прежде чем узнаете о различии. Функционально виндовая консоль от линуксовой отличается как телеграф от сотовой связи.
2) Исходя из п.1 у винды нету таких хороших и привычных команд как whois, dig, mtr, grep, awk. Да, конечно у всего этого можно найти аналоги - но в линуксе это стоит из "коробки", и места на рабочем столе не засирает (как вариант - меню пуск не засирает).
3) У винды основным инструментом управления является мышь. В принципе не слишком критично, так как юзерфрендли линуксы и тоже мышку используют, просто "опционально". Хочешь мышкой - хочешь клавой, только дай компьютеру знать, чего ты от него хочешь.
4) У мышки только две клавиши. Вместо того, чтобы нажать физическую клавишу на клавиатуре - приходится тянутся виртуальным курсором к виртуальной клавише. Как человеку освоившему слепой метод набора мне не нравится тыкать ко клавиатуре одним пальцем, так-же мне почему-то кажется неудобным тыкать по монитору одним курсором, у которого хоть и две клавиши, но все-же. Имхо мышка с клавой помирятся только когда будут 3Д-сканеры жестов, улавливающие движения нескольких пальцев, примерно как в фильме "Особое мнение"
5) Почему ничего само не обновляется, и прораммы сами не устанавливаются? Почему при огромном количестве программеров и хакеров, под винду так и не написали ничего похожего на synaptic?
6) Виндовые проги не комбятся. Т.е. нельзя делать ничего аналогичного sleep 3600; poweroff;

При всем этом, и не смотря ни на что, у винды есть одно преемущество, ради которого я её использую:
Винда работает лучше чем wine :)
Tags: ,

Простейший тест
vatolkin
Не выспался, зато доделал маленький онлайн-тест сегодня ночью.

Кому интересно - заходите на:
http://simpletest.arthost.org.ua

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

Кстати, если есть психологи - помогите написать может быть более развернутые ответы на тест.
Tags: ,

Живопись
vatolkin
Проходил нынче в "неухоженном" подземном переходе на петровке, что и натолкнуло на мысль

Если первобытные люди рисовали наскальные рисунки из религиозных мотивов (например верили что это помогает в охоте), то современники должно быть пишут на стенах слово Х*Й, так как верят что это помогает в поиске сексуальных партнеров. С точки зрения будущих археологов - прямая аналогия :)

У кого какие соображения на этот счет?

regexp-ы
vatolkin
Много лет назад Соломону было сделано кольцо, которое успокаивало его и в ярости и в радости. Для этого понадобилось написать "Все пройдет".

В наши-же времена люди придумали regexp-ы, которые усиливают ярость в тех, кто не умеет их писать, и радуют тех, кто их писать умеет. Похоже времена поменялись...

Вы только посмотрите на этот регэксп. Разве не хочется задушить его автора?
/(0[ \-()]*\d{1}[ \-()]*\d{1}[ \-()]*\d{1}[ \-()]*\d{1}[ \-()]*\d{1}[ \-()]*\d{1}[ \-()]*\d{1}[ \-()]*\d{1}[ \-()]*\d{1})[\., \-()"<]+/m

З.Ы. регэксп выбирает из текста 10-и значные телефоны, начинающиеся с нуля, при этом цифры могут быть перемешаны с пробелами, тире и скобками в любом порядке. Для украинских досок обьявлений "вылавливает" телефоны думаю не менее 97% случаев. Кому пригодится - можете использовать :)
Tags: ,

?

Log in