Богатырёв Андрей : другие произведения.

Игра в калах

"Самиздат": [Регистрация] [Найти] [Рейтинги] [Обсуждения] [Новинки] [Обзоры] [Помощь|Техвопросы]
Ссылки:


 Ваша оценка:
  • Аннотация:
    Правила игры стащены из старой "Науки и жизни". Программа - из какой-то книжки по Прологу, дописано и исправлено мной.

Калах

Играют двое. Вначале у каждого из игроков имеется по 36 мелких равноценных фишек - "камней", которые разложены поровну на 6 полях, пронумерованных слева направо. Поля соперников расположены друг против друга. Кроме того, каждый игрок имеет по специальному полю-накопителю, называемому "калах", и расположенному справа от шестого поля. Пусть B - владелец нижних полей (в нашем случае он и начинает игру), А - владелец верхних полей.

Калах A:
пуст

654321

Калах B:
пуст

666 666
666 666
123456

При очередном ходе играющий снимает с одного из своих полей все камни и распределяет их по одному на последующие поля, не пропуская ни одного, в порядке возрастания их номеров. Полем, следующим за шестым, считается свой калах. Далее камни распределяются по чужим полям (опять-таки в порядке возрастания их номеров), затем вновь по своим (чужой калах пропускается) и так далее, как бы совершая обход полей-лунок против часовой стрелки. Например, пойдя с поля номер 1 нижнего ряда, мы перейдём от начальной позиции:

Калах A:
0

654321

Калах B:
0

666 666
666 666
123456
к следующей: B ходит: 1

Калах A:
0

654321

Калах B:
1

666 666
077 777
123456
Если последний из распределяемых камней попал в свой калах, то игрок делает ещё один ход. Так, начавший игру в нашем примере должен пойти повторно: например со второго поля:

Калах A:
0

654321

Калах B:
1

666 666
077 777
123456
B ходит: 2

Калах A:
0

654321

Калах B:
2

666 677
008 888
123456
Ходы могут повторяться многократно: в партиях встречаются серии по 5-6 ходов!

Во всех остальных случаях очередь хода передаётся противнику. Это и произошло сейчас в начатой нами партии. Противник может ответить ходом с первого поля (как мы вскоре увидим, неудачным): A ходит: 1

Калах A:
0

654321

Калах B:
2

666 677
008 888
123456
получается:

Калах A:
1

654321

Калах B:
2

777 780
108 888
123456
В том случае, когда последний из распределяемых камней попадает на своё же пустое поле, а на противоположном (противолежащем) поле противника имеются камни, содержимое этих двух полей переносится в калах сделавшего ход ("съел"), а очередь хода передаётся противнику. В нашей показательной партии это правило позволяет владельцу нижних полей ходом с первого поля существенно пополнить свой калах: B ходит: 1

Калах A:
1

654321

Калах B:
2

777 780
108 888
123456

Калах A:
1

654321

Калах B:
2

777 780
018 888
123456
Ням-ням!

Калах A:
1

654321

Калах B:
10

707 780
008 888
123456
Если на полях игрока не остаётся ни одного камня, то все камни, находящиеся на полях противника, переносятся в калах противника, и игра на этом заканчивается. После такой операции у обоих игроков может оказаться в калахах по 36 камней. В таком случае игра считается закончившейся вничью. Во всех остальных случаях выигравшим считается тот, кто собрал в свой калах больше 36 камней.

Разумеется, чтобы определить победителя, можно не дожидаться опустошения чьих-либо полей: калах может только наполняться, и тот, кто набрал больше половины (36) камней, уже не уступит противнику своего первенства. Продолжать игру в таком случае стоит лишь для того, чтобы выразить исход партии точным счётом.


Программа игры на языке Пролог


writeln([]) :- nl.
writeln([X | Xtail]) :-
	writeq(X),
	writeln(Xtail).
puts([C|S]) :-
	put(C), puts(S).
puts([]) :- !.

/* ------------------------------------------------------------------ */
/*
	игра Калах

	play(Game) :- играть игру с именем Game.

	*------------------------------------------* *------*
	|L (7) | (6) | (5) | (4) | (3) | (2) | (1) | |      |
	|      |-----------------------------------* |      |
	|      |                                     |      |
	|      | *-----------------------------------|      |
	|      | | (1) | (2) | (3) | (4) | (5) | (6) | K (7)|
	*------* *------------------------------------------*

	E1 =:= E2  значения арифм. выражений равны
	E1 =\= E2  значения арифм. выражений различны

 */

/* ------------------------------------------------------------------ */
play(Game) :-
	initialize(Game, Position, Player),
	show_game(Position, Player),
	play(Position, Player, Result).

play(Position, Player, Winner) :-
	game_over(Position, Player, Winner),
	!,
	message( Winner ),
	show_game( Position, Player ).

play(Position, Player, Result) :-
	select_motion(Position, Player, Motion),
	motion(Motion, Position, PositionNew, real_motion),
	check_position(PositionNew),
	show_game(PositionNew, Player),
	next_player(Player, PlayerNew),  %% other_palyer
	!,
	play(PositionNew, PlayerNew, Result).

/* ------------------------------------------------------------------ */
/* Выбор хода с использованием минимаксной стратегии
 * и альфа-бета отсечение.
 */
select_motion(Position, computer, Motion) :-    %% ходит компьютер
	look_ahead(Depth),      %% просмотр вперед
	alpha_beta(Depth, Position, -40, 40, Motion, Value),

	puts( "*************************"), nl,
	puts( "*** Computer moves: "), writeq( Motion ), nl,
	puts( "*************************"), nl.

select_motion(Position, human, Motion) :- %% ходит человек
	repeat,
	nl,
	puts( "Please, do Your motion in form [2]. or [1,4]. : "),
	read(Motion),
	suitable(Position, Motion).       %% проверить корректность хода

/* ------------------------------------------------------------------ */
alpha_beta(0, Position, Alpha, Beta, Motion, Value) :-
	value(Position, Value).

alpha_beta(D, Position, Alpha, Beta, Motion, Value) :-
	D > 0,          %% depth
	setof(M, motion(Position, M), Motions),
	Alpha1 is   -Beta,
	Beta1  is   -Alpha,
	D1     is D - 1,
	estimate_and_select(Motions, Position, D1, Alpha1, Beta1,
			    nil, (Motion, Value)).

/* ------------------------------------------------------------------ */
/* оценить и выбрать */
estimate_and_select([Motion | Motions],
		    Position, D, Alpha, Beta, Record, BestMotion) :-
	motion(Motion, Position, Position1, virtual_motion),
	alpha_beta(D, Position1, Alpha, Beta, MotionX, Value),
	Value1 is  -Value,
	cutter(Motion, Value1, D, Alpha, Beta, Motions, Position,
	       Record, BestMotion),
	!.

estimate_and_select([], Position, D, Alpha, Beta, Motion, (Motion, Alpha)).

/* ------------------------------------------------------------------ */
/* отсечение */
cutter(Motion, Value, D, Alpha, Beta, Motions, Position, Record, (Motion, Value)) :-
       Value >= Beta,
       !.

cutter(Motion, Value, D, Alpha, Beta, Motions, Position, Record, BestMotion) :-
       Alpha < Value,
       Value < Beta,
       !,
       estimate_and_select(Motions, Position, D, Value, Beta, Motion, BestMotion).

cutter(Motion, Value, D, Alpha, Beta, Motions, Position, Record, BestMotion) :-
       Value =< Alpha,
       !,
       estimate_and_select(Motions, Position, D, Alpha, Beta,
			   Record, BestMotion).

/* ------------------------------------------------------------------ */
/* ход для генерации setof-ом */
motion(Board, [Sock | Socks]) :-
	member(Sock, [1,2,3,4,5,6]),       %% 6 лунок
	stones_in_socket(Sock, Board, N),
	continue_motion(N, Sock, Board, Socks).

motion(board([0,0,0,0,0,0], K, Ys, L), []).

/* ------------------------------------------------------------------ */
suitable(Board, []) :-
	!, fail.
suitable(Board, ListOfMotions) :-
	suitables(Board, ListOfMotions).

suitables(Board, [Sock | Socks]) :-
	0 < Sock,
	Sock < 7,

	stones_in_socket(Sock, Board, N),
	continue_motion(N, Sock, Board, Socks).

suitables(Board, []).

/* ------------------------------------------------------------------ */
/* камешки в лунке Sock */
stones_in_socket(Sock, board(Hs, K, Ys, L), Stones) :-
	n_th_member(Sock, Hs, Stones),
	Stones > 0.

/* ------------------------------------------------------------------ */
/* попытаться продолжить ход */
/* Stones - сколько камней из лунки Sock */

/* нельзя продолжить ход */
continue_motion(Stones, Sock, Board, []) :-
	Stones =\= (7 - Sock) mod 13,
	!.

/* если последний камень попадает в свой калах -
 * то можно сделать еще один ход */
continue_motion(Stones, Sock, Board, Ms) :-
	Stones =:= (7 - Sock) mod 13,
	!,
	%% распределить камешки
	spread_stones(Stones, Sock, Board, Board1),
	motion(Board1, Ms).

/* ------------------------------------------------------------------ */
/* Выполнение хода */
motion([N | Ns], Board, FinalBoard, Type) :-
	stones_in_socket(N, Board, Stones),
	spread_stones(Stones, N, Board, Board1),
	motion(Ns, Board1, FinalBoard, Type).

motion([], Board1, Board2, Type) :-
	exchange(Board1, Board2).  %% обмен

/* ------------------------------------------------------------------ */
/*
	spread_stones(Stones, Socket, Board, Board1) :-

	состояние Board1 - это результат распределения
	камней Stones из лунки Socket при текущем состоянии доски
	Board.

	Распределение производится в 2 этапа:
	распределение по своим лункам
		затем
	распределение по лункам противника
 */
spread_stones(Stones, Socket, Board, FinalBoard) :-
	spread_my_sockets(Stones, Socket, Board, Board1, Stones1),
	spread_his_sockets(Stones1, Board1, FinalBoard).

/* ----------------------------------------------------------------- */
spread_stones_around(Stones, Board, FinalBoard) :-
	/* начиная с лунки номер 0 */
	spread_my_sockets_around(Stones, Board, Board1, Stones1),
	spread_his_sockets(Stones1, Board1, FinalBoard).

/* ------------------------------------------------------------------ */
/* распределить по моим лункам */
/* N - номер лунки из которой делается ход,
 * Stones - число камней в ней
 */
spread_my_sockets(Stones, N, board(Hs,  K,  Ys, L),
			     board(Hs1, K1, Ys, L),
			     Stones1) :-
/* последний камень попадает на сторону соперника */
	Stones > 7 - N,
	!,
	take_and_spread(N, Stones, Hs, Hs1),    %% взять и распределить
	K1      is K + 1,
	Stones1 is Stones - ( 7 - N ).

spread_my_sockets(Stones, N, board(Hs, K, Ys, L),
			     Board,
			     0) :-
/* последний камень ложится на моей же стороне или в мой калах */
	take_and_spread(N, Stones, Hs, Hs1),
	check_grab(N, Stones, Hs1, Hs2, Ys, Ys1, HowMany),
	    %% проверить захват (съедение).
	modify_kalah(HowMany, Stones, N, K, K1),
	check_for_finish(board(Hs2, K1, Ys1, L), Board).


/* ------------------------------------------------------------------ */

/* распределить по моим лункам из последнего поля противника (N==0) */
spread_my_sockets_around(Stones, board(Hs,  K,  Ys, L),
			     board(Hs1, K1, Ys, L),
			     Stones1) :-
/* последний камень попадает на сторону соперника */
	Stones > 7,
	!,
	spread(6, Hs, Hs1),
	K1      is K + 1,
	Stones1 is Stones - 7.

spread_my_sockets_around(Stones, board(Hs, K, Ys, L),
			     Board,
			     0) :-
/* последний камень ложится на моей же стороне или в мой калах */
	spread(Stones, Hs, Hs1),
	check_grab(0, Stones, Hs1, Hs2, Ys, Ys1, HowMany),
	    %% проверить захват
	modify_kalah(HowMany, Stones, 0, K, K1),
	check_for_finish(board(Hs2, K1, Ys1, L), Board).

/* ------------------------------------------------------------------ */
/* проверить захват (съедение камней) */
check_grab(N, Stones, Hs, Hs1, Ys, Ys1, HowMany) :-
	FinalSocket    is N + Stones,
	FinalSocket < 7,        /* калах - номер 7 - не проверять */
	ContrarySocket is 7 - FinalSocket,

	/* если моя лунка, в которую попадает последний камень,
	   ПУСТА (то есть в ней оказался ЕДИНСТВЕННЫЙ только что
	   положенный в нее камень) ...
	 */
	n_th_member(FinalSocket, Hs, H),
	H =:= 1,  %% the only rock (the rock only)

	/* а противоположная лунка соперника - не пуста ... */
	n_th_member(ContrarySocket, Ys, Y),
	Y > 0,

	!,
	/* то съесть камни из лунки соперника в мой калах
	 * (и свой камень тоже)
	 */
	n_substitution(ContrarySocket, Ys, 0, Ys1),
	n_substitution(FinalSocket,    Hs, 0, Hs1),
	HowMany is Y + 1.

check_grab(N, Stones, Hs, Hs, Ys, Ys, 0) :-
	!.

/* ------------------------------------------------------------------ */
/* проверить на окончание */
check_for_finish(board(Hs, K, Ys, L),
		 board(Hs, K, Hs, L1)) :-
	is_zero(Hs),
	!,
	sumlist(Ys, YsSum),
	L1 is L + YsSum.

check_for_finish(board(Hs, K,  Ys, L),
		 board(Ys, K1, Ys, L)) :-
	is_zero(Ys),
	!,
	sumlist(Hs, HsSum),
	K1 is K + HsSum.

check_for_finish(Board, Board) :-
	!.

/* ------------------------------------------------------------------ */
/* модифицировать калах */

/* никого не съели: 0. Калах неизменен */
modify_kalah(0, Stones, N, K, K) :-
	Stones < 7 - N,
	!.

/* никого не съели, но последний камень угодил в калах */
modify_kalah(0, Stones, N, K, K1) :-
	Stones =:= 7 - N,
	!,
	K1 is K + 1.

/* что-то съели: HowMany камней в калах */
modify_kalah(HowMany, Stones, N, K, K1) :-
	HowMany > 0,
	!,
	K1 is K + HowMany.

/* ------------------------------------------------------------------ */
/* распределить по лункам соперника */
spread_his_sockets(0, Board, Board) :-
	!.

spread_his_sockets(Stones, board(Hs, K, Ys,  L),
			   board(Hs, K, Ys1, L)) :-
	1 =< Stones,
	Stones =< 6,
	not_zero(Hs),
	!,
	spread(Stones, Ys, Ys1).        %% распределить

spread_his_sockets(Stones, board(Hs, K, Ys,  L),
			   Board) :-
	Stones > 6,
	!,
	spread(6, Ys, Ys1),
	Stones1   is Stones - 6,
	spread_stones_around(Stones1, board(Hs, K, Ys1, L), Board).

spread_his_sockets(Stones, board(Hs, K, Ys, L),
			   board(Hs, K, Hs, L1)) :-
	is_zero(Hs),
	!,
	sumlist(Ys, YsSum),
	L1 is Stones + YsSum + L.

/* ------------------------------------------------------------------ */
/* распределение камней на низком уровне */
/* N - число камней, K - номер лунки */
/*
    [A1, ..., Ak-1, Bk, Bk+1    ,  ..., Bk+n    ,  Ak+n+1, ..., Am ] -->
    [A1, ..., Ak-1, 0 , Bk+1 + 1,  ..., Bk+n + 1,  Ak+n+1, ..., Am ]
*/
take_and_spread(1, N, [H | Hs], [0 | Hs1]) :-
	!,
	spread(N, Hs, Hs1).

take_and_spread(K, N, [H | Hs], [H | Hs1]) :-
	K > 1,
	!,
	K1 is K - 1,
	take_and_spread(K1, N, Hs, Hs1).

/* ------------------------------------------------------------------ */
/*
    [A1    , ..., An    , Bn+1, ..., Bm ] -->
    [A1 + 1, ..., An + 1, Bn+1, ..., Bm ]
*/
spread(0, Hs, Hs) :-
	!.

spread(N, [H | Hs], [H1 | Hs1]) :-
	N > 0,
	!,
	N1 is N - 1,
	H1 is H + 1,
	spread(N1, Hs, Hs1).

spread(N, [], []) :-
	!.

/* ------------------------------------------------------------------ */
/*
 * Оценочная функция
 */

value(board(H, K, Y, L), Value) :-
	Value is K - L.

/* ------------------------------------------------------------------ */
/* Проверка окончания игры */
game_over(board(Hs, N, Hs, N), Player, draw) :-
	things(K),      %% штуки
	N =:=  6 * K,
	/* is_zero(Hs), */
	!.

game_over(board(H, K, Y, L), Player, Player) :-
	things(N),
	K > 6 * N,
	!.

game_over(board(H, K, Y, L), Player, EnemyPlayer) :-
	things(N),
	L > 6 * N,
	next_player(Player, EnemyPlayer).  %% следующий партнер

/* ------------------------------------------------------------------ */
/* сообщения о победителе */
message(human) :-
	puts( "Congratulations! You won!"), nl.

message(computer) :-
	puts( "Sorry, but I won!"), nl.

message(draw) :-
	puts( "Draw score" ), nl.

/* ------------------------------------------------------------------ */
/* Всякие вспомогательные средства */

/* n_th_member(N, L, Y):
   Y = число камней в N-ом гнезде списка L
*/
n_th_member(N, [H | Hs], K) :-
	N > 1,
	!,
	N1 is N - 1,
	n_th_member(N1, Hs, K).

n_th_member(1, [H | Hs], H).

/* ------------------------------------------------------------------ */
/* n_substitution(N, L, Y, LNew):
    LNew = список L, где число камней в N-ом гнезде
	   заменено на число Y.
*/
n_substitution(1, [X | Xs], Y, [Y | Xs]) :-
	!.

n_substitution(N, [X | Xs], Y, [X | Xs1]) :-
	N > 1,
	!,
	N1 is N - 1,
	n_substitution(N1, Xs, Y, Xs1).

/* ------------------------------------------------------------------ */
check_position( board(Hs, K, Ys, L) ) :-
	sumlist(Hs, Hsum),
	sumlist(Ys, Ysum),
	Total is Hsum + Ysum + K + L,
	things(N),
	Total =:= 2 * 6 * N,
	!.
check_position( board(Hs, K, Ys, L) ) :-
	puts( "Bad position !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!" ), nl.

/* ------------------------------------------------------------------ */
/* другой игрок */
next_player(computer, human).
next_player(human,    computer).

/* ------------------------------------------------------------------ */
exchange(board(Hs, K, Ys, L),
	 board(Ys, L, Hs, K)).

/* ------------------------------------------------------------------ */
show_game(Position, human) :-
	demo(Position).

show_game(Position, computer) :-
	exchange(Position, Position1),
	demo(Position1).

demo(board(H, K, Y, L)) :-
	show_stones(H, upper),
	show_kalahs(K, L),
	show_stones(Y, lower).

show_stones(H, upper) :-
	order(Ord),
	reverse(Ord, OrdRev),
	show_order(OrdRev),
	nl, write('-------------------------------------'),

	nl, tab(5),
	reverse(H, HR),
	show_sockets(HR),
	nl.

