Allegro.cc - Online Community

Allegro.cc Forums » Programming Questions » Beat my noughts and crosses bot?

This thread is locked; no one can reply to it. rss feed Print
Beat my noughts and crosses bot?
James Stanley
Member #7,275
May 2006
avatar

I'm not sure exactly where to post this, but I've written a noughts and crosses bot (Charlie), and I'd like some of you to see if it is beatable (I'd rather it wasn't).

The code is attached, compile with...

gcc -o noughts noughts.c charlie.c

Then run noughts.

Type 0 if you want to start, or X if you want Charlie to start.
Enter the 0-indexed co-ordinates of where you want to go (they're written by the board).

If you manage to beat Charlie, can you please post the game?
Thanks.

Vanneto
Member #8,643
May 2007

There is nothing attached.

In capitalist America bank robs you.

James Stanley
Member #7,275
May 2006
avatar

Hmm...
There ought to have been.
Trying again.

EDIT:
Now there is.

Slartibartfast
Member #8,789
June 2007
avatar

I'm sorry for being rude, but what's the point?
As long as both players aren't morons*, a game of tic-tac-toe will always end in a draw.
wanders off to wikipedia to see if there's any actual proof to what I said
Wikipedia agrees, and states a strategy by which no matter what X did, O can always force a draw (but won't win unless X makes a mistake [ie is a moron])

*-well, that's an exaggeration, but pretty much everyone I know that is familiar with the rules of the game is smart enough never to lose. (and so, never to win.)

James Stanley
Member #7,275
May 2006
avatar

Quote:

I'm sorry for being rude, but what's the point?

I thought I'd got it to that state before, but then somebody at my school beat it.
I was wondering if anyone here had other tactics which could beat it.

Slartibartfast
Member #8,789
June 2007
avatar

I meant the question more along the lines of why program a tic tac toe bot, considering that it is such a simple game, but I'm guessing you did it for fun and personal enlightenment (rather than to boast the unbeatable tic tac toe player).
In that case, the wikipedia article I linked lists "the ultimate strategy", so you can try that on the bot, or just make the bot use it instead of whatever it does currently.

Hmmm, this post reminds me of a game I programmed in allegro a long while ago. (I didn't feel it was finished, and then abandoned it, so I didn't feel like adding it to the depot, or sharing it. [Plus its not that cool of a game, and I'm not really sure how to add games to the depot])
The similarity is that game also has a built-in AI player (though mine is configurable through the commandline, and the game has a hotseat mode as well), which is pretty tough.
If you feel like checking it out (or beating my AI in order to prove your superiority over me after being rude to you) its available Over Here.
Its a game similar to Connect 4, only it is played diagonally, I spent hours playing it with my friends in highschool :)
EDIT: If you are really interested I'll even share the algorithm for the "AI" :)

James Stanley
Member #7,275
May 2006
avatar

I did it because I plan to learn about programming bots. I thought 'what better place to start than the simplest game I can think of?'

I'm going to play your game now.

EDIT:
Actually I can't, it's Windows-only.

Slartibartfast
Member #8,789
June 2007
avatar

Hmm, that's true.
Well, the code's ugly, but since I don't plan on working on it anytime soon, and I'm willing to share the (slightly unfinished) algorithm anyway, I'll just attach the source code and you can compile it for your platform.
All the graphics are drawing primitives, so you don't need anything beyond the source code.

Matthew Leverton
Supreme Loser
January 1999
avatar

Charlie beat me because the coordinates are messed up. :P 0,1 should be row 0, column 1. But I digress.

I played the three different variations of the game and it was a draw every time.

James Stanley
Member #7,275
May 2006
avatar

Well my compiler didn't enjoy it, but it compiled.
Seems a nice combination of noughts and crosses and connect 4.
Your AI's pretty good, too. I'm going to have to read that.

EDIT:

Quote:

Charlie beat me because the coordinates are messed up. :P 0,1 should be row 0, column 1. But I digress.

What?
Everyone says the co-ordinates are wrong... I don't see what's wrong with them.
Co-ordinates are specified x, y, like always.

Quote:

I played the three different variations of the game and it was a draw every time.

Good. Thanks for testing!

EDIT2:
Ooohhhh...!
Now I understand what's wrong with them!

Slartibartfast
Member #8,789
June 2007
avatar

Quote:

Well my compiler didn't enjoy it, but it compiled.

Like I said, its quite ugly.

Quote:

Your AI's pretty good, too. I'm going to have to read that.

Its a really simple algorithm, first it builds a list of where it can place its mark, then it checks the neighbours of each place in the list and gives it a "grade" on how important it is (which depends on the number of identical marks in a row, and upon the grade of the squares that the next player will now be able to put on top of this square), and picks the highest scored one.
This algorithm can evolve into a more random one by choosing a random number between 1 and (sum of all grades) and picking one of the places according to the number.

BTW, the code I posted in the previous post is not the latest code, turns out its an older version of the game (also with a weaker AI). I attached the newest code to this post. IIRC there's still one tiny little kink in the AI I didn't fix even in the newest version. (where it doesn't properly recognize a few very certain cases)

kazzmir
Member #1,786
December 2001
avatar

Hey thats a neat game. And you're( Slartibartfast ) AI is pretty good. Initially I didn't understand the game mechanics, but I looked at the source and figured it out. I only won 2/14 games.

Slartibartfast
Member #8,789
June 2007
avatar

Quote:

Hey thats a neat game. And you're( Slartibartfast ) AI is pretty good. Initially I didn't understand the game mechanics, but I looked at the source and figured it out. I only won 2/14 games.

(Thanks.)
The game mechanics I owe to someone named "Yahlee" (Which is why you'll see the game is named "Yahlee in a row" if you go the the game's site), who is a friend of a friend.
The AI is strong thanks to its many MHZ, what I don't like about it is that if you (the player) make the same moves, then the AI will make the same moves, so you can just win once and then repeat that game over and over again.
I'd say 2/14 is pretty good for someone having just learned the game mechanics. My friends (that played the game "live" for a long time) can probably beat it ~50% of the time, and I beat it ~75% of the time. (Not that I'm boasting that I'm better, I'm probably not. Its just that I'm more familiar with it and played tons of games against it)
There are still a few cases the AI doesn't recognize, like: 4 5 1X2X3 XOXO
In this case, the AI (which is O) would put a O in 4 or 5 rather than in 2. This will make the AI lose the game, because now X will put an X in 2, which will make the AI block with a O in either 1 or 3, and leave 3 or 1 open for X to win with.

Kibiz0r
Member #6,203
September 2005
avatar

"Beat my noughts" sounds... naughty.

bamccaig
Member #7,536
July 2006
avatar

Slartibartfast said:

...if you (the player) make the same moves, then the AI will make the same moves, so you can just win once and then repeat that game over and over again.

...I beat it ~75% of the time.

:-X:P

Slartibartfast
Member #8,789
June 2007
avatar

Evert
Member #794
November 2000
avatar

Damnit, now look what you've made me do? :-/
You've made me go and do what I wanted to try for the Allegro 20-liner thread a few years ago but didn't get to do: write a simple boardgame using an alpha-beta search algorithm.

The rules for the 20-liners were originally that the code had to be no more than 20 lines long. This was later clarified to mean it should not have more than 20 statement ending semicolons. This bit of code only has 16, so it can be written in about 16 lines of sourcecode - it's quite a bit more than that presently because I've tried to make the code a bit readable.
It commits all sort of atrocities like using global variables, unrestricted use of comma operators and not to forget the ternary operator ?: (most of those are hidden by preprocessor defines though).
Anyway, for your amusement:

1/* N-dimensional Tic-Tac-Toe, with alpha-beta AI.
2 * Written as an Allegro 20 liner. This means the code can be written in 20
3 * lines of source code or less, each ending in a semicolon.
4 * It's currently more than that for readability, but it only contains 16
5 * statement ending semicolons, so it's effectively 16 lines of source code.
6 */
7#include <allegro.h>
8#include <string.h>
9 
10#define N 3
11#define BOARD_COLOUR(c) ((c)?( 3*((c)+1)/2+1):0)
12 
13/* Some syntactic sugar to hide the ternary operator and make the code more readable */
14#define IF(a) (a)?
15#define THEN (
16#define ELSE ):(
17#define ENDIF )
18 
19int player = 1, best_value, value, best_move,n,moves=N*N, score, old_mouse_b = 0, x, board[N][N], cols[N], rows[N], diags[3];
20 
21/* Perform a move on the board */
22int move(int x, int y) {
23 return (board[x][y] = player),
24 (cols[x]+=player),
25 (rows[y]+=player),
26 (diags[(x==y)?0:2]+=player),
27 (diags[(x+y)==(N-1)?1:2]+=player),
28 (player = -player),
29 moves--;
30}
31 
32/* Reverse a move on the board */
33int unmove(int x, int y) {
34 return (board[x][y] = 0),
35 (cols[x]+=player),
36 (rows[y]+=player),
37 (diags[(x==y)?0:2]+=player),
38 (diags[(x+y)==(N-1)?1:2]+=player),
39 (player = -player),
40 moves++;
41}
42 
43/* Evaluates a position: returns +N if red wins, -N if blue wins or 0 */
44int evaluate(void) {
45 for(x=0;x<N;x++) {
46 if ( (abs(cols[x]) == N) || (abs(rows[x]) == N) ||
47 (abs(diags[0]) == N) || (abs(diags[1]) == N))
48 return
49 IF(abs(cols[x]) == N) THEN
50 cols[x]
51 ELSE
52 IF(abs(diags[0]) == N) THEN
53 diags[0]
54 ELSE
55 IF(abs(diags[1]) == N) THEN
56 diags[1]
57 ELSE
58 rows[x]
59 ENDIF
60 ENDIF
61 ENDIF;
62 }
63 return 0;
64}
65 
66int alphabeta(const int a, const int b, const int horizon_distance) {
67 int n = 0, value = -N, best_value = -N, lower = a, upper = b, score = player*evaluate();
68 
69 /* Maximum search depth */
70 if (horizon_distance==0 || score!=0) {
71 return score;
72 }
73 
74 /* Evaluate each move in turn */
75 for (n=0; n<N*N; n++) if (!board[n%N][n/N]) {
76 move(n%N, n/N),
77 (value=-alphabeta(-upper, -lower, horizon_distance-1)),
78 unmove(n%N, n/N),
79 
80 /* Is this move better than one found earlier? */
81 IF(value>best_value) THEN
82 (best_value = value),
83 
84 /* Good enough to update our evaluation of the position? */
85 IF(best_value>lower) THEN
86 lower = best_value
87 ELSE
88 0
89 ENDIF,
90 
91 /* Abort if this variation is worse than one we examined before */
92 IF(best_value>=upper) THEN
93 n=N*N+1
94 ELSE
95 0
96 ENDIF
97 ELSE
98 0
99 ENDIF;
100 }
101 return best_value;
102}
103 
104/* Rather stupid alpha-beta search; doesn't do minimal window searches and
105 * doesn't handle fail high or fail low events.
106 */
107int cmove(void) {
108 for(value=best_value=-N*N, best_move=0, n=0; n<N*N; n++) if (!board[n%N][n/N]) {
109 (move(n%N, n/N)),
110 (value=-alphabeta(-N, N, moves)),
111 (unmove(n%N, n/N)),
112 
113 IF(value>best_value) THEN
114 (best_value=value),
115 (best_move=n)
116 ELSE
117 0
118 ENDIF;
119 }
120 
121 return move(best_move%N, best_move/N);
122}
123 
124int main(void)
125{
126 IF(allegro_init() || install_keyboard() || (install_mouse()==0) || set_gfx_mode(GFX_AUTODETECT_WINDOWED, N*40, N*40, 0, 0)) THEN
127 allegro_message("Error initialising\n"), exit(0), 0
128 ELSE
129 show_mouse(screen), (int)memset(board,0, sizeof board)
130 ENDIF;
131 
132 while (!key[KEY_ESC] && !evaluate() && moves) {
133 IF(player==-1) THEN
134 cmove()
135 ELSE
136 rest(10)
137 ENDIF;
138 old_mouse_b =
139 IF(!(mouse_b&1) && (old_mouse_b&1)) THEN
140 IF(board[mouse_x/40][mouse_y/40]==0) THEN
141 move(mouse_x/40, mouse_y/40), 0
142 ELSE
143 mouse_b
144 ENDIF
145 ELSE
146 mouse_b
147 ENDIF;
148 
149 /* The display loop draws a bit more than it has to, but that's ok */
150 for(x=0;x<N*N;x++)
151 hline(screen, 0, x*40, 40*N, 15),
152 vline(screen, x*40, 0, 40*N, 15),
153 circlefill(screen, 40*(x%N)+20, 40*(x/N)+20, 15, BOARD_COLOUR(board[x%N][x/N]));
154 }
155 
156 return textprintf_centre_ex(screen, font, N*40/2, N*40/2, 15, 0, "%s", (evaluate()==0)?"Draw":(evaluate()>0)?"Red wins":"Blue wins"), readkey(), 0;
157}
158END_OF_MAIN()

Untested for N>3.

PS. Oh, in case you were wondering, it's quite unbeatable.

Go to: