bindings/samples/tic-tac-toe.c

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