show_stones(H, lower) :-
	nl, tab(5),
	show_sockets(H),
	nl, write('-------------------------------------'),

	order(Ord),
	show_order(Ord),
	nl.

show_order(Ord) :-
	nl, tab(5),
	show_sockets(Ord).

show_sockets([H | Hs]) :-
	show_heap(H),
	show_sockets(Hs).

show_sockets([]) :-
	!.

show_heap(N) :-
	N < 10,
	write(N),
	tab(4).

show_heap(N) :-
	N >= 10,
	write(N),
	tab(3).

show_kalahs(K, L) :-
	write(K),
	tab(34),
	write(L).       %% , nl  было еще тут.

/* ------------------------------------------------------------------ */
eat(Stones) :-
	Stones =:= 0,
	!.
eat(Stones) :-
	puts( "eat "),
	write(Stones),
	puts( " stones."),
	nl.

/* ------------------------------------------------------------------ */
is_zero([0,0,0,0,0,0]).
not_zero(Hs) :-
	Hs \== [0,0,0,0,0,0].

/* ------------------------------------------------------------------ */
member(X, [X | Xs]).
member(X, [Y | Ys]) :-
	member(X, Ys).

/* ------------------------------------------------------------------ */
reverse(List, ListNew) :-
	reverse(List, [], ListNew).
reverse([X | Xs], Accum, Ys) :-
	reverse(Xs, [X | Accum], Ys).
reverse([], Ys, Ys).

/* ------------------------------------------------------------------ */
/* сумма элементов списка */
sumlist([I | Is], Sum) :-
	sumlist(Is, IsSum),
	Sum is I + IsSum.
sumlist([], 0).

/* ------------------------------------------------------------------ */
/* длина списка */
llength([Head | List], Len) :-
	llength(List, LenOfList),
	Len is LenOfList + 1.
llength([], 0).

/* ------------------------------------------------------------------ */
/* инициализация */
look_ahead(2).  %% просмотр на 2 полухода вперёд. Рекомендую 3, но это гораздо дольше.

initialize(kalah, board( [N,N,N,N,N,N], 0,
			 [N,N,N,N,N,N], 0), human) :-
	things(N).
things(6).      %% по 6 камней в лунке.
order([1,2,3,4,5,6]).

/* ------------------------------------------------------------------ */
:- puts( "Now type   'go.'  Then enjoy."), nl.
go :- play(kalah).

Программа на Си

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


Makefile

CFLAGS=-O2 -DDEBUG

kalah: kalah.o alphabeta.o
	$(CC) -o kalah kalah.o alphabeta.o

kalah.o: kalah.c kalah.h
	$(CC) $(CFLAGS) -c kalah.c

alphabeta.o: alphabeta.c kalah.h
	$(CC) $(CFLAGS) -c alphabeta.c

test: kalah
	kalah -e -e -auto -human -r -no-rand -depth 7 > Log1
	kalah    -e -auto -human -r -no-rand -depth 7 > Log2
	kalah       -auto -human -r -no-rand -depth 7 > Log3


kalah.h

Следовало бы назвать "socket" (гнездо) "bucket" (ведро) или "basket" (корзина) или даже "cup" (лунка). Но уж как назвал...

#include <stdio.h>
#include <stdarg.h>
#include <values.h>

#define NSOCKETS	6
#define NSTONES		NSOCKETS

typedef struct player {
	short socket[NSOCKETS];
	short kalah;
} Player;

#define ALLSTONES	(NSOCKETS*NSTONES*2)
#define HALF_ALLSTONES	(NSOCKETS*NSTONES)
#define INFINITY	(MAXINT-1)

#define TAKEBACK	(-12345)

typedef struct board {
	Player player[2];
	char who;		/* Who has to make a turn in this position */
	char again;
	char move;
	char final;		/* Is a leaf (final) position */
	char level;
	char step_number;
	int serial;		/* Unique serial number of this board */
	struct board *prev, *next;
} Board;

/* Who values */
#define NONE	(-1)
#define HUMAN	0
#define COMPU	1

/* Bitmap set */
#define SET		unsigned int
#define CLEARSET(x)	(x)=0
#define ADDSET(x, n)	(x) |= (1 << (n))
#define DELSET(x, n)	(x) &= ~(1 << (n))
#define ISINSET(x, n)	((x) & (1 << (n)))

#define MAX(a, b)	(((a) < (b)) ? (b) : (a))
#define MIN(a, b)	(((a) < (b)) ? (a) : (b))
#define SQR(x)		((x)*(x))
#define FIELDLEN	4
#define FIELDFMT	" %2d "

extern int debug;
extern int report;

extern int random_selections;

void whoprintf(int who, char *fmt, ...);
int VALUE(Board *b);
int DIFF(Board *b);
void white(int y);
void line(int y);
void shift(Board *b);
void printRuler(int kalah_too);
void printCell(int x);
void printIndices(int who);
void printPlayer(Board *b, int who);
void printBoard(Board *b);
void checkConsistency(Board *b);
void checkFinalNode(Board *b);
int  checkOnlyTurn(Board *b);
int legalTurn(Board *b, int from);
Board *makeTurn(Board *b, int from);
int AlphaBeta      (Board *position, int depth, int thisdepth, int alpha, int beta);
int MiniMaxTopLevel(Board *position, int depth, int thisdepth, int *bestMotion);
Board *takeBack(Board *b, int who);
void saveGame(Board *b);
int computeTurn(Board *b);
int getAnswer(Board *b);
int whoFirst();
void gameOver(Board *b);
int main(int ac, char *av[]);

kalah.c
#include "kalah.h"

int Depth     = 6;	/* Search depth (half-motions) 	*/
int verbose   = 1;
int serial    = 1;
int automatic = 0;
int manual    = 0;
int estim     = 0;	/* Kind of the estimation function */
int randomize = 1;	/* Use srand() */

/* For debugging	*/
int debug   = 0;
int report  = 0;
/* =================================================================== */
void whoprintf(int who, char *fmt, ...){
	va_list args;

	if(*fmt == '@'){
		fmt++;
		printf("\t");
	}
	printf("%s ", who == HUMAN ? "HUMAN" : "COMPUTER");
	va_start(args, fmt);
	vprintf(fmt, args);
	va_end(args);
}

