Аннотация: Правила игры стащены из старой "Науки и жизни". Программа - из какой-то книжки по Прологу, дописано и исправлено мной.
Калах
Играют двое. Вначале у каждого из игроков имеется по 36 мелких равноценных
фишек - "камней", которые разложены поровну на 6 полях, пронумерованных слева направо.
Поля соперников расположены друг против друга. Кроме того, каждый игрок имеет
по специальному полю-накопителю, называемому "калах", и расположенному
справа от шестого поля. Пусть B - владелец нижних полей (в нашем случае он и
начинает игру), А - владелец верхних полей.
Калах A: пуст
6
5
4
3
2
1
Калах B: пуст
6
6
6
6
6
6
6
6
6
6
6
6
1
2
3
4
5
6
При очередном ходе играющий снимает с одного из своих полей все камни
и распределяет их по одному на последующие поля,
не пропуская ни одного, в порядке возрастания их номеров.
Полем, следующим за шестым, считается свой калах. Далее камни
распределяются по чужим полям (опять-таки в порядке возрастания их
номеров), затем вновь по своим (чужой калах пропускается) и так далее,
как бы совершая обход полей-лунок против часовой стрелки.
Например, пойдя с поля номер 1 нижнего ряда, мы перейдём от начальной позиции:
Калах A: 0
6
5
4
3
2
1
Калах B: 0
6
6
6
6
6
6
6
6
6
6
6
6
1
2
3
4
5
6
к следующей:
B ходит: 1
Калах A: 0
6
5
4
3
2
1
Калах B: 1
6
6
6
6
6
6
0
7
7
7
7
7
1
2
3
4
5
6
Если последний из распределяемых камней попал в свой калах, то игрок делает ещё один ход.
Так, начавший игру в нашем примере должен пойти повторно: например со второго поля:
Калах A: 0
6
5
4
3
2
1
Калах B: 1
6
6
6
6
6
6
0
7
7
7
7
7
1
2
3
4
5
6
B ходит: 2
Калах A: 0
6
5
4
3
2
1
Калах B: 2
6
6
6
6
7
7
0
0
8
8
8
8
1
2
3
4
5
6
Ходы могут повторяться многократно: в партиях встречаются серии по 5-6 ходов!
Во всех остальных случаях очередь хода передаётся противнику.
Это и произошло сейчас в начатой нами партии.
Противник может ответить ходом с первого поля (как мы вскоре увидим, неудачным):
A ходит: 1
Калах A: 0
6
5
4
3
2
1
Калах B: 2
6
6
6
6
7
7
0
0
8
8
8
8
1
2
3
4
5
6
получается:
Калах A: 1
6
5
4
3
2
1
Калах B: 2
7
7
7
7
8
0
1
0
8
8
8
8
1
2
3
4
5
6
В том случае, когда последний из распределяемых камней попадает на своё же пустое поле,
а на противоположном (противолежащем) поле противника имеются камни, содержимое этих двух
полей переносится в калах сделавшего ход ("съел"),
а очередь хода передаётся противнику. В нашей показательной партии это правило
позволяет владельцу нижних полей ходом с первого поля существенно пополнить
свой калах:
B ходит: 1
Калах A: 1
6
5
4
3
2
1
Калах B: 2
7
7
7
7
8
0
1
0
8
8
8
8
1
2
3
4
5
6
Калах A: 1
6
5
4
3
2
1
Калах B: 2
7
7
7
7
8
0
0
1
8
8
8
8
1
2
3
4
5
6
Ням-ням!
Калах A: 1
6
5
4
3
2
1
Калах B: 10
7
0
7
7
8
0
0
0
8
8
8
8
1
2
3
4
5
6
Если на полях игрока не остаётся ни одного камня, то все камни, находящиеся на полях
противника, переносятся в калах противника,
и игра на этом заканчивается.
После такой операции у обоих игроков может оказаться в калахах по 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).
Программа на Си
Гарантии, что альфа-бета процедура ниже запрограммирована правильно, не даю. Не учили меня ей в колледже, даром что Универ. Написано очень давно.
Следовало бы назвать "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.