Главная » Игры, Исходники » Игра "Уголки"

0

Для иллюстрации всего вышесказанного приведем небольшой пример. На игровом поле 8×8 находятся 12 черных шашек (в левом верхнем углу) и 12 белых (в правом нижнем). Нужно занять исходные позиции противника. Черные должны стремиться занять правый нижний угол, а белые — левый верхний. Шашки ходят во всех направлениях на одну клетку (кроме диаго­налей). Шашка может прыгать через другие шашки в любых направлениях (кроме диагоналей).

Для решения этой задачи используется перебор. Ход противника не учиты­вается. Если говорить про моделирование поведения противника, то мы мо­делируем "болвана". Тем не менее, т. к. взятий нет, это неплохо работает на практике. Используется некоторый массив, где в каждой клетке нарисовано, куда фигуре лучше пойти. Просчет мы ведем только для черных. Таким об­разом, числа массива минимальные в верхнем левом углу и максимальные в правом нижнем. Теоретически, массив оценок для черных должен быть следующий:

1, 2, 3, 4, 5, 6, 7, 8,

9,10,11,12,13,14,15,16,

17,18,19,20,21,22,23,24,

25,26,27,28,29,30,31,32,

33,34,35,36,37,38,39,40,

41,42,43,44,45,46,47,48,

49,50,51,52,53,54,55,56,

57,58,59,60,61,62,63,64

Я использовал другие числа, чтобы программа более явно стремилась в пра­вый нижний угол. Дело в том, что мы не учитываем ход противника (для него массив инвертирован), и у нас нет времени на вычисления. В "Угол­ках" программа должна ходить практически сразу. Если она будет думать по 30 секунд над тривиальной задачей и вычислять позиционные преимущест­ва, это будет выглядеть смешно. Мы считаем на 3 хода (только своих). Если бы мы учитывали ход противника, то задача ничуть не уступала бы шахма­там. Потребовалась бы большая глубина перебора (чтобы было хотя бы 3 своих полухода, нужно суммарно иметь 6: 3 своих и 3 противника). При­шлось бы прибегать к сложным программным решениям, а для такой про­стой программы это выглядело бы нелепо. На практике играла бы програм­ма не лучше (может, и хуже). Данный прием пропуска хода используется и в шахматах, но несколько по-другому. Суть в том, что если мы делаем под­ряд два хода, это засчитывается как наш возможный максимум. Если про­тивник сделает ход, то результат может быть только меньше для нас. Здесь мы считаем на 3 хода и, следовательно, пропускаем 2 хода противника (по­лухода). Получается, что мы играем не с "болваном", а с "суперболваном". Программа ходит так, как если бы противник 2 раза не походил. Но т. к. игра построена в основном на "зевках", это работает.

Есть еще один интересный момент в программе. Это определение "пры­гающих" ходов шашки. Шашка начинает движение из своей стартовой точ­ки и может выписывать довольно замысловатые траектории. При нахожде­нии возможного пути мы пользуемся следующим правилом: шашка может сделать любой легальный ход, за исключением тех клеток, на которых она уже побывала. Это только при взятии перемещений шашки в одном узле. Для запоминания полей, на которых шашка уже побывала, мы используем множество, в котором запоминаем индекс клетки массива, где побывала шашка. В языке С типа данных "множество" нет, и приходится конструиро­вать его самим. Это делается чрезвычайно просто. Решение довольно любо­пытное и может применяться в других программах. Наше множество пред­ставлено массивом 16 байт. В каждом байте — 8 бит, следовательно, в мно­жестве может быть запомнено 16 х 8 = 128 элементов (значений от О до 127). Если элемент (например, 10) есть, в множестве соответствующий бит установлен в 1. Если нет — в 0. Для определения бита, соответствующе­го данному числу, мы должны найти номер байта и номер бита в этом бай­те. Это делается очень просто:

byteNumber = N / 8; //результат деления bitNumber = N % 8; //остаток от деления

Игровое поле в уголках 8×8. Мы используем несколько больший массив: (10,10). Края массива (лишние поля) заполнены флагом выхода за пределы поля. Таким образом, не нужны проверки выхода за пределы. Мы всегда наращиваем координату на одну клетку, и если в ней флаг выхода за преде­лы игрового поля, то это значит, что мы вышли за пределы поля 8×8.

Листинг 1.1.

CopyRight © 2004 by Kornilov Evgeny e_k@sbor.net ////////// DEFINITION //////////////// #define В 1 //черная шашка tdefine W 2 //белая

#define F 3 //флаг выхода за пределы доски //стартовая позиция

int pos[10*10] = {

F,F, F, F, F, F, F, F, F, F, F,B,B,B,B,0,0,0,0,F, F,B,B,B,B,0,0,0,0,F, F,B,B,B,B,0,0,0,0,F, F,0,0,0,0,0,0,0,0,F, F, 0,0, 0,0, 0,0, 0,0, F, F,0,0,0,0,W,W,W,W,F, F,0,0,0,0,W,W,W,W,F, F,0,0,0,0,W,W,W,W,F, F, F, F, F, F, F, F, F, F, F };