/*
		6         1
	+----+----+----+----+----+
	| NN | NN | .. | NN |    |
	+    +----+----+----+    +
	|    | NN | .. | NN | NN |
	+----+----+----+----+----+
		1         6
*/
void white(int y){
	int x;
	for(x=0; x < y; x++) putchar(' ');
}
void line(int y){
	int x;
	for(x=0; x < y; x++) putchar('-');
}
void shift(Board *b){
	int x;
	for(x=0; x < b->level; x++)
		printf(".  ");
}
void printRuler(int kalah_too){
	int x;
	int ncells = (kalah_too ? NSOCKETS+2 : NSOCKETS);

	putchar(kalah_too ? '+' : '|');
	if(!kalah_too){
		white(FIELDLEN);
		putchar('+');
	}
	for(x=0; x < ncells; x++){
		line(FIELDLEN);
		putchar('+');
	}
	if(!kalah_too){
		white(FIELDLEN);
		putchar('|');
	}
	putchar('\n');
}
void printCell(int x){
	printf(FIELDFMT, x);
}
void printIndices(int who){
	int x, y;

	putchar(' ');
	white(FIELDLEN);
	putchar(' ');
	for(x=0; x < NSOCKETS; x++){
		y = (who == COMPU) ? NSOCKETS-1-x : x;
		printCell(y+1);
		putchar(' ');
	}
	putchar('\n');
}
void printPlayer(Board *b, int who){
	int x, y;

	putchar('|');

	if(who == COMPU) printCell(b->player[who].kalah);
	else		 white(FIELDLEN);

	putchar('|');
	for(x=0; x < NSOCKETS; x++){
		int indx = (who == HUMAN) ? x : (NSOCKETS-1-x);
		printCell(b->player[who].socket[indx]);
		putchar('|');
	}
	if(who == HUMAN) printCell(b->player[who].kalah);
	else		 white(FIELDLEN);

	putchar('|');
	whoprintf(who, "@%s\n", b->who == who ? "<== TURN":"");
}
void printBoard(Board *b){
	putchar('\n');
	if(debug){
		shift(b); printf("BOARD#%d\n", b->serial);
	}
	shift(b); printIndices(COMPU);
	shift(b); printRuler(1);
	shift(b); printPlayer(b, COMPU);
	shift(b); printRuler(0);
	shift(b); printPlayer(b, HUMAN);
	shift(b); printRuler(1);
	shift(b); printIndices(HUMAN);
	putchar('\n');
}
/* =================================================================== */
int DIFF(Board *b){
	return    b->player[HUMAN].kalah - b->player[COMPU].kalah;
}
int VALUE(Board *b){
	switch(estim){
	default:
	case 0:		return SQR(b->player[HUMAN].kalah) - SQR(b->player[COMPU].kalah);
	case 1:		return DIFF(b);
	case 2:		return b->player[HUMAN].kalah;
	}
}
Board *initBoard(int who_first){
	int x;
	Board *b = (Board *) calloc(1, sizeof(Board));

	b->player[HUMAN].kalah = 0;
	b->player[COMPU].kalah = 0;
	b->who = who_first;
	b->again = 0;
	b->move = NONE;
	b->prev = NULL;
	b->next = NULL;
	b->final = 0;
	b->serial = serial++;
	b->step_number = 1;
	for(x=0; x < NSOCKETS; x++){
		b->player[HUMAN].socket[x] = NSTONES;
		b->player[COMPU].socket[x] = NSTONES;
	}
	return b;
}
/* =================================================================== */
/* Test if this is the final (or LEAF) node, compute the score	*/
void checkFinalNode(Board *b){
	int x;
	int sumH, sumC;

	/* If all someone's fields are empty, collect all stones
	 * into other kalah and stop.
	 */

	b->final = 0;

	for(sumH = sumC = x = 0; x < NSOCKETS; x++){
		sumH += b->player[HUMAN].socket[x];
		sumC += b->player[COMPU].socket[x];
	}
	if(sumH == 0){
		b->player[COMPU].kalah += sumC;
		for(x=0; x < NSOCKETS; x++)
			b->player[COMPU].socket[x] = 0;
		if(verbose) printf("HUMAN HAS NO MORE MOVES. Collecting stones.\n");
		b->final = 1;
		b->who   = NONE;
	}
	if(sumC == 0){
		b->player[HUMAN].kalah += sumH;
		for(x=0; x < NSOCKETS; x++)
			b->player[HUMAN].socket[x] = 0;
		if(verbose) printf("COMPUTER HAS NO MORE MOVES. Collecting stones.\n");
		b->final = 1;
		b->who   = NONE;
	}
}
void checkConsistency(Board *b){
	int x;
	int sumH, sumC, sum;

	/* CHECK THE CONSISTENCY OF THE BOARD */
	sum = b->player[HUMAN].kalah + b->player[COMPU].kalah;
	for(sumH = sumC = x = 0; x < NSOCKETS; x++){
		sumH += b->player[HUMAN].socket[x];
		sumC += b->player[COMPU].socket[x];
	}
	sum += sumH + sumC;
	if(sum != ALLSTONES){
		printBoard(b);
		printf("Bad position: %d\n", sum);
		exit(1);
	}
}
int checkOnlyTurn(Board *b){
	int x;
	int nonzero = 0;
	int which_one = NONE;

	for(x=0; x < NSOCKETS; x++)
		if(b->player[b->who].socket[x] != 0){
			nonzero++;
			which_one = x;
		}

	if(nonzero == 1){	/* only one move exists */
		return which_one;
	}
	return NONE;
}
/* =================================================================== */
int legalTurn(Board *b, int from){
	if(from < 0 || from >= NSOCKETS){
		whoprintf(b->who, "tries to use illegal cell number: %d\n", from+1);
		return 0;
	}
	if(b->player[b->who].socket[from] == 0){
		whoprintf(b->who, "tries to move from empty cell: %d\n", from+1);
		return 0;
	}
	return 1;	/* is legal */
}
Board *makeTurn(Board *b, int from){
	register int nstones;
	register int x;
	int side;
	int who = b->who;
	Board *ptr = (Board *) calloc(1, sizeof(Board));

	if(ptr == NULL){
		printf("Cannot allocate memory\n");
		exit(1);
	}
	
	/* Copy */
	*ptr = *b;
	ptr->prev = b;		/* parent position */
	b->next = ptr;

	ptr->move = from;

	/* Now move */
	if(from < 0 || from >= NSOCKETS){
		printf("bad turn: %d at %d\n", who, from+1);
		exit(1);
	}
	nstones = b->player[who].socket[from];
	if(nstones == 0){
		printf("zero turn: %d at %d\n", who, from+1);
		exit(1);
	}
	/* Stones are taken away */
	ptr->player[who].socket[from] = 0;
	side = who;
	x = from+1;

	ptr->who = !who;	/* Other player */
	ptr->again = 0;
	ptr->level = 0;
	ptr->serial = serial++;
	ptr->step_number = b->step_number+1;

	for(;;){
		/* spread across the remaining sockets */
		if(x >= NSOCKETS){
			if(side == who){
				/* put stone into player's kalah */
				ptr->player[who].kalah++;
				nstones--;
				if(nstones == 0){
					/* If the last stone came into our own
					 * kalah, we can make yet another move
					 */
					ptr->who = who;
					ptr->again = 1;
					goto done;
				}
			}
			/* switch the side of the board */
			side = !side;
			x = 0;
			continue;
		}
		for( ; x < NSOCKETS; x++){
			ptr->player[side].socket[x]++;
			nstones--;
			if(nstones == 0){
				int eat;

/* check if we eat the enemy's cell:
	1) Last stone is put into my empty cell AND
	2) the contrary enemy's cell is not empty.
*/
if(side == who &&    ptr->player[who].socket[x] == 1 	    &&
		(eat=ptr->player[!who].socket[NSOCKETS-1-x]) != 0) {
	/* Previously 0 was there */

	if(verbose){
		whoprintf(who, "EATS <1> in his cell #%d and <%d> in your cell #%d\n",
		x+1, eat, NSOCKETS-1-x+1);
		printBoard(ptr);
	}
	/* Eat my own stone */
	ptr->player[who].socket[x] = 0;
	ptr->player[who].kalah++;

	/* Eat enemy's stones */
	ptr->player[!who].socket[NSOCKETS-1-x] = 0;
	ptr->player[who].kalah += eat;
}
				goto done;
			}
		}
	}
done:
	/* All stones are distributed */
	checkFinalNode(ptr);
#ifdef DEBUG
	checkConsistency(ptr);
#endif
	return ptr;
}
/* =================================================================== */
Board *takeBack(Board *b, int who){
	Board *ptr, *pptr;

	printf("\nTAKING THE MOVE BACK...\n\n");

	for(ptr = b->prev; ptr; ptr=ptr->prev){
		if(ptr->who == who)
			break;
	}
	if(ptr == NULL){
		printf("There is no previous motion.\n");
		return b;
	}
	/* Free the subtree */
	for(pptr=b;  pptr != ptr;){
		Board *up;
		up = pptr->prev;
		free(pptr);
		pptr = up;
	}
	ptr->next = NULL;
	return ptr;
}
void saveGame(Board *b){
	FILE *fp;
	Board *bprev = b;
	char buf[128];

	sprintf(buf, "games-%dx%d.sav", NSOCKETS, NSTONES);

	if((fp = fopen(buf, "a")) == NULL)
		return;
	for(;b; bprev=b, b=b->next){
		fprintf(fp, "%c%d ", b->who ? 'C' : 'H',
			             b->move == NONE ? 0 : b->move+1);
	}
	fprintf(fp, "[%d:%d]\n", bprev->player[HUMAN].kalah, 
				 bprev->player[COMPU].kalah);
	fclose(fp);
}
#define LENGTH 128
void xgets(char *buf){
	char *s;
	fgets(buf, LENGTH-1, stdin);
	for(s=buf; *s; s++)
		if(*s == '\n' || *s == '\r')
			*s = '\0';
}
/* Returns the best turn from the position "b" */
int computeTurn(Board *b){
	int turn;	/* motion */
	int value;

	verbose = 0;
	whoprintf(b->who, "THINKING... "); fflush(stdout);

		value = MiniMaxTopLevel(b, Depth, 0, &turn);

	printf("\n");
	verbose = 1;

	/* human counts from 1, computer from 0 */
	whoprintf(b->who, "(%d) MOVES%s: %d\n\n",
		b->step_number, b->again ? " again" : "", turn+1);

	if(! legalTurn(b, turn))
		exit(1);

	return turn;
}
int getAnswer(Board *b){
	char answer[LENGTH];
	int turn;

	for(;;){
		whoprintf(b->who, "(%d) MOVES%s: ",
			b->step_number, b->again ? " again" : "");
		fflush(stdout);
		xgets(answer);
		if(!strcmp(answer, "t")){	/* TAKEBACK */
			return TAKEBACK;
		}
		if(!strcmp(answer, "h")){	/* HINT */
			return computeTurn(b);
		}
		if(!strcmp(answer, "a")){	/* AUTOMATIC */
			automatic++;
			manual = 0;
			return computeTurn(b);
		}
		if(!strcmp(answer, "+")){	/* DEPTH++ */
			Depth++;
			printf("Search depth is now %d\n", Depth);
			continue;
		}
		turn = atoi(answer);
		/* human counts from 1, computer from 0 */
		turn--;
		if(legalTurn(b, turn)){
			break;
		}
		printf("TRY AGAIN\n\n");
		printBoard(b);
	}
	return turn;
}
int whoFirst(){
	char answer[LENGTH];
	int first_player;

	for(;;){
		printf("Who moves first? C(omputer) or H(uman): "); fflush(stdout);
		xgets(answer);

		if(*answer == 'c' || *answer == 'C'){
			first_player = COMPU; break;	}
		else if(*answer == 'h' || *answer == 'H'){
			first_player = HUMAN; break;	}
	}
	return first_player;
}
void gameOver(Board *b){
	int value = DIFF(b);
	printf("GAME OVER.\nScore:\tHUMAN=%d : COMPUTER=%d\t(%d)\n\n",
		b->player[HUMAN].kalah, b->player[COMPU].kalah, value);

	if(value > 0)		printf("HUMAN won.\n");
	else if(value < 0)	printf("COMPUTER won.\n");
	else 			printf("DRAW.\n");

	if(report) printf("\n%d random decisions were made.\n", random_selections);
}
int main(int ac, char *av[]){
	Board *b, *root;
	int turn;
	int firstPlayer = NONE;

	while(av[1] && av[1][0] == '-'){
		if(!strcmp(av[1], "-d")){
			debug++; report++; av++; ac--; continue;
		}
		if(!strcmp(av[1], "-e")){
			estim++; av++; ac--; continue;
		}
		if(!strcmp(av[1], "-r")){
			report++; av++; ac--; continue;
		}
		if(!strcmp(av[1], "-auto")){
			automatic++; av++; ac--; continue;
		}
		if(!strcmp(av[1], "-human")){
			firstPlayer = HUMAN; av++; ac--; continue;
		}
		if(!strcmp(av[1], "-computer")){
			firstPlayer = COMPU; av++; ac--; continue;
		}
		if(!strcmp(av[1], "-manual")){
			manual++; av++; ac--; continue;
		}
		if(!strcmp(av[1], "-no-rand")){
			randomize=0; av++; ac--; continue;
		}
		if(!strcmp(av[1], "-depth") && av[2]){
			Depth = atoi(av[2]); av += 2; ac -= 2; continue;
		}
		printf("Unknown switch: %s\n", av[1]);
		exit(1);
	}

	if(randomize)
		srand(time(NULL));
	if(firstPlayer == NONE)
		firstPlayer = whoFirst();
	root = b = initBoard(firstPlayer);

	while(b){
		printBoard(b);

		if(b->final)		/* Game Over */
			break;

		turn = checkOnlyTurn(b);

		if(turn != NONE){	/* there is only one possible motion */
			whoprintf(b->who, "has only one move: %d. Doing it.\n", turn+1);
			whoprintf(b->who, "(%d) MOVES%s: %d\n\n",
				b->step_number, b->again ? " again" : "", turn+1);

		} else if(!manual && (b->who == COMPU || automatic)){
			turn = computeTurn(b);
		} else {
			turn = getAnswer(b);
			if(turn == TAKEBACK){
				b = takeBack(b, b->who);
				continue;	/* while(b) */
			}
		}
		b = makeTurn(b, turn);
	}
	gameOver(b);
	saveGame(root);
	return 0;
}

