Пытаюсь реализовать метод альфа бета отсчечений в игре Реверси
возникло несколько вопросов:
1) Какие лучеше всего значения поставить под alpha и beta?
Понятно что alpha < beta то есть присваиваю
alpha = -1000
beta = 1000
но не уверен что это правильно...
2) Не могли бы Вы посмотреть данную реализуацию
и прокомментировать что не правильно работает в самом алгоритме...
и соблюдены ли правла игры
Adopt wrote: > Пытаюсь реализовать метод альфа бета отсчечений в игре Реверси > возникло несколько вопросов: > > 1) Какие лучеше всего значения поставить под alpha и beta? > Понятно что alpha < beta то есть присваиваю > alpha = -1000 > beta = 1000 > но не уверен что это правильно... > > 2) Не могли бы Вы посмотреть данную реализуацию > и прокомментировать что не правильно работает в самом алгоритме... > и соблюдены ли правла игры > > интерфейс пока примитивный > > http://rsdn.ru:80/File/39660/reversout.jar
Хотел посмотреть и обыграть, но из-за непонятного моей
java version "1.4.1_01"
Java(TM) 2 Runtime Environment, Standard Edition (build 1.4.1_01-b01)
Java HotSpot(TM) Client VM (build 1.4.1_01-b01, mixed mode)
main class не смог. html-страничка, быть может, помогла бы. Или ключик к
java. Или указание на Вашу версию. Под любимой ОС не смотрел, сейчас под
Windows. Завтра посмотрю.
Здравствуйте, raskin, Вы писали:
R>Adopt wrote: >> Пытаюсь реализовать метод альфа бета отсчечений в игре Реверси >> возникло несколько вопросов:
R>Хотел посмотреть и обыграть, но из-за непонятного моей R>java version "1.4.1_01" R>Java(TM) 2 Runtime Environment, Standard Edition (build 1.4.1_01-b01) R>Java HotSpot(TM) Client VM (build 1.4.1_01-b01, mixed mode)
R>main class не смог. html-страничка, быть может, помогла бы. Или ключик к R>java. Или указание на Вашу версию. Под любимой ОС не смотрел, сейчас под R>Windows. Завтра посмотрю.
Adopt wrote: > R>Adopt wrote: >> > Пытаюсь реализовать метод альфа бета отсчечений в игре Реверси >> > возникло несколько вопросов: > > R>Хотел посмотреть и обыграть, но из-за непонятного моей > [skip] > R>java. Или указание на Вашу версию. Под любимой ОС не смотрел, сейчас под > R>Windows. Завтра посмотрю. > > нужна JRE 1.5 ...
Спасибо за совет.
Впечатления из-под Linux:
1. Прорисовка верхнего ряда мне показалась странной (в полклетки) — это
мой глюк?
2. Правила нарушаются:
*o
o*
------
***
o*
------
o
o**
o*
------
O
*****
o*
------
o
o?***
o o*
3. За углы не борется. То есть совсем. То есть идёт вперёд ногами против
любого вменяемого противника. Догонять IaGno(идущего туда же). Это про
оценочную функцию — отданный мне угол при свободных пол-доски -- это
должен быть минус для оценки позиции.
2!! + 3 привели к решению бросить это дело. (до исправления?).
P.S. Сделайте, пожалуйста, кнопку [New Game] или скажите, как этого
(Restart) добиться без перезапуска Java.
Здравствуйте, raskin, Вы писали:
R>. За углы не борется. То есть совсем. То есть идёт вперёд ногами против R>любого вменяемого противника. Догонять IaGno(идущего туда же). Это про R>оценочную функцию — отданный мне угол при свободных пол-доски -- это R>должен быть минус для оценки позиции.
R>2!! + 3 привели к решению бросить это дело. (до исправления?).
R>P.S. Сделайте, пожалуйста, кнопку [New Game] или скажите, как этого R>(Restart) добиться без перезапуска Java.
Можно поподробней на счет правил... а не очень понял....
Уже приятно поиграться.
Но:
1. Правила. Сделайте ей запись партии, что ли. Ход — поле до — поле
после. Или отдельную кнопку: указать свой ход — показать что изменится —
показать ответный ход — показать что изменится (всё разными цветами) —
применить. Увидите много интересного. И я помогу, вероятно. А то делать
снимки экрана про запас — лень. (Уж извините). И трафика случайным
читателям ветки они пожрут.
2. Зачем она иногда выдаёт Exception:Index out of bounds на легальные
ходы? Следующим щелчком всё срабатывает, но изучение записи этой
проблемы поможет найти ошибки в алгоритме, и похоже в алгоритме
обработки хода.
3. В поиске Вы как оценочную функцию используете количество фишек?
Добавьте поправку на углы. Это не все делают, но те программы, кто не
делает, играют слабее.
Здравствуйте, raskin, Вы писали:
R>Adopt wrote: >> Здравствуйте, Adopt, Вы писали: >> >> A>Здравствуйте, raskin, Вы писали: >> >> вот более свежая версия >> >> http://rsdn.ru:80/File/39660/ReversiNew.jar
R>Уже приятно поиграться. R> Но: R>1. Правила. Сделайте ей запись партии, что ли. Ход — поле до — поле
ok, сделаю
R>2. Зачем она иногда выдаёт Exception:Index out of bounds на легальные
это баг
R>3. В поиске Вы как оценочную функцию используете количество фишек?
можно поподробней как такое возможно такое реализовать?
Adopt wrote: > R>Уже приятно поиграться. > R> Но: > R>1. Правила. Сделайте ей запись партии, что ли. Ход — поле до — поле > > ok, сделаю > > R>2. Зачем она иногда выдаёт Exception:Index out of bounds на легальные > > это баг
Верю. Один такой баг у меня объяснил половину нестыковок на игровом поле. > > R>3. В поиске Вы как оценочную функцию используете количество фишек? > > можно поподробней как такое возможно такое реализовать?
Alpha-Beta отсечение, насколько я помню, это поиск по дереву игры с
оптимизацией и применением на некоторой глубине оценочной функции (я не
верю, что Ваша программа обходит хоть одну ветвь до конца — на 60 ходов.
Мне ещё 18 нет, а я у неё уже выигрывал..). Поэтому на некотором шаге
оценкой позиции является не фактическая её стоимость (+\infty/-\infty),
а её оценка исходя из разных характеристик. Одна из них — количество
фишек. Если она же единственная, то программа сдаёт углы и стороны без
особого сопротивления (они дают выигрыш не сразу), а потом оказывается
поздно. На самом же деле, сданный угол при полупустой доске — почти
верный проигрыш. Я никогда не писал сам такую программу, но если Вы
введёте в оценочную функцию большую ценность углов/сторон с параметром,
могу поподбирать немного. Могу, в принципе, посмотреть оценочную функцию
в kreversi и сказать их идеи. При этом, правда, возможно (хотя не факт)
игрушка окажется под угрозой "вируса GPL", как это называют противники
любимой ОС.
Здравствуйте, Adopt, Вы писали:
A>Пытаюсь реализовать метод альфа бета отсчечений в игре Реверси A>возникло несколько вопросов:
A>1) Какие лучеше всего значения поставить под alpha и beta? A> Понятно что alpha < beta то есть присваиваю A> alpha = -1000 A> beta = 1000 A> но не уверен что это правильно...
A>2) Не могли бы Вы посмотреть данную реализуацию A>и прокомментировать что не правильно работает в самом алгоритме... A>и соблюдены ли правла игры
A>интерфейс пока примитивный
A>http://rsdn.ru:80/File/39660/reversout.jar
A>7kb
Оригинальный Alpha-Beta используешь? На сколько полуходов можно перебрать реверси (я сам в свое время шахматы писал)?
Здравствуйте, raskin, Вы писали:
R>Adopt wrote: >> R>Уже приятно поиграться. >> R> Но: >> R>1. Правила. Сделайте ей запись партии, что ли. Ход — поле до — поле >> R>могу поподбирать немного. Могу, в принципе, посмотреть оценочную функцию R>в kreversi и сказать их идеи. При этом, правда, возможно (хотя не факт) R>игрушка окажется под угрозой "вируса GPL", как это называют противники R>любимой ОС.
да, было бы здорово....
Скажите какие ошибки в правилах игры присутствуют
в этой версии (сделана кнопка Computer Step)
Здравствуйте, mkopachev, Вы писали:
M>Здравствуйте, Adopt, Вы писали:
A>>Пытаюсь реализовать метод альфа бета отсчечений в игре Реверси A>>возникло несколько вопросов:
A>>1) Какие лучеше всего значения поставить под alpha и beta? A>> Понятно что alpha < beta то есть присваиваю A>> alpha = -1000 A>> beta = 1000 A>> но не уверен что это правильно...
A>>2) Не могли бы Вы посмотреть данную реализуацию A>>и прокомментировать что не правильно работает в самом алгоритме... A>>и соблюдены ли правла игры
A>>интерфейс пока примитивный
A>>http://rsdn.ru:80/File/39660/reversout.jar
A>>7kb
M> Оригинальный Alpha-Beta используешь? На сколько полуходов можно перебрать реверси (я сам в свое время шахматы писал)?
Здравствуйте, mkopachev, Вы писали:
M>Здравствуйте, Adopt, Вы писали:
A>>Пытаюсь реализовать метод альфа бета отсчечений в игре Реверси A>>возникло несколько вопросов:
M> Оригинальный Alpha-Beta используешь? На сколько полуходов можно перебрать реверси (я сам в свое время шахматы писал)?
M> С уважением Михаил Копачев
Adopt wrote: > Здравствуйте, raskin, Вы писали: > > R>Adopt wrote: >> > R>Уже приятно поиграться. >> > R> Но: >> > R>1. Правила. Сделайте ей запись партии, что ли. Ход — поле до — поле >> > > R>могу поподбирать немного. Могу, в принципе, посмотреть оценочную функцию > R>в kreversi и сказать их идеи. При этом, правда, возможно (хотя не факт) > R>игрушка окажется под угрозой "вируса GPL", как это называют противники > R>любимой ОС. > > да, было бы здорово.... >
Ничего особенного, но аккуратно (странно, кстати, раньше программа
играла сильнее, может быть потом старую версию тоже посмотрю). Есть очки
за занятые клетки и бонусы. При этом бонусы учитываются в начале игры с
большим весом, чем в конце (когда они не учитываются). Клетки 2-ой и
7-ой линии дают бонус -1. Углы дают бонус 2. Соседние с углом клетки —
бонус -1. Кроме того, в начале игры ценится не столько численность,
сколько перевес. А подробности — 22 KB:
Exception in thread "AWT-EventQueue-0"
java.lang.ArrayIndexOutOfBoundsException:
0 >= 0
at java.util.Vector.elementAt(Unknown Source)
at reversi.c.a(Unknown Source)
at reversisample.MainJFrame.c(Unknown Source)
at reversisample.MainJFrame.b(Unknown Source)
at reversisample.a.actionPerformed(Unknown Source)
at javax.swing.AbstractButton.fireActionPerformed(Unknown Source)
at javax.swing.AbstractButton$Handler.actionPerformed(Unknown
Source)
at javax.swing.DefaultButtonModel.fireActionPerformed(Unknown
Source)
at javax.swing.DefaultButtonModel.setPressed(Unknown Source)
at
javax.swing.plaf.basic.BasicButtonListener.mouseReleased(Unknown Sour
ce)
at java.awt.Component.processMouseEvent(Unknown Source)
at javax.swing.JComponent.processMouseEvent(Unknown Source)
at java.awt.Component.processEvent(Unknown Source)
at java.awt.Container.processEvent(Unknown Source)
at java.awt.Component.dispatchEventImpl(Unknown Source)
at java.awt.Container.dispatchEventImpl(Unknown Source)
at java.awt.Component.dispatchEvent(Unknown Source)
at java.awt.LightweightDispatcher.retargetMouseEvent(Unknown
Source)
at java.awt.LightweightDispatcher.processMouseEvent(Unknown Source)
at java.awt.LightweightDispatcher.dispatchEvent(Unknown Source)
at java.awt.Container.dispatchEventImpl(Unknown Source)
at java.awt.Window.dispatchEventImpl(Unknown Source)
at java.awt.Component.dispatchEvent(Unknown Source)
at java.awt.EventQueue.dispatchEvent(Unknown Source)
at
java.awt.EventDispatchThread.pumpOneEventForHierarchy(Unknown Source)
at java.awt.EventDispatchThread.pumpEventsForHierarchy(Unknown
Source)
at java.awt.EventDispatchThread.pumpEvents(Unknown Source)
at java.awt.EventDispatchThread.pumpEvents(Unknown Source)
at java.awt.EventDispatchThread.run(Unknown Source)
Здравствуйте, Adopt, Вы писали:
A>Здравствуйте, mkopachev, Вы писали:
M>>Здравствуйте, Adopt, Вы писали:
A>>>Пытаюсь реализовать метод альфа бета отсчечений в игре Реверси A>>>возникло несколько вопросов:
A>>>1) Какие лучеше всего значения поставить под alpha и beta? A>>> Понятно что alpha < beta то есть присваиваю A>>> alpha = -1000 A>>> beta = 1000 A>>> но не уверен что это правильно...
A>>>2) Не могли бы Вы посмотреть данную реализуацию A>>>и прокомментировать что не правильно работает в самом алгоритме... A>>>и соблюдены ли правла игры
A>>>интерфейс пока примитивный
A>>>http://rsdn.ru:80/File/39660/reversout.jar
A>>>7kb
M>> Оригинальный Alpha-Beta используешь? На сколько полуходов можно перебрать реверси (я сам в свое время шахматы писал)?
A>Да, вот отсюда A>http://algolist.manual.ru
А что-нибудь типа NegaScout или MTD(f) не пробовал? Это достаночно серьезно ускоряет перебор. На шахматах я получил возможность увеличить глубину просмотра примерно втрое без дополнительных оптимизаций и использования генераторов ходов.
З.Ы. А вот по твоей ссылке я пройти не могу — проксик режет сволота .
Здравствуйте, raskin, Вы писали:
R>Adopt wrote: >> Здравствуйте, raskin, Вы писали: >>
R>Игра против Iagno. Светлая фишка — последний ход синего (Iagno). Не R>Photoshop, что Вы. http://rsdn.ru:80/File/40778/rev_err2_small.png . R>Iagno всё делает правильно. Размер — 40 KB.
Можете поподробней что в этой комбинации не так,
и что должна сделать была программа?
Если не сложно указывайте координаты...
Спасибо
R>Время жизни картинок — надеюсь, большое. (>=1 месяц)
Adopt wrote: > R>Игра против Iagno. Светлая фишка — последний ход синего (Iagno). Не > R>Photoshop, что Вы. http://rsdn.ru:80/File/40778/rev_err2_small.png . > R>Iagno всё делает правильно. Размер — 40 KB. > > Можете поподробней что в этой комбинации не так, > и что должна сделать была программа? > Если не сложно указывайте координаты... > > Спасибо > > > R>Время жизни картинок — надеюсь, большое. (>=1 месяц)
Была бы история в консоли — были бы координаты сразу.
Ситуация:
(начало координат 1,1)
1,4 — чёрная фишка
2,5 — чёрная
3,4 — чёрная
3,5 — белая
3,6 — чёрная
4,4 — чёрная
4,5 — белая
5,4 — чёрная
5,5 — белая
Ход белых:
3,7
Взяты:
3,6 между 3,5 и 3,7
Ответ чёрных:
4,7
взяты:
3,6 между 4,7 и 2,5
Программа объявляет взятыми:
3,6 (корректно)
4,5 (между 4,4 и 4,7 игнорируя 4,6 ??)
Adopt wrote: > Здравствуйте, raskin, Вы писали: > > R>4,5 (между 4,4 и 4,7 игнорируя 4,6 ??) > > R>В символах _bw (. — следующий ход): > R> > > R>___b > R>____b > R>___bwb. > R>___bw > R>___bw > R>=========NEXT======= > R>___b > R>____b > R>___bwww > R>___bw_. > R>___bw > R>===========NEXT======= > R>___b____ | ___b____ > R>____b___ | ____b___ > R>___bwbw_ | ___bwbw_ > R>___bw_b_ | ___bb_b_ > R>___bw___ | ___bw___ > R>________ | ________ > R>________ | ________ > R>________ | ________ > R> > > > > А как часто повторяется эта ошибка — периодически или постоянно? > Бывали ли случаи когда по диагонали вниз вправо не закрашивались ячейки?
Разные похожие ошибки повторяются иногда. Я к тому же не всегда их
замечаю. А Setup Board, например, здесь нет. Из-за отсутствия истории с
указанием всех ходов и принадлежностей всех клеток после каждого поиск
нестыковок ручной => трудоёмкий. А опыта .jar -> .class -> .java или
писания на Java у меня нет, поэтому самому добавлять мне не хочется.
Если получится могу написать и отладить переворот фишек на Pascal и
отослать вам хоть .exe, хоть ELF (с исходником, не вопрос) — вам какой
формат ближе (я не уверен, что сделаю, но шанс есть)?
Здравствуйте, raskin, Вы писали:
R>Разные похожие ошибки повторяются иногда. Я к тому же не всегда их R>замечаю. А Setup Board, например, здесь нет. Из-за отсутствия истории с R>указанием всех ходов и принадлежностей всех клеток после каждого поиск R>нестыковок ручной => трудоёмкий. А опыта .jar -> .class -> .java или R>писания на Java у меня нет, поэтому самому добавлять мне не хочется. R>Если получится могу написать и отладить переворот фишек на Pascal и R>отослать вам хоть .exe, хоть ELF (с исходником, не вопрос) — вам какой R>формат ближе (я не уверен, что сделаю, но шанс есть)?
Adopt wrote: > Здравствуйте, raskin, Вы писали: > > R>Разные похожие ошибки повторяются иногда. Я к тому же не всегда их > R>замечаю. А Setup Board, например, здесь нет. Из-за отсутствия истории с > R>указанием всех ходов и принадлежностей всех клеток после каждого поиск > R>нестыковок ручной => трудоёмкий. А опыта .jar -> .class -> .java или > R>писания на Java у меня нет, поэтому самому добавлять мне не хочется. > R>Если получится могу написать и отладить переворот фишек на Pascal и > R>отослать вам хоть .exe, хоть ELF (с исходником, не вопрос) — вам какой > R>формат ближе (я не уверен, что сделаю, но шанс есть)? > > Вот новая версия где исправлен баг > http://rsdn.ru:80/File/39660/ReversiUpd.jar > > Здесь все нормально? > > история будет выводиться в консоль в следующей версии
Adopt wrote: > Здравствуйте, raskin, Вы писали: > > R>Adopt wrote: >> > Здравствуйте, raskin, Вы писали: >> > > R>Код верификатора (консольный на Паскаль; ELF — по просьбе/когда соберусь > R>выложу архив EXE): > R>http://rsdn.ru:80/File/40778/reversi_src.zip > R>http://rsdn.ru:80/File/40778/reversi_elf.zip > > Спасибо. > > Но не очень понятно что делает функция make_move? > она делает ход компьютера?
Нет. Это же верификатор. Программа работает как доска, ругающаяся при
нарушении правил. Вход описан write_usage, а структура такова:
good_piece — этот символ является чьей-то фишкой
good_field — этот символ может описывать поле
TBoard:
init — заполнить доску пустыми клетками
to_string — строка описания доски
set_field — задать состояние заданной клетки (для установки позиции)
make_move — сделать ход заданной стороны в заданную клетку (с контролем
возможности и переворотами)
num_flip — подсчитать сколько вражеских фишек надо перевернуть вдоль
луча в заданном направлении при ходе в заданную точку
do_flips — перевернуть фишки в условиях предыдущего пункта
make_four — поставить на доске начальную позицию
read_it — считать доску с консоли в кратком формате
do_keyboard_query — запросить и выполнить действие
соответственно, "s62b" поставит чёрную фишку в 6:2, что бы ни стояло на
доске, а "m62b" поставит её туда только если можно, причём сделает
перевороты (тестировал — ошибок не нашёл). Аналогично set_field(6,2,'b')
и make_move(6,2,'b') .
Здравствуйте, raskin, Вы писали:
R>Adopt wrote: >> Здравствуйте, raskin, Вы писали: >> >> R>Adopt wrote: >>> > Здравствуйте, raskin, Вы писали: >>> >
R>соответственно, "s62b" поставит чёрную фишку в 6:2, что бы ни стояло на R>доске, а "m62b" поставит её туда только если можно, причём сделает R>перевороты (тестировал — ошибок не нашёл). Аналогично set_field(6,2,'b') R>и make_move(6,2,'b') .
Вот новая версия с полностью передаланными ходами,
так же во втором файле исходник на Java как расчитываются ходы
Добавлен лог, то есть все ходы выводятся на консоль
Adopt wrote: > Здравствуйте, raskin, Вы писали: > > R>Adopt wrote: >> > Здравствуйте, raskin, Вы писали: >> > >> > R>Adopt wrote: >> >> > Здравствуйте, raskin, Вы писали: >> >> > > > R>соответственно, "s62b" поставит чёрную фишку в 6:2, что бы ни стояло на > R>доске, а "m62b" поставит её туда только если можно, причём сделает > R>перевороты (тестировал — ошибок не нашёл). Аналогично set_field(6,2,'b') > R>и make_move(6,2,'b') . > > Вот новая версия с полностью передаланными ходами, > так же во втором файле исходник на Java как расчитываются ходы > > Добавлен лог, то есть все ходы выводятся на консоль > > http://rsdn.ru:80/File/39660/ReversiNUP.jar > http://rsdn.ru:80/File/39660/src.java > > Спасибо.
Придирка насчёт консоли: перезапуск игры не выводится.
Насчёт правил: здорово, что обрабатывается пропуск хода компьютера.
Хуже, что не обрабатывается пропуск хода игроком.
Остальное, вроде бы правильно (сверял окончательную позицию с тем, что
говорила проверяющая программа в консоли).
Замечание (не попытка наехать, я понимаю, что Вы сначала отладили
правила): то, что программа не ценит углы, помогло мне выиграть всухую.
Здравствуйте, raskin, Вы писали:
R>Adopt wrote: >> Здравствуйте, raskin, Вы писали: >>
R>, но не поняла, что Iagno пропускает ход.
R>Iagno уровень 2 : Iagno выиграл.
R>А так — уже здорово. Теперь можно подбирать оценочную функцию.
Да, осталось самое сложное....
решил что надо строить дерево на несколько ходов вперед,
количество ходов на которое будет построено дерево
является уровенем сложности. Однако это не оптимально ведь требуется довольно много ресурсов.
В этой версии целевая функция просто выбирает
какой ход даст больше очков, то есть само дерево
не строится, а оценивается текущая ситуация.
Adopt wrote: > Здравствуйте, raskin, Вы писали: > R>А так — уже здорово. Теперь можно подбирать оценочную функцию. > > Да, осталось самое сложное.... > решил что надо строить дерево на несколько ходов вперед, > количество ходов на которое будет построено дерево > является уровенем сложности. Однако это не оптимально ведь требуется > довольно много ресурсов.
А куда дели Alpha-Beta поиск? Исходно же был он? Ресурсов не так много —
на три полухода надо при полном переборе 8000 позиций, т.е. <10^6
операций с полями. А отсечение ещё сокращает перебор. > > В этой версии целевая функция просто выбирает > какой ход даст больше очков, то есть само дерево > не строится, а оценивается текущая ситуация.
Играть стала слабее. Iagno1 у неё выиграл. Просчитывать хотя бы ответ
противника необходимо. > > http://rsdn.ru:80/File/39660/ReversiAlp.jar
За индикацию New game — спасибо. Правда, теперь она используется мало —
история нужна была при поиске ошибок в обработке правил. > > Как можно еще реализовать целевую функцию?
А ценность полей Вы учитываете? Но все равно перебор с отсечением
реализовать в конце концов придётся.
Здравствуйте, raskin, Вы писали:
>> В этой версии целевая функция просто выбирает >> какой ход даст больше очков, то есть само дерево >> не строится, а оценивается текущая ситуация. R>Играть стала слабее. Iagno1 у неё выиграл. Просчитывать хотя бы ответ R>противника необходимо. >> >> http://rsdn.ru:80/File/39660/ReversiAlp.jar R>За индикацию New game — спасибо. Правда, теперь она используется мало — R>история нужна была при поиске ошибок в обработке правил. >> >> Как можно еще реализовать целевую функцию? R>А ценность полей Вы учитываете? Но все равно перебор с отсечением R>реализовать в конце концов придётся.
Возможен ли такой алгоритм?
1) Найти возможные ходы
2) Поставить ход в позицию x, y одну из найденных
3) Рассчитать очки, которые получаются при ходе
3) Рассчитать возможные ходы противника
4) В цикле рекурсивно вызвать функцию для каждой из них (перейти в п. 2)
только с указанием другого цвета
и вычесть возвращенное этой функцией значение из очков п.3
5) вернуть очки из п.3
6) Сделать сортировку по очкам и выбрать найбольши эелемент
+ к этому алгоритму сдлелать альфа бета отсечения,
то есть проверять только самые лучшие ходы противника....
Adopt wrote: > 1) Найти возможные ходы > 2) Поставить ход в позицию x, y одну из найденных > 3) Рассчитать очки, которые получаются при ходе > 4) Рассчитать возможные ходы противника > 5) В цикле рекурсивно вызвать функцию для каждой из них (перейти в п. 2) > только с указанием другого цвета > и вычесть возвращенное этой функцией значение из очков п.3 > 6) вернуть очки из п.3 > 7) Сделать сортировку по очкам и выбрать найбольши эелемент > > + к этому алгоритму сдлелать альфа бета отсечения, > то есть проверять только самые лучшие ходы противника....
Отсекать по оценочным очкам, полученным противником, по-моему, не
оптимально. Лучше традиционно (разве в первых версиях было не так?).
Поскольку часто съесть больше всего означает отдать угол-другой. Лучший
ход быстро оказывается худшим. Но попробовать можно. С Iagno (если
дойдёт — с KReversi) я сравнивать помогу, а личную встречу Вы им сами
организуете. Если дать возможность выбирать, кто первый ходит.
R>Отсекать по оценочным очкам, полученным противником, по-моему, не R>оптимально. Лучше традиционно (разве в первых версиях было не так?). R>Поскольку часто съесть больше всего означает отдать угол-другой. Лучший R>ход быстро оказывается худшим. Но попробовать можно. С Iagno (если R>дойдёт — с KReversi) я сравнивать помогу, а личную встречу Вы им сами R>организуете. Если дать возможность выбирать, кто первый ходит.
Вот версия в которой реализовано alpha — beta отсечения + еще дополнительно ограничена глубина
проверки до 4
Adopt wrote: > Вот версия в которой реализовано alpha — beta отсечения + еще > дополнительно ограничена глубина > проверки до 4 >
Так и делают. Качество зависит от глубины и от оценочной функции. > http://rsdn.ru:80/File/39660/ReversiNUP.jar > > Интересно ли с ней играть?
Во-первых, когда у неё остаётся 3 фишки против 48 и ни одного хода она
не пишет "Заставили пропустить", а кидает Exception.
Во-вторых, я не показатель — мне с Iagno:level 3 играть иногда скучно.
Метод лобовой атаки к Вашей программе применим вполне: аккуратно
громится угол, после чего вокруг него собирается >32 фишек, которые
нельзя взять.
Кроме того, она проиграл Iagno:level 1. У Вас же была версия, играющая
сильнее, но ошибающаяся иногда — может ладно, что изредка подтормаживала?
.