Задача 4 от брой 01/2006 - ВМЪКНИ - Анализ

Структурата state съдържа състояние на дъската собствените и противниковите точки, флаг показващ кой е направил този ход и масив за всички 15 възможни хода.

Рекурсивният метод построява пълно дърво на ходовете. Строежа става в ‘дълбочина’. След създаването на 15-те следващи възможни хода S_a1,..,S_a15 на състоянието S_a се търси максимумът на моите или противниковите точки(в зависимост от флагът player) и те се добавят към точките на S_a. Разбира се това е най-опростения вариант и няма никаква гаранция че противникът ще избере ходът носещ му най-много точки.

И накрая от генерираното дърво с корен S трябва да изберем подходящ ход. Това се прави от методът getMove. Критерият е прост, търси се максимумът на функцията

myPoints - k * opPoints за всяко S_i.

Параметърът k влияе по следния начин: колкото по-малко е k, толкова по-‘лакомо’ играе алгоритъмът, т.е. стреми се да спечели колкото може повече точки, без значение какво печели противника. И обратното, колкото по-‘голямо’ е k, толкова повече се ‘пренебрегват’ собствените точки за сметка на минимизиране на противниковите. Във вариантът, който предадох, е с k=0,5. Това е някакъв компромисен вариант, не е на принципа ‘на противника да му е зле’, нито е сляпо преследване само на собствени точки. При няколко възможни максимума се избира случайно някой от тях. В интерес на повечето точки е ако има няколко възможни хода да изберем такъв, който не ‘избутва’ плочка, а запълва празна клетка, за да има повече плочки на дъската. Затова на такива ходове давам двоен шанс.

И последната важна за отбелязване част (която всъщност ми е донесла втората позиция) е следенето за ходовете на противника. Ако той направи определен брой поредни ходове ‘6’ (заложил съм 5 хода), преминавам към конструиране на 7 нива вместо на 3, като за противников ход се смята само ‘6’.

Нишки не съм ползвал, и не използвам създаденото до момента дърво, а всеки път се създава ново.

Автор: Лазарин Лазаров

За въпроси можете да ни пишете на адрес: konkurs@musala.com.

Supported by Musala Soft Ltd.

Copyright 2000-2010 by Musala Soft Ltd. All rights reserved.