alphabeta.c
#include "kalah.h"

int positions_estimated;
int random_selections;

#define DEBUG_ENTER		if(debug){	\
	shift(position); \
	printf("ENTER BOARD#%d depth=%d alpha=%d beta=%d forWhom=%s\n", position->serial,\
		depth, alpha, beta,\
		position->who == HUMAN ? "HUMAN" : "COMPUTER");\
	position->level = thisdepth; \
	printBoard(position);\
}
#define DEBUG_AB_EXIT		if(debug){	\
	shift(position); \
	printf("RETURN BOARD#%d VALUE=%d\n\n", position->serial,\
		position->who == HUMAN ? maxValue : minValue); \
	position->level = 0;	\
}
#define DEBUG_EXIT		if(debug){	\
	shift(position); \
	printf("RETURN BOARD#%d best=%d VALUE=%d\n\n", position->serial, best == NONE ? 0 : best+1,\
		position->who == HUMAN ? maxValue : minValue); \
	printBoard(brd);	\
	position->level = 0;	\
}

#define DEBUG_LEAF		if(debug){	\
	shift(position); \
	printf("RETURN BOARD#%d LEAF VALUE=%d\n\n", position->serial, value); \
	position->level = 0;	\
}

#define DEBUG_TURN		if(debug){	\
	shift(position); \
	whoprintf(position->who, "turn=#%d\n", x+1); \
}

