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.
There is nothing attached.
]]>Hmm...
There ought to have been.
Trying again.
EDIT:
Now there is.
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.)
]]>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.
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"
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.
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.
Charlie beat me because the coordinates are messed up. 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.
]]>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:
Charlie beat me because the coordinates are messed up. 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.
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!
Well my compiler didn't enjoy it, but it compiled.
Like I said, its quite ugly.
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)
]]>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.
]]>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.
"Beat my noughts" sounds... naughty.
]]>...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.
]]>
Obviously when I intentionally don't repeat winning sequences.
]]>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 | |
19 | int 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 */ |
22 | int 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 */ |
33 | int 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 */ |
44 | int 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 | |
66 | int 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 | */ |
107 | int 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 | |
124 | int 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 | } |
158 | END_OF_MAIN() |
Untested for N>3.
PS. Oh, in case you were wondering, it's quite unbeatable.
]]>