Программа АТАРИГО

Здравствуйте!

После долгого перерыва вышла новая версия программы. Не всё получается так быстро, как планируется :-)

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

По просьбам пользователей сделал раздел ссылок на другие играющие программы. В частности разместил на сервере программку под DOS, но не могу понять кто ее автор. Я ее видел на диске, кажется, под названием GOSIMUL. У меня она как GO_G лежит.
Кто-нибудь что-нибудь знает про неё?



Программа 'АТАРИГО': [www.atarigo.narod.ru]

У меня она есть это предыдущая версия MFGO

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

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

На доске 3х3: (время счета ~ 7 сек)

oxo
xxx
oxo

На доске 4х3: (время счета ~ 1.5 час - это без учета симметрии начальных позиций)

oooo
xxxx
oooo

А вот дальше уже проблемы :-) Запущеный на ночь расчет на доске 4х4 ничего не дал. Похоже надо оптимизировать. Или пора на ассемблер переходить? :-)

А какие будут мнения по поводу решения на досках 4х4, 5х4 и 5х5 ? :-)



Программа 'АТАРИГО': [www.atarigo.narod.ru]

Где-то я слышал, что некотором Университете кластером из нескольких десятков компов, за несколько суток просчитана до конца игра на доске 6х7. Не атари го, а настоящее го.
7х7 уже не получилось.



Виктор aka "Председатель ревизионной комиссии РФГ"

Что-то не так. На доске 4х3 первый ход в (2,4) не выигрывает.

Про малые доски :
[senseis.xmp.net]

Там в частности сказано , что 6*7 решено , а 7*7 - нет , но про университетские кластеры я не заметил ...



Наш рот всегда открыт для диалога (c) Владимир ВишневскийOkruzhor (экс-Игозавр)

Ну склероз у меня :-)
Ну ей богу, "то что было не со мной - помню" :-)



Виктор aka "Председатель ревизионной комиссии РФГ"

Где в АТАРИГО пасс? если у меня уже два глаза, я что должен себе их закрывать? А стандартное лишение глаз нельзя, так как это захват моего камня, то что является в АТАРИГО проигрышем

А в АТАРИГО паса нет! Так что придется глазки самому себе закрывать :-)

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

В новой версии АТАРИГО (которая выйдет примерно в феврале) уже будет кнопочка "Пас". Но означать она будет именно, то что я написал.



Программа 'АТАРИГО': [www.atarigo.narod.ru]

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

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

Вообще, как мне кажется, игра Го уникальна (для программиста) тем, что очень хорошо "масштабируется". Причем как "вширь" (изменяя размер доски), так и "вглубь" (изменяя количество N - необходимых для победы "захватов"). А уже при увеличении N возникает понятие "территории", желание ее защищать и необходимая для этого стратегия :-)
Там, правда, еще Ко есть, но это отдельная тема..

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



Программа 'АТАРИГО': [www.atarigo.narod.ru]

Илья Ветров писал(а):

> Про малые доски :
> [senseis.xmp.net]
>
> Там в частности сказано , что 6*7 решено , а 7*7 - нет , но про
> университетские кластеры я не заметил ...
>

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

Мне больше нравится статья: "Solving Ponnuki-Go on Small Boards", Erik Welf и другие .., 2002 год.

Примерное содержание:

Для реального Го:
"Компьютерное решение было опубликованно только для доски 4х4..
Решения (с помощью человека) 5х5 и 6х6 существуют, но чрезвычайно неуловимы (subtle) и не были подтверждены компьютерным анализом.."

Для Атари-Го:
"Мы обнаружили, что на малых квадратных досках с четными размерами (2х2 и 4х4) побеждают белые (черные, как ходящие первыми, попадают в цугцванг)..
На нечетных досках (3х3 и 5х5) побеждают черные, которые используют свой первый ход для захвата центра..
Интересным остается вопрос, кто побеждает на доске 6х6 ?.. Мы запускали расчет, но после нескольких недель работы "отрубилось" электричество.." :-)



Программа 'АТАРИГО': [www.atarigo.narod.ru]

Сергей Межов писал(а):

> Что-то не так. На доске 4х3 первый ход в (2,4) не выигрывает.

Решил еще раз попросить компьютер напрячь свои электронные мозги. Помигал он задумчиво лампочками: "да нет", говорит, "все так, первый ход в крайний пункт средней линии выигрывает!" :-)
Может быть мы правила по разному трактуем?
Давайте посмотрим, какие здесь есть варианты в ответ на первый ход черных "а2" (здесь и далее обозначения обычные: по горизонтали - слева направо буквы, по вертикали - снизу вверх цифры).

1) на любой ответ белых по крайним горизонталям (ну, в левом то углу им сразу хана, и обозначается это символом "@") будут симметричные (например) ответы черных по центральной линии:

|@x..| |.o..| |..o.| |...o|
|x...| |xx..| |x.x.| |x..x|
|....| |....| |....| |....|

2) если же имелся ввиду ответ "белые b2", то на него черные решительно отвечают "с2" :-)
и вот несколько основных вариантов:

|.o..| |.o..| |.oo.| |.oo.|
|xox.| |xox.| |xox.| |xoxx|
|....| |.x..| |.x..| |.x..|

______________|.o.o| |.oxo|
______________|xox.| |xox.|
______________|.x..| |.x..|

|..o.| |..o.| |.oo.| |.oo.|
|xox.| |xox.| |xox.| |xoxx|
|....| |.x..| |.x..| |.x..|

|...o| |..xo| |..xo| |..x@|
|xox.| |xox.| |xoxo| |xox@|
|....| |....| |....| |...x|

|....| |....| |.o..| |.ox.|
|xoxo| |xoxo| |xoxo| |xoxo|
|....| |.x..| |.x..| |.x..|


Как мы видим, черные везде выигрывают..



Программа 'АТАРИГО': [www.atarigo.narod.ru]

Мы, действительно, по разному трактуем правила. В моем запрещено говорить пас, а жертвы в процессе игры - не поражение.

Дальше, уже при N=2 (количество необходимых для победы "захваченных" камней) появится возможность жертвовать один камень :-)

По поводу пасов могут быть варианты. Без них, конечно, получается более строго математически, но зато не так интересно играть. Как правильно заметил Владимир - "ерунда" :-)
Копромисcный вариант - "американские" пасы..

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



Программа 'АТАРИГО': [www.atarigo.narod.ru]

По поводу пасов. Отсутствие паса - это древнейшие правила Го. Игра не менее интересная, но намного продолжительнее.

Сергей Межов писал(а):

> Мы, действительно, по разному трактуем правила. В моем
> запрещено говорить пас, а жертвы в процессе игры - не
> поражение.

Вы говорите о правилах атари-го? Можно их огласить?
Мне кажется было бы интересно играть по правилам кто больше сьест камней ( моему младшему 5 лет и ему в го нравится ИМЕННО кушать камушки :)) т.е игра идет до того момента, когда все ходы будут суицидом :)

Именно таковы древнейшие правила Го. Невозможность совершения очередного хода - конец игры.

А кто при этом побеждает? Партнер того, кто не может ходить или тот, кто к этому времени больше съел камней? :-)

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

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



Программа 'АТАРИГО': [www.atarigo.narod.ru]

В древности понятия "победитель" не было. Было понятие - конец игры.