#define DEBUG_NEWPOSITION	if(debug){	\
	brd->level = thisdepth+1; \
	printBoard(brd);	\
}

#define DEBUG_ALPHABETA		if(debug){	\
	shift(position); \
	printf("GOT x=#%d value=%d max=%d min=%d\n", x+1, value, maxValue, minValue); \
}

#define DEBUG_ALPHA_CUT		if(debug){	\
	shift(position); \
	printf("ALPHA CUT: min_%d <= a_%d\n", minValue, alpha);	\
}
#define DEBUG_BETA_CUT		if(debug){	\
	shift(position); \
	printf("BETA CUT: b_%d <= max_%d\n", beta, maxValue);	\
}
#define DEBUG_BEST		if(debug){  \
	shift(position); \
	printf("BEST: max=%d min=%d value=%d best=#%d\n", maxValue, minValue, value, x+1);\
}

/* Return VALUE of the position and the best motion from it */
int MiniMaxTopLevel(Board *position, int depth, int thisdepth, int *bestMotion){
	register x, best;
	int value, count;
	int minValue, maxValue;
	Board *brd;
	SET motions, best_motions;

	if(depth == 0 || position->final){	// Leaf node for this search
		printf("The very notion of a 'motion' is undefined for the leaf position\n");
		*bestMotion = NONE;
		exit(33);
		return value;
	}

	CLEARSET(motions);
	CLEARSET(best_motions);

	/* Look thru all possible turns */
	for(x=0; x < NSOCKETS; x++){
		if(position->player[position->who].socket[x] == 0)	/* No motion */
			continue;
		ADDSET(motions, x);
	}

	/* Estimation loop */

	minValue = +INFINITY;
	maxValue = -INFINITY;
	brd = NULL;

	if(report) printf("Looking for the %s\n", position->who == HUMAN ? "MAX" : "MIN");

	/* Indeed, the score for each possible move
	 * can be estimated in a separate thread.
	 */

	for(x=0; x < NSOCKETS; x++){
		if(!ISINSET(motions, x))
			continue;

		/* Generate new position (doing the turn) */
		if(brd) free(brd);	/* kill old */
		brd = makeTurn(position, x);

		switch(position->who){

		case HUMAN:	/* MAX node */

			positions_estimated = 0;
			if(brd->who != position->who){	/* Opponent's turn (Computer's) */
				value =   AlphaBeta(brd, depth-1, thisdepth+1, -INFINITY, +INFINITY);
			} else {			/* Human's turn again */
				value =   AlphaBeta(brd, depth,   thisdepth+1, -INFINITY, +INFINITY);
			}
			if(report) printf("For move #%d positions seen=%09d, value=%d\n",
					x+1, positions_estimated, value);

			if(value == maxValue){
				ADDSET(best_motions, x);	/* yet another best */
			}
			if(value > maxValue){
				maxValue = value;
				CLEARSET(best_motions);
				ADDSET(best_motions, x);
			}
			break;

		case COMPU:	/* MIN node */

			positions_estimated = 0;
			if(brd->who != position->who){	/* Human's turn */
				value =   AlphaBeta(brd, depth-1, thisdepth+1, -INFINITY, +INFINITY);
			} else {			/* Computer's turn again */
				value =   AlphaBeta(brd, depth,   thisdepth+1, -INFINITY, +INFINITY);
			}
			if(report) printf("For move #%d positions seen=%09d, value=%d\n",
					x+1, positions_estimated, value);

			if(value == minValue){
				ADDSET(best_motions, x);
			}
			if(value < minValue){
				minValue = value;
				CLEARSET(best_motions);
				ADDSET(best_motions, x);
			}
			break;
		}
	}
	if(brd) free(brd);	/* kill old */
	position->next = NULL;

	/* Analyse the best motions set */
	best = NONE;
	for(count=x=0; x < NSOCKETS; x++){
		if(ISINSET(best_motions, x)){
			count++;
			best = x;
		}
	}

	if(count > 1){
		/* There are several "best" motions */
		if(report){
			printf("There are several best choices:");
			for(x=0; x < NSOCKETS; x++){
				if(ISINSET(best_motions, x))
					printf(" #%d", x+1);
			}
			printf("\n");
		}

		/* Select the random turn among the best ones */
		if(report) printf("Making random selection among them.\n");
		value = rand() % count;		/* 0...count-1 */
		random_selections++;
		for(count=x=0; x < NSOCKETS; x++){
			if(ISINSET(best_motions, x)){
				if(count == value){
					best = x;
					break;
				}
				count++;
			}
		}

	} else if(count == 0){
		printf("There is NO BEST MOTION - ???\n");
		exit(111);
	}
	if(report) printf("Best motion is #%d with value %d\n", best+1,
			(position->who == HUMAN) ? maxValue : minValue);

	if(bestMotion) *bestMotion = best;
	return (position->who == HUMAN) ? maxValue : minValue;
}

