Skip to content

Instantly share code, notes, and snippets.

@louisswarren
Last active December 14, 2023 08:09
Show Gist options
  • Save louisswarren/76d39fb00a466e11b9fd9bb804ac2995 to your computer and use it in GitHub Desktop.
Save louisswarren/76d39fb00a466e11b9fd9bb804ac2995 to your computer and use it in GitHub Desktop.
Simulate connect 4
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#define ENABLE_MOVE_COUNTER
struct game {
uint8_t col[2][7];
int p;
int num_moves;
};
void
setup(struct game *g)
{
for (int i = 0; i < 7; ++i) {
g->col[0][i] = 1 << 6;
g->col[1][i] = 1 << 6;
}
g->p = 0;
#ifdef ENABLE_MOVE_COUNTER
g->num_moves = 0;
#endif
}
int
is_valid_move(const struct game *g, int n)
{
return !((g->col[0][n] | g->col[1][n]) & 1);
}
void
move(struct game *g, int n)
{
assert(n >= 0);
assert(n < 7);
uint8_t m = g->col[0][n] | g->col[1][n];
g->col[g->p][n] |= (m & (uint8_t)(-m)) >> 1;
g->p ^= 1;
#ifdef ENABLE_MOVE_COUNTER
g->num_moves++;
#endif
}
int
result(const struct game *g)
{
for (int p = 0; p < 2; ++p) {
int r = 0;
const uint8_t *x = g->col[p];
/* Horizontal wins */
for (uint8_t m = 1; m < (1 << 6); m <<= 1) {
for (int i = 0; i < 4; ++i) {
r |= (x[i + 0] & m) &
(x[i + 1] & m) &
(x[i + 2] & m) &
(x[i + 3] & m);
}
}
/* Vertical wins */
for (int j = 0; j < 3; ++j) {
for (int i = 0; i < 7; ++i) {
r |= ((x[i] >> j) & 15) == 15;
}
}
/* Diagonal wins */
for (int j = 0; j < 3; ++j) {
for (int i = 0; i < 4; ++i) {
r |= ((x[i + 0] >> (j + 0)) & 1)
& ((x[i + 1] >> (j + 1)) & 1)
& ((x[i + 2] >> (j + 2)) & 1)
& ((x[i + 3] >> (j + 3)) & 1);
r |= ((x[i + 0] >> (j + 3)) & 1)
& ((x[i + 1] >> (j + 2)) & 1)
& ((x[i + 2] >> (j + 1)) & 1)
& ((x[i + 3] >> (j + 0)) & 1);
}
}
if (r) {
return p ? -1 : 1;
}
}
return 0;
}
void
draw(struct game *g)
{
puts("/+-+-+-+-+-+-+-+\\");
for (uint8_t m = 1; m < (1 << 6); m <<= 1) {
putchar('|');
for (int i = 0; i < 7; ++i) {
putchar(' ');
if (g->col[0][i] & m) {
putchar('X');
} else if (g->col[1][i] & m) {
putchar('O');
} else {
putchar(' ');
}
}
puts(" |");
}
puts("|+-+-+-+-+-+-+-+|");
puts("| A B C D E F G |");
}
int
play_random(struct game *g)
{
for (;;) {
int i;
for (i = 0; i < 7; ++i) {
if (is_valid_move(g, i))
break;
}
if (i == 7)
return 0;
/* Warning: not uniformly random */
for (i = rand() % 7; ; (i = (i + 1) % 7)) {
if (is_valid_move(g, i))
break;
}
move(g, i);
int r = result(g);
if (r)
return r;
}
}
void
search(void)
{
struct game gs[6 * 7];
int n = 0;
setup(&gs[0]);
for (;;) {
setup(&gs[n]);
}
}
void
mean_moves(int n_games)
{
int n;
struct game g;
long long move_count = 0;
long long scores[3] = {0};
srand(1);
for (n = 0; n < n_games; ++n) {
setup(&g);
scores[play_random(&g) + 1]++;
move_count += g.num_moves;
}
printf("Averaged %lld moves in %d games\n", move_count / n, n);
printf("O won %lld/%d = %%%0.1f\n",
scores[0], n, 100.0 * (double)scores[0]/n);
printf("X won %lld/%d = %%%0.1f\n",
scores[2], n, 100.0 * (double)scores[2]/n);
printf("Draw %lld/%d = %%%0.1f\n",
scores[1], n, 100.0 * (double)scores[1]/n);
}
int
main(int argc, const char *argv[])
{
int n;
int r;
struct game g;
srand(1);
int n_to_log = argc >= 2 ? atoi(argv[1]) : 1;
int n_to_analyse = argc >= 3 ? atoi(argv[2]) : 0;
for (n = 0; n < n_to_log; ++n) {
const char *msg[] = {"O", "Nobody", "X"};
setup(&g);
r = play_random(&g);
draw(&g);
printf("%s wins in %d moves\n\n", msg[r + 1], g.num_moves);
}
if (n_to_analyse > 0)
mean_moves(n_to_analyse);
return 0;
}
@louisswarren
Copy link
Author

Plays ~380K games per second

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment