1 /*
2 .-.
3 | '
4 '._.HECKERS
5
6 Authored by abakh <abakh@tuta.io>
7 To the extent possible under law, the author(s) have dedicated all copyright and related and neighboring rights to this software to the public domain worldwide. This software is distributed without any warranty.
8
9 You should have received a copy of the CC0 Public Domain Dedication along with this software. If not, see <http://creativecommons.org/publicdomain/zero/1.0/>.
10 */
11
12 #include <curses.h>
13 #include <string.h>
14 #include <time.h>
15 #include <float.h>
16 #include <limits.h>
17 #include <stdlib.h>
18 #include <signal.h>
19 #include <math.h>
20 #include <stdbool.h>
21 #include "config.h"
22 #define LIGHT -1
23 #define DARK 1
24 #define KING 2
25 #define DOESNT_MATTER 1
26 #define IMAGINARY 0
27 #define NORMAL 1
28 #define ALT_IMG 2
29 #define ALT_NRM 3
30 #define WIN 100000
31
32
33 byte py,px;//cursor
34 byte cy,cx;//selected(choosen) piece
35 int dpt;
36 byte game[8][8];
37 byte computer[2]={0,0};
38 byte score[2];//set by header()
39 bool endgame=false;
40 byte jumpagainy , jumpagainx;
41 bool kinged;//if a piece jumps over multiple others and becomes a king it cannot continue jumping
42
in(byte A[4],byte B[4],byte a,byte b)43 bool in(byte A[4],byte B[4],byte a,byte b){
44 for(byte c=0;c<4;++c)
45 if(A[c]==a && B[c]==b)
46 return true;
47 return false;
48 }
rectangle(byte sy,byte sx)49 void rectangle(byte sy,byte sx){
50 byte y,x;
51 for(y=0;y<=8+1;++y){
52 mvaddch(sy+y,sx,ACS_VLINE);
53 mvaddch(sy+y,sx+8*2,ACS_VLINE);
54 }
55 for(x=0;x<=8*2;++x){
56 mvaddch(sy,sx+x,ACS_HLINE);
57 mvaddch(sy+8+1,sx+x,ACS_HLINE);
58 }
59 mvaddch(sy,sx,ACS_ULCORNER);
60 mvaddch(sy+8+1,sx,ACS_LLCORNER);
61 mvaddch(sy,sx+8*2,ACS_URCORNER);
62 mvaddch(sy+8+1,sx+8*2,ACS_LRCORNER);
63 }
header(void)64 void header(void){
65 score[0]=score[1]=0;
66 byte y,x;
67 for(y=0;y<8;++y){
68 for(x=0;x<8;++x){
69 if(game[y][x]){
70 if(game[y][x]<0)
71 score[0]++;
72 else
73 score[1]++;
74 }
75 }
76 }
77 mvprintw(0,0," .-.");
78 mvprintw(1,0,"| ' %2d:%2d",score[0],score[1]);
79 mvprintw(2,0,"'._,HECKERS ");
80 }
draw(byte sy,byte sx)81 void draw(byte sy,byte sx){//the game's board
82 rectangle(sy,sx);
83 chtype ch ;
84 byte y,x;
85 for(y=0;y<8;++y){
86 for(x=0;x<8;++x){
87 ch=A_NORMAL;
88 if(y==py && x==px)
89 ch |= A_STANDOUT;
90 if(y==cy && x==cx)
91 ch |= A_BOLD;
92 if(game[y][x]){
93 if(game[y][x]<0){
94 if(has_colors())
95 ch|=COLOR_PAIR(1);
96 else
97 ch |= A_UNDERLINE;
98 }
99 if(abs(game[y][x])<2)
100 ch |='O';
101 else
102 ch |='K';
103 }
104 else if( (y%2) != (x%2) )
105 ch|='.';
106 else
107 ch|=' ';
108 mvaddch(sy+1+y,sx+x*2+1,ch);
109 }
110 }
111 }
112 //place the pieces on the board
fill(void)113 void fill(void){
114 byte y,x;
115 for(y=0;y<8;++y){
116 for(x=0;x<8;++x){
117 game[y][x]=0;
118 if( (y%2) != (x%2)){
119 if(y<3) game[y][x]=1;
120 if(y>4) game[y][x]=-1;
121 }
122 }
123 }
124 }
125 //fill mvy/x with possible moves
moves(byte ty,byte tx,byte mvy[4],byte mvx[4])126 bool moves(byte ty,byte tx,byte mvy[4],byte mvx[4]){
127 bool ret=0;
128 byte ndx=0;
129 byte t= game[ty][tx];
130 move(15,0);
131 byte dy,dx;
132 for(dy=-1;dy<2;++dy){
133 for(dx=-1;dx<2;++dx){
134 if( !dy || !dx || (!ty && dy<0) || (!tx && dx<0) || (dy==-t) || (ty+dy>=8) || (tx+dx>=8) )
135 ;
136 else if(!game[ty+dy][tx+dx]){
137 ret=1;
138 mvy[ndx]=ty+dy;
139 mvx[ndx]=tx+dx;
140 ++ndx;
141 }
142 else
143 ++ndx;
144 }
145 }
146 return ret;
147 }
148 //would be much faster than applying moves() on every tile
can_move(byte side)149 bool can_move(byte side){
150 byte y , x ,t, dy , dx;
151 for(y=0;y<8;++y){
152 for(x=0;x<8;++x){
153 if( (t=game[y][x])*side > 0 ){
154 for(dy=-1;dy<2;++dy){
155 for(dx=-1;dx<2;++dx){
156 if( !dy || !dx || (!y && dy<0) || (!x && dx<0) || (dy==-t) || (y+dy>=8) || (x+dx>=8) )
157 ;
158 else if( !game[y+dy][x+dx] )
159 return 1;
160 }
161 }
162 }
163 }
164 }
165 return 0;
166
167 }
168 //fill mvy/x with possible jumping moves
jumps(byte ty,byte tx,byte mvy[4],byte mvx[4])169 bool jumps(byte ty,byte tx,byte mvy[4],byte mvx[4]){
170 bool ret=0;
171 byte ndx=0;
172 byte ey,ex;
173 byte t= game[ty][tx];
174 byte dy,dx;
175 for(dy=-1;dy<2;++dy){
176 for(dx=-1;dx<2;++dx){
177 ey = dy*2;
178 ex = dx*2;
179 if(!dy || !dx ||(dy==-t)|| (ty+ey<0) || (tx+ex<0) || (ty+ey>=8) || (tx+ex>=8) )
180 ;
181 else if(!game[ty+ey][tx+ex] && game[ty+dy][tx+dx]*t<0){
182 ret=1;
183 mvy[ndx]=ty+ey;
184 mvx[ndx]=tx+ex;
185 ++ndx;
186 }
187 else
188 ++ndx;
189 }
190 }
191 return ret;
192 }
193 //same as can_move for jumps
can_jump(byte ty,byte tx)194 byte can_jump(byte ty,byte tx){
195 byte dy,dx,t=game[ty][tx];
196 byte ey,ex;
197 byte ret=0;
198 for(dy=-1;dy<2;++dy){
199 for(dx=-1;dx<2;++dx){
200 ey=dy*2;
201 ex=dx*2;
202 if((dy==-t)||(ty+ey<0)||(tx+ex<0)||(ty+ey>=8)||(tx+ex>=8) )
203 ;
204 else if(!game[ty+dy*2][tx+dx*2]&&game[ty+dy][tx+dx]*t<0){
205 ++ret;
206 if(ret>1)
207 return ret;
208 }
209
210 }
211 }
212 return ret;
213 }
214 //see if the side is forced to do a jump
forced_jump(byte side)215 byte forced_jump(byte side){
216 byte y,x;
217 byte foo,ret;
218 foo=ret=0;
219 for(y=0;y<8;++y){
220 for(x=0;x<8;++x){
221 if(game[y][x]*side>0 && (foo=can_jump(y,x)) )
222 ret+=foo;
223 if(ret>1)
224 return ret;
225 }
226 }
227 return ret;
228 }
cmove(byte fy,byte fx,byte sy,byte sx)229 byte cmove(byte fy,byte fx,byte sy,byte sx){//really move/jump , 'move' is a curses function
230 byte a = game[fy][fx];
231 byte ret=0;
232 game[fy][fx]=0;
233 game[sy][sx]=a;
234 if(abs(fy-sy) == 2){
235 ret =game[(fy+sy)/2][(fx+sx)/2];
236 game[(fy+sy)/2][(fx+sx)/2]=0;
237 }
238 return ret;
239 }
240 //make the pawn a king
king(byte y,byte x)241 bool king(byte y,byte x){
242 byte t= (4-y)*game[y][x];
243 if( (y==7 || !y) && t<0 && t>-5 ){
244 game[y][x]*=2;
245 return 1;
246 }
247 return 0;
248 }
advantage(byte side)249 double advantage(byte side){
250 unsigned char own,opp;
251 own=opp=0;
252 byte foo;
253 byte y,x;
254 for(y=0;y<8;++y){
255 for(x=0;x<8;++x){
256 foo=game[y][x]*side;
257 if(foo>0){
258 ++own;//so it wont sacrfice two pawns for a king ( 2 kings == 3 pawns)
259 own+=foo;
260 }
261 else if(foo<0){
262 ++opp;
263 opp-=foo;
264 }
265 }
266 }
267 if(!own)
268 return 0;
269 else if(!opp)
270 return WIN;
271 else
272 return (double)own/opp;
273 }
posadvantage(byte side)274 double posadvantage(byte side){
275 double adv=0;
276 double oppadv=0;
277 byte foo;
278 byte y,x;
279 byte goal= (side>0)*7 , oppgoal=(side<0)*7;
280 /*This encourages the AI to king its pawns and concentrate its kings in the center.
281 The idea is : With forces concentrated in the center, movements to all of the board would be in the game tree's horizon of sight(given enough depth);
282 and with forces being focused , its takes less movements to make an attack. */
283 for(y=0;y<8;++y){
284 for(x=0;x<8;++x){
285 foo=game[y][x]*side;
286 if(foo>0){
287 adv+=foo;
288 ++adv;
289 if(foo==1)
290 adv+= 1/( abs(y-goal) );//adding positional value
291 else if(foo==2)
292 adv+= 1/( fabs(y-3.5)+ fabs(x-3.5) );
293 }
294 else if( foo<0 ){
295 oppadv-=foo;
296 ++oppadv;
297 if(foo==-1)
298 adv+=1/( abs(y-oppgoal) );
299 else if(foo==-2)
300 adv+= 1/( fabs(y-3.5)+ fabs(x-3.5) );
301 }
302 }
303 }
304 if(!adv)
305 return 0;
306 else if( !oppadv )
307 return WIN;
308 else
309 return adv/oppadv;
310 return adv;
311 }
312 //the AI algorithm
decide(byte side,byte depth,byte s)313 double decide(byte side,byte depth,byte s){//s is the type of move, it doesn't stand for anything
314 byte fj=forced_jump(side);//only one legal jump if returns 1
315 byte nextturn;
316
317 byte mvy[4],mvx[4];
318 byte n;
319
320 bool didking;
321 byte captured;
322
323 double adv=0;
324 byte toy,tox;
325 byte y,x;
326
327 double wrstadv=WIN+1;
328
329 double bestadv=0;
330 byte besttoy,besttox;
331 byte besty,bestx;
332 bestx=besty=besttox=besttoy=-100;
333 bool canmove=0;
334
335 byte nexts ;
336 if(s == IMAGINARY || s == NORMAL )
337 nexts=IMAGINARY;
338 else
339 nexts=ALT_IMG;
340
341 for(y=0;y<8;++y){
342 for(x=0;x<8;++x){
343 if(fj && (s==NORMAL || s==ALT_NRM) && jumpagainy>=0 && (jumpagainy!=y || jumpagainx!=x) )
344 continue;
345 if(game[y][x]*side>0){
346 canmove=0;
347 memset(mvy,-1,4);
348 memset(mvx,-1,4);
349 if(fj)
350 canmove=jumps(y,x,mvy,mvx);
351 else
352 canmove=moves(y,x,mvy,mvx);
353 if(canmove){
354 for(n=0;n<4;++n){
355 if(mvy[n] != -1){//a real move
356 toy=mvy[n];
357 tox=mvx[n];
358 captured=cmove(y,x,toy,tox);//do the imaginary move
359 if(fj && can_jump(toy,tox) ) //its a double jump
360 nextturn=side;
361 else
362 nextturn=-side;
363 didking=king(toy,tox);
364
365 //see the advantage you get
366 if(fj==1 && (s==ALT_NRM || s==NORMAL) )
367 adv= DOESNT_MATTER;//you have to do the move anyway
368 else if(!depth){
369 if(s==IMAGINARY || s==NORMAL)//calculating advantage only based on numerical superiority
370 adv=advantage(side);
371 else
372 adv=posadvantage(side);//taking to account the position of the pieces
373 }
374 else{
375 if(nextturn==side)
376 adv=decide(nextturn,depth,nexts);
377 else{ //best move is the one that gives least advantage to the opponet
378 adv=decide(nextturn,depth-!fj,nexts);
379 if(adv==WIN)
380 adv=0;
381 else if(adv)
382 adv=1/adv;
383 else
384 adv=WIN;
385 }
386 }
387 //undo the imaginary move
388 if(didking)
389 game[toy][tox]/=2;
390 game[y][x]=game[toy][tox];
391 game[toy][tox]=0;
392 if(fj)
393 game[(toy+y)/2][(tox+x)/2]=captured;
394
395 if(besty<0 || adv>bestadv || (adv==bestadv && ( rand()%2 )) ){
396 besty=y;
397 bestx=x;
398 besttoy=toy;
399 besttox=tox;
400 bestadv=adv;
401 }
402 if(adv<wrstadv)
403 wrstadv=adv;
404 if(fj == 1)
405 goto EndLoop;
406 }
407 }
408 }
409 }
410 }
411 }
412 EndLoop:
413 if( (s==NORMAL || s==ALT_NRM) && besty >= 0 ){
414 if(endgame && fj!=1 && s==NORMAL && bestadv==wrstadv ){//the algorithm is not given enough depth to determine which move is better
415 if(wrstadv == WIN){//the randomization in the algorithm may cause an illusion of an inevitable win in several moves
416 if(depth > 1)
417 decide(side,depth-1,NORMAL);
418 else
419 goto Move;
420 }
421 else
422 decide(side,depth,ALT_NRM);//change your opinion about what advantage means
423 }
424 else{
425 Move:
426 cmove(besty,bestx,besttoy,besttox);
427 kinged=king(besttoy,besttox);
428 if(!kinged && can_jump(besttoy,besttox) ){
429 jumpagainy = besttoy;//so the next player (itself) can only continue the chain of jumps from there
430 jumpagainx = besttox;
431 }
432 else
433 jumpagainy=jumpagainx=-1;
434 }
435 }
436 return bestadv;
437 }
438 //peacefully close when ^C is pressed
sigint_handler(int x)439 void sigint_handler(int x){
440 endwin();
441 puts("Quit.");
442 exit(x);
443 }
444
mouseinput(void)445 void mouseinput(void){
446 #ifndef NO_MOUSE
447 MEVENT minput;
448 #ifdef PDCURSES
449 nc_getmouse(&minput);
450 #else
451 getmouse(&minput);
452 #endif
453 if( minput.y-4 <8 && minput.x-1<16){
454 py=minput.y-4;
455 px=(minput.x-1)/2;
456 }
457 else
458 return;
459 if(minput.bstate & (BUTTON1_CLICKED|BUTTON1_PRESSED|BUTTON1_RELEASED) )
460 ungetch('\n');
461 #endif
462 }
help(void)463 void help(void){
464 erase();
465 header();
466 attron(A_BOLD);
467 mvprintw(3,0," **** THE CONTROLS ****");
468 mvprintw(8,0,"YOU CAN ALSO USE THE MOUSE!");
469 attroff(A_BOLD);
470 mvprintw(4,0,"RETURN/ENTER : Select or move the piece");
471 mvprintw(5,0,"hjkl/ARROW KEYS : Move cursor");
472 mvprintw(6,0,"q : quit");
473 mvprintw(7,0,"F1 & F2 : Help on controls & gameplay");
474 mvprintw(10,0,"Press a key to continue");
475 refresh();
476 getch();
477 erase();
478 }
gameplay(void)479 void gameplay(void){
480 erase();
481 header();
482 attron(A_BOLD);
483 mvprintw(3,0," **** THE GAMEPLAY ****");
484 attroff(A_BOLD);
485 move(4,0);
486 printw("1) The game starts with each player having 12 men;\n");
487 printw(" men can only diagonally move forwards \n");
488 printw(" (toward the opponet's side).\n\n");
489 printw("2) Men can become kings by reaching the opponet's \n");
490 printw(" first rank; kings can diagonally move both forwards\n");
491 printw(" and backwards.\n\n");
492 printw("3) Pieces can capture opponet's pieces by jumping over them\n");
493 printw(" also they can capture several pieces at once by doing a\n");
494 printw(" chain of jumps.\n\n");
495 printw("4) You have to do a jump if you can.\n\n");
496 printw("5) A player wins when the opponet can't do a move e. g. \n");
497 printw(" all of their pieces are captured.\n\n");
498 refresh();
499 getch();
500 erase();
501 }
main(int argc,char ** argv)502 int main(int argc,char** argv){
503 dpt=4;
504 if(argc>2){
505 printf("Usage: %s [AIpower]\n",argv[0]);
506 return EXIT_FAILURE;
507 }
508 if(argc==2){
509 if(sscanf(argv[1],"%d",&dpt) && dpt<128 && dpt>0)
510 ;
511 else{
512 puts("That should be a number from 1 to 127.");
513 return EXIT_FAILURE;
514 }
515 }
516 initscr();
517 #ifndef NO_MOUSE
518 mousemask(ALL_MOUSE_EVENTS,NULL);
519 #endif
520 noecho();
521 cbreak();
522 keypad(stdscr,1);
523 int input ;
524 printw("Dark plays first.\nChoose type of the dark player(H/c)\n" );
525 refresh();
526 input=getch();
527 if(input=='c'){
528 computer[0]=dpt;
529 printw("Computer.\n");
530 }
531 else{
532 computer[0]=0;
533 printw("Human.\n");
534 }
535 printw("Choose type of the bright player(h/C)\n");
536 refresh();
537 input=getch();
538 if(input=='h'){
539 computer[1]=0;
540 printw("Human.\n");
541 }
542 else{
543 computer[1]=dpt;
544 printw("Computer.\n");
545 }
546 if(has_colors()){
547 start_color();
548 use_default_colors();
549 init_pair(1,COLOR_RED,-1);
550 }
551 signal(SIGINT,sigint_handler);
552 Start:
553 srand(time(NULL)%UINT_MAX);
554 fill();
555 cy=cx=-1;
556 py=px=0;
557 byte mvy[4],mvx[4];
558 memset(mvy,-1,4);
559 memset(mvx,-1,4);
560 byte turn=1;
561 bool t=1;
562 bool fj;
563 byte result;
564 byte todraw=0;
565 double adv = 1;//used to determine when the game is a draw
566 double previousadv =1;
567 Turn:
568 curs_set(0);
569 jumpagainy=jumpagainx=-1;
570 kinged=0;
571 turn =-turn;
572 t=!t;//t == turn<0 that's turn in binary/array index format
573 fj = forced_jump(turn);
574 erase();
575 flushinp();
576 header();
577 draw(3,0);
578 if(t){
579 previousadv=adv;
580 adv= advantage(1) + (score[0]*score[1]);//just taking the dry scores to account too,nothing special
581 if(previousadv==adv)
582 ++todraw;
583 else
584 todraw=0;
585 }
586 if(!score[0] || (turn==-1 && !fj && !can_move(-1))){
587 result=1;
588 goto End;
589 }
590 else if(!score[1] || (turn==1 && !fj && !can_move(1))){
591 result=-1;
592 goto End;
593 }
594 else if(todraw==50){ // 50 turns without any gain for either side
595 result=0;
596 goto End;
597 }
598 endgame= score[t]<=5 || score[!t]<=5;
599 draw(3,0);
600 refresh();
601 while(computer[t]){
602 mvprintw(13,0,"Thinking...");
603 refresh();
604 computer[t]=dpt+ (score[!t] != score[t]) + endgame;
605 decide(turn,computer[t],1);
606 if(!(fj && jumpagainy>=0 && !kinged )){
607 goto Turn;
608 }
609 }
610 while(1){
611 erase();
612 draw(3,0);
613 header();
614 if(!(computer[0]||computer[1])){
615 if(t)
616 addstr(" Bright's turn");
617 else{
618 attron(COLOR_PAIR(1));
619 addstr(" Dark's turn");
620 attroff(COLOR_PAIR(1));
621 }
622 }
623 refresh();
624 input=getch();
625 if( input == KEY_F(1) || input=='?' )
626 help();
627 if( input == KEY_F(2) )
628 gameplay();
629 if( input == KEY_MOUSE )
630 mouseinput();
631 if( (input=='k' || input==KEY_UP) && py>0)
632 --py;
633 if( (input=='j' || input==KEY_DOWN) && py<7)
634 ++py;
635 if( (input=='h' || input==KEY_LEFT) && px>0)
636 --px;
637 if( (input=='l' || input==KEY_RIGHT) && px<7)
638 ++px;
639 if( input=='q'){
640 result=2;
641 goto End;
642 }
643 if(input=='\n' || input==KEY_ENTER){
644 if(game[py][px]*turn>0){
645 cy=py;
646 cx=px;
647 memset(mvy,-1,4);
648 memset(mvx,-1,4);
649 if(!fj)
650 moves(py,px,mvy,mvx);
651 jumps(py,px,mvy,mvx);
652 }
653 if( in(mvy,mvx,py,px) && !(jumpagainy>=0 && (cy !=jumpagainy || cx != jumpagainx) ) ){
654 memset(mvy,-1,4);
655 memset(mvx,-1,4);
656 cmove(cy,cx,py,px);
657 kinged=king(py,px);
658 cy=-1;
659 cx=-1;
660 if( !(fj && can_jump(py,px) && !kinged ) ){
661 goto Turn;
662 }
663 else{
664 jumpagainy=py;
665 jumpagainx=px;
666 }
667 }
668 }
669 }
670 End:
671 move(13,0);
672 switch(result){
673 case -1:
674 printw("The dark side has won the game.");
675 break;
676 case 0:
677 printw("Draw.");
678 break;
679 case 1:
680 printw("The bright side has won the game.");
681 break;
682 case 2:
683 printw("You resigned.");
684 }
685 printw(" Wanna rematch?(y/n)");
686 curs_set(1);
687 input=getch();
688 if(result==2){
689 if (input=='Y' || input=='y')
690 goto Start;
691 }
692 else if(input!='n' && input!='N' && input!= 'q'){
693 /*byte b=computer[0]; //switch sides, i don't know if it's necessary
694 computer[0]=computer[1];
695 computer[1]=b;*/
696 goto Start;
697 }
698 endwin();
699 return EXIT_SUCCESS;
700 }
701