/* Return Value of the position */
int AlphaBeta(Board *position, int depth, int thisdepth, int alpha, int beta){
	register x;
	int value;
	int minValue, maxValue;
	Board *brd;
	SET motions;

	DEBUG_ENTER

	if(depth == 0 || position->final){	// Leaf node for this search
		value = VALUE(position);
		DEBUG_LEAF
		return value;
	}

	CLEARSET(motions);

	/* Look thru all possible turns */
	for(x=0; x < NSOCKETS; x++){
		if(position->player[position->who].socket[x] == 0)	/* No motion */
			continue;
		ADDSET(motions, x);
	}

	/* Estimation loop */

	minValue = +INFINITY;
	maxValue = -INFINITY;
	brd = NULL;

	for(x=0; x < NSOCKETS; x++){
		if(!ISINSET(motions, x))
			continue;

		DEBUG_TURN

		/* Generate new position (doing the turn) */
		if(brd) free(brd);	/* kill old */
		brd = makeTurn(position, x);

		positions_estimated++;
		DEBUG_NEWPOSITION

		switch(position->who){

		case HUMAN:	/* MAX node */

			if(brd->who != position->who){	/* Opponent's turn (Computer's) */
				value =   AlphaBeta(brd, depth-1, thisdepth+1, maxValue, beta);
			} else {			/* Human's turn again */
				value =   AlphaBeta(brd, depth,   thisdepth+1, alpha,    beta);
			}
			DEBUG_ALPHABETA

			if(value > maxValue){
				maxValue = value;
				DEBUG_BEST
			}
			/* beta cut */
			if(beta <= maxValue){
				DEBUG_BETA_CUT
				goto terminate_loop;
			}
			break;

		case COMPU:	/* MIN node */

			if(brd->who != position->who){	/* Human's turn */
				value =   AlphaBeta(brd, depth-1, thisdepth+1, alpha, minValue);
			} else {			/* Computer's turn again */
				value =   AlphaBeta(brd, depth,   thisdepth+1, alpha,    beta);
			}
			DEBUG_ALPHABETA

			if(value < minValue){
				minValue = value;
				DEBUG_BEST
			}
			/* alpha cut */
			if(minValue <= alpha){
				DEBUG_ALPHA_CUT
				goto terminate_loop;
			}
			break;
		}
	}

terminate_loop:
	if(brd) free(brd);	/* kill old */
	position->next = NULL;

	DEBUG_AB_EXIT
	return (position->who == HUMAN) ? maxValue : minValue;
}

MINIMAX algorithm.
==================

minimax(Node *node){

	if(isLeaf(node))
		return VALUE(node);

	int maxValue = -INFINITY;	// alpha
	int minValue = +INFINITY;	// beta

	foreach subnode in Children(node) {
		int value = minimax(subnode);
		if(isOpponent(node)){
			minValue = MIN(minValue, value);
		} else { // my node
			maxValue = MAX(maxValue, value);
		}
	}
	return (isOpponent(node) ? minValue : maxValue);
}

ALPHA-BETA algorithm.
=====================

			alpha1 : = MAX of the scores of its children
				   explored up to now.

	MAXnode(alpha1, beta1)	// myNode
		|
		|
		|
	MINnode(alpha2, beta2)	// opponentNode

			alpha2 := alpha1 (taken from parent)

	----------------------------------------------------------------

			beta1 := MIN of the scores of its children
				 explored up to now.

	MINnode(alpha1, beta1)
		|
		|
		|
	MAXnode(alpha2, beta2)

			beta2 := beta1 (borrowed from the parent)

	----------------------------------------------------------------

call: AlphaBeta(node, -INFINITY, +INFINITY).

The AlphaBeta however does NOT allow to choose the BEST move.
Toplevel procedure must follow the idea of pure MIN or MAX;
looking through ALL possible topmost positions and their estimations.

AlphaBeta(node, A, B){

	int value;

	if(isLeaf(node))
		return VALUE(node);

	int maxValue = -INFINITY;	// alpha
	int minValue = +INFINITY;	// beta

	if(isOpponent(node)){

		// B is being ignored

		foreach subnode in Children(node) {
		// subNodes are my nodes (MAX)
			value = AlphaBeta(subnode, A, minValue);
			minValue = MIN(minValue, value);
			if(minValue <= A)
				break;
		}
		return minValue;
		
	} else { 	// isMy(node)

		// A is being ignored

		foreach subnode in Children(node) {
		// subNodes are opponent's nodes (MIN)
			value = AlphaBeta(subnode, maxValue, B);
			maxValue = MAX(maxValue, value);
			if(B <= maxValue)
				break;
		}
		return maxValue;
	}
}

The game of the depth 9. It is still undetermined,
7 random decisions were made.

The computation took 48 hours.
H0 H1 C4 H4 C2 H1 C5 H1 C3 C4 H2 C4 H3 H6 H6 H1 H5 H3 H2 H5 C6 C1 C5 H1 C4 H2 H5 C2 H1 C6 H1 C1 C5 H3 H3 H6 C5 H4 H6 C4 H6 C1 C6 H5 H4 H3 C2 C6 H2 C4 H5 C3 C6 H1 C5 H2 C6 [33:39]
 Ваша оценка:

Связаться с программистом сайта.

Новые книги авторов СИ, вышедшие из печати:
Э.Бланк "Пленница чужого мира" О.Копылова "Невеста звездного принца" А.Позин "Меч Тамерлана.Крестьянский сын,дворянская дочь"

Как попасть в этoт список
Сайт - "Художники" .. || .. Доска об'явлений "Книги"