Поиск оптимальной стратегии игры в точки

[sir Alex]

Народ, вы наверно знаете игру Точки. Но на всякий случай расскажу правила
Двачеловека по очереди ставят точки в узлы клетчатой решетки.Цель провести замкнутую ломаную так, чтобы внутри оказались точки противника.Соединять точки можно, если они находятся в соседних узлах,или на диагонали единичного квадрата.Свои точки внутри ломаной противника использовать нельзя.Свои точки ломанной использовать можно.У каждого игрока есть фиксированое кол-во ходов(например, 50).Помогите найти оптимальную стратегию игры, плз!!!

 

[Trotil]

sir Alex
Я думаю, это исследовательская тема для дипломной работы в вузе

Тебе где поставили такой вопрос?

 

[sir Alex]

ага...но сказали найти хоть что-то,не обязательно доводить до конца...преп все-таки понял,что мы это полностью не сможем сделать...10 класс все-таки(((Играли долго и упорно, и толком ичего не вывели... Есть один принцип, конечно, но срабатывает он в зависимости от противника...Сейча думаем, может програмку такую написать.....

 

[Trotil]

http://pointsgame.narod.ru/
http://pointsxt.logicsworld.net/forum/index.php?showtopic=316 - книга о точках

Это вся литература, которую я нашел.

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

Общая идея:

1) узнаешь как можно больше об правилам и об стратегии игры
2) пробуешь на основе прочитанного разрботать некоторую оценочнуб функцию z = f(A,x,y)
А - матрица текущего положения, по-хорошему, должна быть глобальной
(x,y) - вариант хода
z - число, чем оно больше - тем ход лучше. Соответственно, ищется максимум f.

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

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

 

[sir Alex]

Спасибо огромное,попробуем