Шахматная программа

← →
12 © (2010-08-05 10:03) [0]

Написал таки, но пока на один ход думает :)
Первая игра состоялась вчера с создателем, ходила конем на a6, потом ладьей a8-b8-a8, пока не получила детский мат.
Неплохо для начала.

ТТХ:
на ход (при текущей глубине 1) тратит 260 тиков
На размен идет адекватно, от нападений уходит, от шахов закрывается
система ценностей
пешка - 1000
конь,слон - 3500
ладья - 5000
Ферзь - 9000
Король - 65535

Неоспоримые преимущества позиции, какие?
а то - a8-b8-a8 - интересные ходы, конечно, но много спорно :)
Сегодня еще на ход увеличу, на 2 будет считать
Думаю для начала еще так,
1. каждый потенциальный ход фигуры должен увеличивать ее стоимость на X.
2.каждый потенциальный ход фигуры, если она может убить, должен увеличивать ее стоимость пропорционально той фигуре, которую может убить умножить на X.

зы
хорошая ссылка - это хорошо,
но пересказ своими словами в кол-ве 2х - еще лучше.

← →
12 © (2010-08-05 10:06) [1]

давно еще попалась программка шахматная - играет откровенно слабо, отдаю ферзя и выигрываю все равно.

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

← →
Kerk © (2010-08-05 10:17) [2]

Сделай глубину хотя бы 3 хода :)
Ну и база дебютов обязательно нужна. Хотя бы небольшая.

← →
ocean (2010-08-05 10:23) [3]

> Ну и база дебютов обязательно нужна
+1. Задача нетривиальная, может захватить. Человек учится играть путем опыта. Нужна вообще база позиций, где известно, как надо играть. Заполнять из дебютной энциклопедии и путем самообучения.

← →
12 © (2010-08-05 10:29) [4]

> Сделай глубину хотя бы 3 хода :)

по моим подсчетам, это будет много, надо обрубать ветки будет. Пока не готов
ну, если что, сделаю. Обыграть ту программку надо кровь из носа :)

> Ну и база дебютов обязательно нужна

Согласен, базу на 3 хода думаю сделать

← →
12 © (2010-08-05 11:01) [5]

> Человек учится играть путем опыта

не совсем, скорее учится программировать по-человечески :)
раньше была байка - настоящий программист должен написать тетрис, тектовый редактор,и чего-то там еще

думаю шахматы - все это дело успешно заменят в одном флаконе

← →
Dennis I. Komarov © (2010-08-05 11:16) [6]

> 12 © (05.08.10 11:01) [5]

Это из времени DOSa

← →
Кто б сомневался © (2010-08-05 13:29) [7]

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

← →
Mystic © (2010-08-05 13:50) [8]

Для начала бы изучил теорию. Кстати, твой генератор ходов сколько позиций генерирует в секунду?

← →
12 © (2010-08-05 14:00) [9]

> Для начала бы изучил теорию. Кстати, твой генератор ходов
> сколько позиций генерирует в секунду?

не засекал в таком разрезе

> на ход (при текущей глубине 1) тратит 260 тиков

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

← →
Гость (2010-08-05 14:07) [10]

А скачать где ни будь можно прототип, или пока рано ?

← →
12 © (2010-08-05 14:22) [11]

> скачать где ни будь можно прототип, или пока рано ?

потом Керку в кладовку положу, как закончу
не раньше недели

пока все равно ничего не понятно - ходит в лабель1 как "34-58", например.
Надо рядом на доске дешифровать, и в эдит1 вогнать ответ, например "23-45"

← →
Mystic © (2010-08-05 14:23) [12]

Какое представление доски? Второй вопрос на засыпку. может сразу отобьем охоту начинать ;)

← →
12 © (2010-08-05 14:45) [13]

> Какое представление доски?

TBoard - позиция на доске
рабочая область array [0..7,0..7]
есть array of TFigure

TFigure, имеет X и Y, array of TMove - список возможных ходов(TMove - X,Y)
абстрактный метод GetPossibleMovs, заполняется в потомках array of TMove

Все фигуры произведены от TFigure, со своими GetPossibleMovs

Перебор идет внешним циклом по фигурам, внутренним по возможным ее ходам
После хода получается некая позиция - некий новый TBoard,

← →
Mystic © (2010-08-05 15:41) [14]

Ну это не самое лучшее представление. Не говоря о битбордах (самое быстрое), лучше делать доску массивом размера 0x88 (136 байт). Это упрощает проверку выхода за пределы доски.

← →
12 © (2010-08-05 15:59) [15]

> учше делать доску массивом размера 0x88 (136 байт).

круто..
а как считать ходы?
например, коня в 2d X+-2,Y+-1
ладьи от 0 до X-1, от Х+1 до 7, +тоже самое с Y
и т.п.

>> Это упрощает проверку выхода за пределы доски.
ничего сложного с этим в 2d, и на этом не сэкономишь заметно

← →
Mystic © (2010-08-05 16:16) [16]

Смотри, доска 8x8 как бы подмножество доски 16x16. Смотреть координаты надо в 16-ричном виде. Т. е. $00 это клетка a1, $31 это клетка d2. Вообще, если X это вертикаль, а Y это горизонталь, то берется элемент массива 16 * X + Y.

