Text-based Tic-Tac-Toe in C

Question

I have written a text-based tic-tac-toe game in C. Are there any ways I can further improve the code?

It uses an ENUM to indicate the player type and two bitfields to indicate the board.

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include <ctype.h>
#include <limits.h>

#define FULL 0777

typedef unsigned int bitfield;

typedef enum {
    X, O, NONE = -1
} side;

/* The board is represented using two bitfields indicating the squares
   containing an X and an O.  The bits correspond to squares as shewn
   in the diagram below (0 indicates the least significant bit) */
/*  0 | 1 | 2
 * ---+---+----
 *  3 | 4 | 5
 * ---+---+----
 *  6 | 7 | 8 */

/* mask for square i */
#define SQUARE(i) (1 << i)

side next_player(side p)
{
    return (p + 1) % 2;
}

char token(side p)
{
    switch (p) {
    case X:
        return 'X';
    case O:
        return 'O';
    default:
        return '?';
    }
}


/* Determine if there are three in a row.  Given an input n
   representing a bitmask for the squares occupied by a player, test
   if any of the patterns in wins is matched.  */
bool is_win(bitfield board)
{
    /* The array wins contains bitmasks corresponding to the possible
       ways to get three in a row */
    static const bitfield wins[] =
        { 0007, 0070, 0700, 0111, 0222, 0444, 0421, 0124 };
    for (size_t i = 0; i < sizeof(wins) / sizeof(int); i++)
        if ((board & wins[i]) == wins[i])
            return true;
    return false;
}

/* evaluation scores */
enum { WIN = 1, LOSS = -1, DRAW = 0 };
typedef int score;

/* determine best move using recursive search */
/*  parameters:
 *      me:         bitfield indicating squares I occupy
 *      opp:        bitfield indicating squares opponent occupies
 *      achievable: score of best variation found so far
 *      cutoff:     if we can find a move better than this our opponent
 *                  will avoid this variation so we can stop searching
 *      best:       output parameter used to store index of square 
 *                  indicating the move with the best score
 *      return value: score of position, from perspective of active player
*/
score
alpha_beta(bitfield me, bitfield opp, score achievable, score cutoff,
       int *best)
{

    int bestmove = 0;

    if ((me | opp) == FULL) /* all squares filled, draw */
        return DRAW;

    for (int i = 0; i < 9; i++) {

        score cur;
        bitfield tmp;

        if ((me | opp) & SQUARE(i)) // square filled
            continue;

        tmp = me | SQUARE(i);   // make move
        // evaluate position after making move
        cur = is_win(tmp) ? WIN :
            -alpha_beta(opp, tmp, -cutoff, -achievable, NULL);

        if (cur > achievable) {
            achievable = cur;
            bestmove = i;
        }
        if (achievable >= cutoff)
            break;
    }
    if (best)
        *best = bestmove;
    return achievable;
}

/* Display the board */
void show_board(const bitfield players[2])
{

    /* 
     *     0 1 2
     *     -----
     * 0:  0 1 2
     * 1:  3 4 5
     * 2:  6 7 8
     *
     */

    for (int row = 0; row < 3; row++) {
        printf("\n+---+---+---+\n|");
        for (int col = 0; col < 3; col++) {
            int square_idx = row * 3 + col;
            char c = '0' + square_idx;
            for (int j = 0; j < 2; j++)
                if (players[j] & SQUARE(square_idx))
                    c = token(j);
            printf(" %c |", c);
        }
    }
    puts("\n+---+---+---+");
}

side get_side()
{
    side s;
    int c;

    printf("Enter AI player x/o or 2 for two player: ");
    while (isspace(c = getchar()))  /* skip whitespace */
        if (c == EOF)
            exit(EXIT_FAILURE);

    if (c == 'X' || c == 'x')
        s = X;
    else if (c == 'O' || c == 'o' || c == '0')
        s = O;
    else
        s = NONE;

    while ((c = getchar()) != '\n') /* ignore rest of line */
        if (c == EOF)
            exit(EXIT_FAILURE);

    return s;
}


