bindings/samples/tic-tac-toe.c

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