Далее, список направлений для фигур такой:
ладья +1, +16, -1, -16
слон +15, +17, -15, -17
ферзь +1, +15, + 16, +17, -1, -15, -16, -17
король +1, +15, + 16, +17, -1, -15, -16, -17 (ход короткий)
конь +14, +18, +31, +33, -14, -18, -31, -33 (ход короткий)

Например, для коня прыжок на две клетки вперед и одну влево: +16 + 16 -1 = 32 - 1 = 31.

Далее, выход за пределы доски выполняется одним условием:
(field and $88) <> 0
Если поле на шахматной доске, то это условие выполняется
10001000 это $88 0yyy0xxx это поле на доске

Таким образом получаем такой цикл для ходов:

function DoMoves(Position, From, IsShort, Directions); begin for I := Low(Directions) to High(Directions) do begin Next := From + Directions[I]; repeat if (Next and $88) <> 0 then Break; // Вышли за пределы доски PieceColor := GetPieceColor(Position.Board[Next]); if PieceColor = Position.ActiveSide then Break; // Наша фигура if PieceColor = Position.PassiveSide then // Это фигура противника, берем ее begin AddTaking(From, Next); // Добавляем взятие Break; end; AddMoving(From, Next); // Добавляем простой ход if IsShort then Break; // Короткий ход (конь и король) Next := Next + Directions[I]; until False; end; end; // И для каждой фигуры function KnightMoves(Position, From); begin Result := CommonMoves(Position, From, True, [+14, +18, +31, +33, -14, -18, -31, -33]); end; function BishopMoves(Position, From); begin Result := CommonMoves(Position, From, False, [+15, +17, -15, -17]); end;

В принципе подобный генератор у меня должен жить где-то на JavaScript.

← →
ocean (2010-08-05 16:59) [17]

> Mystic © (05.08.10 16:16) [16]
При условии необходимости постоянного быстрого перебора вариантов это кажется очень привлекательным. Но почему бы не работать с восьмеричными числами?

← →
GanibalLector © (2010-08-05 17:04) [18]

2 Mystic ©

Скажите, как-то Вы показывали исходник шашек. Я хотел поинтересоваться, а обновления есть? Может есть уже шахматы?

← →
Mystic © (2010-08-05 17:05) [19]

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

← →
Mystic © (2010-08-05 17:06) [20]

> GanibalLector © (05.08.10 17:04) [18]

Нет, я этим не занимался. Точнее много читал и понял, что тот исходник можно смело выкинуть на помойку :) Но нового ничего не писал

← →
ocean (2010-08-05 17:16) [21]

> 10001000 это $88> 0yyy0xxx это поле на доске
Дальше идет операция AND для проверки допустимости хода. Какой смысл в старшем бите? Если имеется в виду, что фигура вне доски встанет на 1ууу0ххх, тогда нужно XOR. А что там с отрицательными числами, не могу сообразить.

← →
ocean (2010-08-05 17:18) [22]

> XOR
Не XOR, а искл. И

← →
Mystic © (2010-08-05 17:35) [23]

Смотри, слон находится на поле h4. Это 3 * 16 + 7 = 55. или 00110111. При попытке пойти вверх-вправо (+17) мы получим 72, или 01001000. Т. е. у нас произошло переполнение по вертикалям (из 111 стало 000), по горизонталям все ок (было 011, стало 100). Так вот, бит переполнения не перешел в горизонтали, я появился в третьем разряде. Таким образом, чтобы проверить, а было ли переполнение, нем надо посмотреть, а установлен хотя бы один бит из маски $88

← →
Mystic © (2010-08-05 17:43) [24]

12 не выдержал мучений, спасибо за игру :)

не там пишешь :)
Взаимно!

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

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

Возникает вопрос: какие уголки? Если диагональные 3x3, то там очень много значит теория... А если 3x4, недиагональные, то что делать с запиранием? Плюс симметрия...

> MsGuns © (07.08.10 19:18) [27]
>
> Просто совет - для начала напиши программу "уголки", которая
> бы тебя обыгрывала.

я напишу программу, которая обыграет одну программу
все. Большего мне не надо.

Напишите лучше точки:)

> Напишите лучше точки:)

Тогда уже лучше го :) А точки даже если взять официальные правила, то возникает масса вопросов. Напрмер, первый ход в центр, а потом я просто буду ставить точки с краю и меня не окружишь. Получается ничья?

http://ru.wikipedia.org/wiki/%D0%A2%D0%BE%D1%87%D0%BA%D0%B8_%28%D0%B8%D0%B3%D1%80%D0%B0%29

одну точку отвоюешь)

У меня есть самодельные исходники точек на Delphi (есть даже сохранение истории ходов), но бот на уровне рандома остался.

> точки с краю и меня не окружишь. Получается ничья?

у нас было по территории еще, типа коэффициентов Бухгольца :)
В случае равных окруженцев по кол-ву, кто больше по площади оттяпал - тот и выиграл

> В случае равных окруженцев по кол-ву, кто больше по площади
> оттяпал - тот и выиграл

В принципе, если нет паса, то рано или поздно придется ставить внутрь территории противника, и точка будет автоматически окружаться.

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

Шахматная программа Найти похожие ветки