int get_move()
{
    char s[100];        // buffer for line input
    char *err;
    fflush(stdout);
    err = fgets(s, sizeof(s), stdin);
    if (err == NULL)
        exit(EXIT_FAILURE);
    return atoi(s);
}

int main()
{

    int ai;
    bool over = false;
    side cur_player = X;

    bitfield players[2] = { 0 };


    ai = get_side();

    while (!over) {
        int move;
        if (cur_player == ai) { /* select AI move */
            alpha_beta(players[cur_player],
                   players[next_player(cur_player)],
                   -INT_MAX, INT_MAX, &move);
        } else {
            show_board(players);

            printf("Player %c, make your move: ",
                   token(cur_player));
            move = get_move();

            if (!(0 <= move && move < 9)) {
                puts("Invalid move.");
                continue;
            }
            if ((players[0] | players[1]) & SQUARE(move)) {
                puts("Square occupied; try again.");
                continue;
            }
        }

        players[cur_player] |= SQUARE(move);

        if (is_win(players[cur_player])) {
            show_board(players);
            printf("%c wins\n", token(cur_player));
            over = true;
        } else if ((players[0] | players[1]) == FULL) {
            puts("Draw");
            over = true;
        }
        cur_player = next_player(cur_player);
    }

    return EXIT_SUCCESS;
}

Answer 1

The overall pattern here is that you write code in needlessly complex ways. Good C programming practice is to write code as simple as possible, obeying the KISS principle.

• Using octal notation with no explanation why is very bad practice. It's an exotic format and C programmers aren't used to it. One might argue that this algorithm here is one valid use for it since it gives groups of 3, but if so, you need to comment on why you are using it and why it works.

  A more readable notation than for example 0007, 0070, 0700 would be 0x3u << 0, 0x3u << 3, 0x3u << 6, because you can expect C programmers to know hex. (Upcoming C2x will also potentially allow 0b binary constants, but they are non-standard for now.)

• Shifting by a signed integer constant such as #define SQUARE(i) (1 << i) is always wrong, because in the event that i ends up for example 31 on a 32 bit int system, this code invokes undefined behavior. Always use unsigned numbers when dealing with bitwise arithmetic, in this case 1u.

• It is good practice to always wrap function-like macro parameters in parenthesis: #define SQUARE(i) (1u << (i)), in case the caller happens to pass an expression.

• SQUARE() suggests that this is a macro used for multiplication, maybe rename it to SQUARE_MASK or similar. Then the code turns self-documenting and comments like /* mask for square i */ become superfluous.

• I wouldn't use a typedef to create a "bitfield" type. The type in this case is unsigned int (or uint32_t) and one needs to know that in order to make sense of the functions taking "bitfield" parameters. Rather, it would seem that "bitfield" should be in the identifiers: uint32_t bitfield_me, uint32_t bitfield_opp. Or perhaps just make it clear that the code is dealing with bitfields through comments.

• typedef enum { X, O, NONE = -1 } side; and the logic behind this is needlessly complex and obscure. This could have been implemented as for example bool x_turn; and turns shifted as x_turn = !x_turn;. Keep it simple. You can still keep an enum to keep track of which character to print, but don't mix up the logic for what to print with the logic for who's turn it is.

• Similarly, avoid needlessly complex boolean expressions and negations. if (!(0 <= move && move < 9)) can be simplified through De Morgan's Laws. Human users probably expect to type 1 to 9, so we should use the much more readable if (move < 1 || move > 9) /* error */ then translate this human input into programmer index-0 based logic by subtracting by 1.

• There is no obvious reason to use recursion here, it makes the code needlessly slow for no good reason and you could implement that function as a loop instead. I suppose this is some algorithm "alpha-beta pruning", but algorithm theory doesn't translate well to C code and mathematical recursion doesn't translate well to C recursion. It would seem that you could simply keep track of all variables and replace the recursive call with a loop/loops.

• int get_move() is obsolete style function declarations/definitions, you should always write int get_move (void).

• atoi is one of those standard lib functions that should never be used for any purpose, because it has no well-defined error handling. Always use strtol (family of functions) instead.