bindings/samples/tic-tac-toe.c

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