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