bindings/samples/tic-tac-toe.c

   1 /*
   2  * Copyright (C) 2016 "IoT.bzh"
   3  * Author José Bollo <jose.bollo@iot.bzh>
   4  *
   5  * Licensed under the Apache License, Version 2.0 (the "License");
   6  * you may not use this file except in compliance with the License.
   7  * You may obtain a copy of the License at
   8  *
   9  *   http://www.apache.org/licenses/LICENSE-2.0
  10  *
  11  * Unless required by applicable law or agreed to in writing, software
  12  * distributed under the License is distributed on an "AS IS" BASIS,
  13  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  14  * See the License for the specific language governing permissions and
  15  * limitations under the License.
  16  */
  17
  18 #define _GNU_SOURCE
  19 #include <stdio.h>
  20 #include <string.h>
  21 #include <json-c/json.h>
  22
  23 #include <afb/afb-binding.h>
  24
  25 /*
  26  * the interface to afb-daemon
  27  */
  28 const struct afb_binding_interface *afbitf;
  29
  30 /*
  31  * definition of waiters
  32  */
  33 struct waiter
  34 {
  35         struct waiter *next;
  36         struct afb_req req;
  37 };
  38
  39 /*
  40  * definition of a board
  41  */
  42 struct board
  43 {
  44         struct board *next;
  45         int use_count;
  46         int moves;
  47         int history[9];
  48         int id;
  49         int level;
  50         char board[9];
  51         struct waiter *waiters;
  52 };
  53
  54 /*
  55  * list of boards
  56  */
  57 static struct board *all_boards;
  58
  59 /*
  60  * Searchs a board having the 'id'.
  61  * Returns it if found or NULL otherwise.
  62  */
  63 static struct board *search_board(int id)
  64 {
  65         struct board *board = all_boards;
  66         while (board != NULL && board->id != id)
  67                 board = board->next;
  68         return board;
  69 }
  70
  71 /*
  72  * Creates a new board and returns it.
  73  */
  74 static struct board *get_new_board()
  75 {
  76         /* allocation */
  77         struct board *board = calloc(1, sizeof *board);
  78
  79         /* initialisation */
  80         memset(board->board, ' ', sizeof board->board);
  81         board->use_count = 1;
  82         board->level = 1;
  83         board->moves = 0;
  84         do {
  85                 board->id = (rand() >> 2) % 1000;
  86         } while(board->id == 0 || search_board(board->id) != NULL);
  87
  88         /* link */
  89         board->next = all_boards;
  90         all_boards = board;
  91         return board;
  92 }
  93
  94 /*
  95  * Release a board
  96  */
  97 static void release_board(struct board *board)
  98 {
  99         /* decrease the reference count ... */
 100         if (--board->use_count == 0) {
 101                 /* ... no more use */
 102                 /* unlink from the list of boards */
 103                 struct board **prv = &all_boards;
 104                 while (*prv != NULL && *prv != board)
 105                         prv = &(*prv)->next;
 106                 if (*prv != NULL)
 107                         *prv = board->next;
 108                 /* release the used memory */
 109                 free(board);
 110         }
 111 }
 112
 113 /*
 114  * Checks who wins
 115  * Returns zero if there is no winner
 116  * Returns the char of the winner if a player won
 117  */
 118 static char winner(const char b[9])
 119 {
 120         int i;
 121         char c;
 122
 123         /* check diagonals */
 124         c = b[4];
 125         if (c != ' ') {
 126                 if (b[0] == c && b[8] == c)
 127                         return c;
 128                 if (b[2] == c && b[6] == c)
 129                         return c;
 130         }
 131
 132         /* check lines */
 133         for (i = 0 ; i <= 6 ; i += 3) {
 134                 c = b[i];
 135                 if (c != ' ' && b[i+1] == c && b[i+2] == c)
 136                         return c;
 137         }
 138
 139         /* check columns */
 140         for (i = 0 ; i <= 2 ; i++) {
 141                 c = b[i];
 142                 if (c != ' ' && b[i+3] == c && b[i+6] == c)
 143                         return c;
 144         }
 145
 146         return 0;
 147 }
 148
 149 /* get the color (X or 0) of the move of index 'move' */
 150 static char color(int move)
 151 {
 152         return (move & 1) == 0 ? 'X' : '0';
 153 }
 154
 155 /* adds the move to the board */
 156 static void add_move(struct board *board, int index)
 157 {
 158         int imove = board->moves++;
 159         board->history[imove] = index;
 160         board->board[index] = color(imove);
 161 }
 162
 163 /* get a random possible move index from the board described by 'b' */
 164 static int get_random_move(char b[9])
 165 {
 166         int index = rand() % 9;
 167         while (b[index] != ' ')
 168                 index = (index + 1) % 9;
 169         return index;
 170 }
 171
 172 /*
 173  * Scores the position described by 'b'
 174  * for the player of color 'c' using an analysis of 'depth'.
 175  * Returns 1 if player 'c' will win.
 176  * Returns -1 if opponent of player 'c' will win.
 177  * returns 0 otherwise.
 178  */
 179 static int score_position(char b[9], char c, int depth)
 180 {
 181         int i, t, r;
 182
 183         /* check if winner */
 184         if (winner(b) == c)
 185                 return 1;
 186
 187         /* when depth of analysis is reached return unknown case */
 188         if (--depth == 0)
 189                 return 0;
 190
 191         /* switch to the opponent */
 192         c = (char)('O' + 'X' - c);
 193
 194         /* inspect opponent moves */
 195         r = 1;
 196         for (i = 0 ; i < 9 ; i++) {
 197                 if (b[i] == ' ') {
 198                         b[i] = c;
 199                         t = score_position(b, c, depth);
 200                         b[i] = ' ';
 201                         if (t > 0)
 202                                 return -1; /* opponent will win */
 203
 204                         if (t == 0)
 205                                 r = 0; /* something not clear */
 206                 }
 207         }
 208         return r;
 209 }
 210
 211 /* get one move: return the computed index of the move */
 212 static int get_move(struct board *board)
 213 {
 214         int index, depth, t, f;
 215         char c;
 216         char b[9];
 217
 218         /* compute the depth */
 219         depth = board->level - 1;
 220         if (board->moves + depth > 9)
 221                 depth = 9 - board->moves;
 222
 223         /* case of null depth */
 224         if (depth == 0)
 225                 return get_random_move(board->board);
 226
 227         /* depth and more */
 228         memcpy(b, board->board, 9);
 229         c = color(board->moves);
 230         f = 0;
 231         for (index = 0 ; index < 9 ; index++) {
 232                 if (board->board[index] == ' ') {
 233                         board->board[index] = c;
 234                         t = score_position(board->board, c, depth);
 235                         board->board[index] = ' ';
 236                         if (t > 0)
 237                                 return index;
 238                         if (t < 0)
 239                                 b[index] = '+';
 240                         else
 241                                 f = 1;
 242                 }
 243         }
 244         return get_random_move(f ? b : board->board);
 245 }
 246
 247 /*
 248  * get the board description
 249  */
 250 static struct json_object *describe(struct board *board)
 251 {
 252         int i;
 253         char w;
 254         struct json_object *resu, *arr;
 255
 256         resu = json_object_new_object();
 257
 258         json_object_object_add(resu, "boardid", json_object_new_int(board->id));
 259         json_object_object_add(resu, "level", json_object_new_int(board->level));
 260
 261         arr = json_object_new_array();
 262         json_object_object_add(resu, "board", arr);
 263         for (i = 0 ; i < 9 ; i++)
 264                 json_object_array_add(arr,
 265                                 json_object_new_string_len(&board->board[i], 1));
 266
 267         arr = json_object_new_array();
 268         json_object_object_add(resu, "history", arr);
 269         for (i = 0 ; i < board->moves ; i++)
 270                 json_object_array_add(arr, json_object_new_int(board->history[i]));
 271
 272         w = winner(board->board);
 273         if (w)
 274                 json_object_object_add(resu, "winner", json_object_new_string_len(&w, 1));
 275         else if (board->moves == 9)
 276                 json_object_object_add(resu, "winner", json_object_new_string("none"));
 277
 278         return resu;
 279 }
 280
 281 /*
 282  * signals a change of the board
 283  */
 284 static void changed(struct board *board, const char *reason)
 285 {
 286         struct waiter *waiter, *next;
 287         struct json_object *description;
 288
 289         /* get the description */
 290         description = describe(board);
 291
 292         waiter = board->waiters;
 293         board->waiters = NULL;
 294         while (waiter != NULL) {
 295                 next = waiter->next;
 296                 afb_req_success(waiter->req, json_object_get(description), reason);
 297                 afb_req_unref(waiter->req);
 298                 free(waiter);
 299                 waiter = next;
 300         }
 301
 302         afb_daemon_broadcast_event(afbitf->daemon, reason, description);
 303 }
 304
 305 /*
 306  * retrieves the board of the request
 307  */
 308 static inline struct board *board_of_req(struct afb_req req)
 309 {
 310         return afb_req_context(req, (void*)get_new_board, (void*)release_board);
 311 }
 312
 313 /*
 314  * start a new game
 315  */
 316 static void new(struct afb_req req)
 317 {
 318         struct board *board;
 319
 320         /* retrieves the context for the session */
 321         board = board_of_req(req);
 322         INFO(afbitf, "method 'new' called for boardid %d", board->id);
 323
 324         /* reset the game */
 325         memset(board->board, ' ', sizeof board->board);
 326         board->moves = 0;
 327
 328         /* replies */
 329         afb_req_success(req, NULL, NULL);
 330
 331         /* signal change */
 332         changed(board, "new");
 333 }
 334
 335 /*
 336  * get the board
 337  */
 338 static void board(struct afb_req req)
 339 {
 340         struct board *board;
 341         struct json_object *description;
 342
 343         /* retrieves the context for the session */
 344         board = board_of_req(req);
 345         INFO(afbitf, "method 'board' called for boardid %d", board->id);
 346
 347         /* describe the board */
 348         description = describe(board);
 349
 350         /* send the board's description */
 351         afb_req_success(req, description, NULL);
 352 }
 353
 354 /*
 355  * move a piece
 356  */
 357 static void move(struct afb_req req)
 358 {
 359         struct board *board;
 360         int i;
 361         const char *index;
 362
 363         /* retrieves the context for the session */
 364         board = board_of_req(req);
 365         INFO(afbitf, "method 'move' called for boardid %d", board->id);
 366
 367         /* retrieves the arguments of the move */
 368         index = afb_req_value(req, "index");
 369         i = index == NULL ? -1 : atoi(index);
 370
 371         /* checks validity of arguments */
 372         if (i < 0 || i > 8) {
 373                 WARNING(afbitf, "can't move to %s: %s", index?:"?", index?"wrong value":"not set");
 374                 afb_req_fail(req, "error", "bad request");
 375                 return;
 376         }
 377
 378         /* checks validity of the state */
 379         if (winner(board->board) != 0) {
 380                 WARNING(afbitf, "can't move to %s: game is terminated", index);
 381                 afb_req_fail(req, "error", "game terminated");
 382                 return;
 383         }
 384
 385         /* checks validity of the move */
 386         if (board->board[i] != ' ') {
 387                 WARNING(afbitf, "can't move to %s: room occupied", index);
 388                 afb_req_fail(req, "error", "occupied");
 389                 return;
 390         }
 391
 392         /* applies the move */
 393         INFO(afbitf, "method 'move' for boardid %d, index=%s", board->id, index);
 394         add_move(board, i);
 395
 396         /* replies */
 397         afb_req_success(req, NULL, NULL);
 398
 399         /* signals change */
 400         changed(board, "move");
 401 }
 402
 403 /*
 404  * set the level
 405  */
 406 static void level(struct afb_req req)
 407 {
 408         struct board *board;
 409         int l;
 410         const char *level;
 411
 412         /* retrieves the context for the session */
 413         board = board_of_req(req);
 414         INFO(afbitf, "method 'level' called for boardid %d", board->id);
 415
 416         /* retrieves the arguments */
 417         level = afb_req_value(req, "level");
 418         l = level == NULL ? -1 : atoi(level);
 419
 420         /* check validity of arguments */
 421         if (l < 1 || l > 10) {
 422                 WARNING(afbitf, "can't set level to %s: %s", level?:"?", level?"wrong value":"not set");
 423                 afb_req_fail(req, "error", "bad request");
 424                 return;
 425         }
 426
 427         /* set the level */
 428         INFO(afbitf, "method 'level' for boardid %d, level=%d", board->id, l);
 429         board->level = l;
 430
 431         /* replies */
 432         afb_req_success(req, NULL, NULL);
 433
 434         /* signals change */
 435         changed(board, "level");
 436 }
 437
 438 /*
 439  * Join a board
 440  */
 441 static void join(struct afb_req req)
 442 {
 443         struct board *board, *new_board;
 444         const char *id;
 445
 446         /* retrieves the context for the session */
 447         board = board_of_req(req);
 448         INFO(afbitf, "method 'join' called for boardid %d", board->id);
 449
 450         /* retrieves the arguments */
 451         id = afb_req_value(req, "boardid");
 452         if (id == NULL)
 453                 goto bad_request;
 454
 455         /* none is a special id for joining a new session */
 456         if (strcmp(id, "none") == 0) {
 457                 new_board = get_new_board();
 458                 goto success;
 459         }
 460
 461         /* searchs the board to join */
 462         new_board = search_board(atoi(id));
 463         if (new_board == NULL)
 464                 goto bad_request;
 465
 466         /*
 467          * joining its board is stupid but possible
 468          * however when called with the same stored pointer
 469          * afb_req_context_set will not call the release
 470          * function 'release_board'. So the use_count MUST not
 471          * be incremented.
 472          */
 473         if (new_board != board)
 474                 new_board->use_count++;
 475
 476 success:
 477         /* set the new board (and leaves the previous one) */
 478         afb_req_context_set(req, new_board, (void*)release_board);
 479
 480         /* replies */
 481         afb_req_success(req, NULL, NULL);
 482         return;
 483
 484 bad_request:
 485         WARNING(afbitf, "can't join boardid %s: %s", id ? : "?", !id ? "no boardid" : atoi(id) ? "not found" : "bad boardid");
 486         afb_req_fail(req, "error", "bad request");
 487         return;
 488 }
 489
 490 /*
 491  * Undo the last move
 492  */
 493 static void undo(struct afb_req req)
 494 {
 495         struct board *board;
 496         int i;
 497
 498         /* retrieves the context for the session */
 499         board = board_of_req(req);
 500         INFO(afbitf, "method 'undo' called for boardid %d", board->id);
 501
 502         /* checks the state */
 503         if (board->moves == 0) {
 504                 WARNING(afbitf, "can't undo");
 505                 afb_req_fail(req, "error", "bad request");
 506                 return;
 507         }
 508
 509         /* undo the last move */
 510         i = board->history[--board->moves];
 511         board->board[i] = ' ';
 512
 513         /* replies */
 514         afb_req_success(req, NULL, NULL);
 515
 516         /* signals change */
 517         changed(board, "undo");
 518 }
 519
 520 /*
 521  * computer plays
 522  */
 523 static void play(struct afb_req req)
 524 {
 525         struct board *board;
 526         int index;
 527
 528         /* retrieves the context for the session */
 529         board = board_of_req(req);
 530         INFO(afbitf, "method 'play' called for boardid %d", board->id);
 531
 532         /* checks validity of the state */
 533         if (winner(board->board) != 0 || board->moves == 9) {
 534                 WARNING(afbitf, "can't play: game terminated (%s)", winner(board->board) ? "has winner" : "no room left");
 535                 afb_req_fail(req, "error", "game terminated");
 536                 return;
 537         }
 538
 539         /* gets the move and plays it */
 540         index = get_move(board);
 541         add_move(board, index);
 542
 543         /* replies */
 544         afb_req_success(req, describe(board), NULL);
 545
 546         /* signals change */
 547         changed(board, "play");
 548 }
 549
 550 static void wait(struct afb_req req)
 551 {
 552         struct board *board;
 553         struct waiter *waiter;
 554
 555         /* retrieves the context for the session */
 556         board = board_of_req(req);
 557         INFO(afbitf, "method 'wait' called for boardid %d", board->id);
 558
 559         /* creates the waiter and enqueues it */
 560         waiter = calloc(1, sizeof *waiter);
 561         waiter->req = req;
 562         waiter->next = board->waiters;
 563         afb_req_addref(req);
 564         board->waiters = waiter;
 565 }
 566
 567 /*
 568  * array of the verbs exported to afb-daemon
 569  */
 570 static const struct afb_verb_desc_v1 binding_verbs[] = {
 571    /* VERB'S NAME     SESSION MANAGEMENT          FUNCTION TO CALL  SHORT DESCRIPTION */
 572    { .name= "new",   .session= AFB_SESSION_NONE, .callback= new,   .info= "Starts a new game" },
 573    { .name= "play",  .session= AFB_SESSION_NONE, .callback= play,  .info= "Asks the server to play" },
 574    { .name= "move",  .session= AFB_SESSION_NONE, .callback= move,  .info= "Tells the client move" },
 575    { .name= "board", .session= AFB_SESSION_NONE, .callback= board, .info= "Get the current board" },
 576    { .name= "level", .session= AFB_SESSION_NONE, .callback= level, .info= "Set the server level" },
 577    { .name= "join",  .session= AFB_SESSION_CHECK,.callback= join,  .info= "Join a board" },
 578    { .name= "undo",  .session= AFB_SESSION_NONE, .callback= undo,  .info= "Undo the last move" },
 579    { .name= "wait",  .session= AFB_SESSION_NONE, .callback= wait,  .info= "Wait for a change" },
 580    { .name= NULL } /* marker for end of the array */
 581 };
 582
 583 /*
 584  * description of the binding for afb-daemon
 585  */
 586 static const struct afb_binding binding_description =
 587 {
 588    /* description conforms to VERSION 1 */
 589    .type= AFB_BINDING_VERSION_1,
 590    .v1= {                               /* fills the v1 field of the union when AFB_BINDING_VERSION_1 */
 591       .prefix= "tictactoe",             /* the API name (or binding name or prefix) */
 592       .info= "Sample tac-tac-toe game", /* short description of of the binding */
 593       .verbs = binding_verbs            /* the array describing the verbs of the API */
 594    }
 595 };
 596
 597 /*
 598  * activation function for registering the binding called by afb-daemon
 599  */
 600 const struct afb_binding *afbBindingV1Register(const struct afb_binding_interface *itf)
 601 {
 602    afbitf = itf;         // records the interface for accessing afb-daemon
 603    return &binding_description;  // returns the description of the binding
 604 }
 605