//куда лучше ходить

int StTab[10*10] = {

0, 0,0,0,0,0,0,0,0,0,

0, 1,2,3,4,5,6,7,8,0,

0, 9,10,11,12,13,14,15,16,0,

0, 10,17,18,19,20,21,22,23,0,

0, 11,18,24,25,26,27,28,29,0,

О, 12,19,25,30,31,32,33,34,0, О, 13,20,26,31,401,402,403,404,0, О, 14,21,27,32,402,405,406,407,0, О, 15,22,28,33,403,406,408,409,0, О, 0,0,0,0,0,0,0,0,0 } ;

//стартовый список фигур машины (черных)

int PieceTab[12] = {11,12,13,14,

21,22,23,24,

31,32,33,34};

//номера конечных позиций

int EndTab[12] = {65,66,67,68,

75,76,77,78,

85,86,87,88};

//приращения при движении шашки int DelTab[4] = {-1,1,-10,10}; //описатель перемещения typedef struct) int source,dest; }TMove,*PMove;

////////////////тип – множество/////////// typedef union{ unsigned char data[16];

long data[4];

}TSet,*PSet; //обнуляет множество #define Clear(set)\

(set).data[0]=0; (set).data[1]=0; (set).data[2] =0; (set).data[3]=0; //включает элемент n в множество set #define Include(set,п)\

(set) .data[ (n) » 3] |= (1 « ( (n) S 7)); //возвращает не 0, если элемент п в множестве set #define In(set,n)\

( (set).data[ (n) » 3 ] & (1 « ((n) & 7)) ) ////////////////////////////////////////////// //переменные при просчете typedef struct{ int score,ply,max; TMove bestMove; TSet set; }Targ,*Parg;

/ /ьлаксимальное значение при просчете #define INFINITY 30000

//максимальная глубина просчета #define MAX_PLY 3 //проверка на конец

int CheckEnd(void) {

int n;

for(n = 0; n < 12; n++)

if(pos[ EndTab[n] ] != B) return 0;

return 1;

}//function

//делает перемещение

#define MakeMove\

pos[move.source] = 0;\

pos[move.dest] = B;\

PieceTab[index] = move.dest;

//отменяет ход

#define UnMakeMove\

pos[move.dest] = 0;\

pos[move.source] = В;\

PieceTab[index] = move.source;

/////// FORWARD //////////

void SimpleMove(Parg,int);

void Move(Parg,int);

void CallSearch(Parg,PMove);

void Search(Parg);

//простой ход на клетку

void SimpleMove(Parg arg,int index) {

int n;

TMove move;

move.source = PieceTab[index];

for(n =0; n < 4; n++) {

move.dest = move.source + DelTab[n];

if(pos[move.dest] = 0) {

MakeMove

CallSearch(arg,Smove);

UnMakeMove }

}

}//function

//прыгает через шашку

void Move(Parg arg, int index)

{

int n,tmp; TMove move;

for(n = 0; n < 4; n++) {

move.source = PieceTab[index];

move.dest = move.source + DelTab[n];

tmp = pos[move.dest];

if(tmp ==0 II tmp == F) continue;

move.dest += DelTabfn];

tmp = pos[move.dest];

if(tmp != 0) continue;

if(In(arg->set, move.dest)) continue;

//нашли — куда походить

Include(arg->set, move.dest);

MakeMove

CallSearch(arg,Smove);

Move(arg,index);

UnMakeMove

M Hot

}//function

//вызов просчета

void CallSearch(Parg arg, PMove move) (

Tai?g nextArg; nextArg.ply = arg->ply+l; nextArg.score = arg->score + (StTab[move->dest] – StTab[move->source]); Search(SnextArg); //если нашли лучший ход if(nextArg.max > arg->max) (

arg->max = nextArg.max; arg->bestMove.source = move->source;

arg->bestMove.dest = move->dest; }

}//function

//основная функция просчета void Search(Parg arg) (

int n;

if(arg->ply >= MAX_PLY) {

arg->max = arg->score;

return;

}

if (CheckEndO ) {

arg->max = INFINITY — arg->ply;

return;

}

arg->max = -INFINITY; //все перемещения на одну клетку for(п = 0; п < 12; п++) SimpleMove(arg,n); //все перемещения через шашки

for(п = 0; п < 12; п++) {

//очистим множество Clear(arg->set); //занесем стартовую координату Include(arg->set,PieceTab[n]);

Move(arg, n) ; }

}//function

// пример первого вызова /******++

Targ arg; int n;

memset(Sarg,0,sizeof(Targ)); Search(Sarg);

//изменение в позиции и в списке фигур for(п = 0; п < 12; п++)

if(PieceTab[n] == arg.bestMove.source) {

PieceTab[n] = arg.bestMove.dest; pos[arg.bestMove.source] = 0; pos[arg.bestMove.dest] = B;

break;

}

Литература:

Корнилов Е. Н.  Программирование шахмат и других логических игр. — СПб.: БХВ-Петербург, 2005. – 272 е.: ил.

По теме:

  • Комментарии