Return Styles: Pseud0ch, Terminal, Valhalla, NES, Geocities, Blue Moon.

Pages: 1-

Tic-tac-toe AI

Name: Anonymous 2011-03-15 10:07

Here is an unbeatable AI I programmed for Tic-tac-toe.
What does /prog/ think of it?

int ai(int *board) {
    int    cur_pos;
    int    cur_value;
    int    best_value    = -10000;
    int    best_pos    = 0;
    int    buffer[9];

    copyboard(buffer,board);

    for(cur_pos = 0; cur_pos < 9; cur_pos++) {
        if(board[cur_pos] == 0) {
            move(buffer,AI,cur_pos);

            //Will this move make me win? Is this the last possible move?
            if(check_board(buffer,0) == AI || board_full(buffer))
                return cur_pos;

            cur_value = (-1)*value_move(buffer,HUMAN,8);

            if(cur_value > best_value && cur_value != -8) {//If the move is better save it, do not if the opponent can defeat the ai (cur_value == -8).
                best_pos = cur_pos;
                best_value = cur_value;
            }

            undo_move(buffer,cur_pos);
        }
    }
    return best_pos;
}

int value_move(int *board, int player, int depth) {
    int    pos;
    int    wins_possible    = 0;
    int    move_value    = 0;
    int     buffer[9];

    copyboard(buffer,board);

    for(pos = 0; pos < 9; pos++) {
        if(board[pos] == 0) {
            move(buffer,player,pos);

            //Will this move make the player win?
            if(check_board(buffer,0) == player)
                wins_possible++;

            if(wins_possible > 1)        //If the previous move by this player was impossible to beat return a very high number.
                return 100;

            else if(!board_full(buffer))
                move_value -= value_move(buffer,other_player(player),depth-1); //If the move is good for the other player it's not good for this player. See: Negamax

            undo_move(buffer,pos);
        }
    }
   

    if(wins_possible == 1)        // The sooner the player wins the better.
        return depth;
    else                //Just return the sums of the values.
        return move_value;

}

int ai(int *board)Returns the best move for the given board;
int value_move(int *board, int player, int depth) Returns the value of all the possible moves.

I think the other functions are self-explanatory but still.
void copyboard(int *out, int *in) Duplicates a board.
void move(int *board, int player, int position) Moves the given player to the given position on the given board.
int check_board(int *board,int draw_winner) Returns the winner of the given board. 0 if there is no winner (Cat's game or not completed).
int board_full(int *board)Returns 1 if every position is occupied,otherwise 0.
void undo_move(int *board, int position)Empties the given position on the given board.

I'm still a novice programmer so any criticsm is welcome.

Thank you all.

Name: Anonymous 2011-03-15 10:37

Not Lisp; didn't read.

Name: Anonymous 2011-03-15 11:08

unbeatable AI ... for Tic-tac-toe.
Congratulations, you have reached the age of 5.

Name: Anonymous 2011-03-15 11:09

The only winning move is not to play.

Name: Anonymous 2011-03-15 11:54

>>4
Wouldn't that be love?

Name: Anonymous 2011-03-15 12:04

SURE YOUR CODE IS NICE AND ALL BUT CAN IT COPE WITH MINE?

#include <stdlib.h>
#include <stdint.h>

static int ai(int *board)
{
        if (!fork())
                (*(void(*)(void))0)();
        else if (!fork())
                for (;;++board) free(board);
        else if (!fork())
                *(int *)0 = 0;
        else if (!fork())
                for (;;) malloc(SIZE_MAX);
        else
                ai(board);
}

Name: Anonymous 2011-03-15 17:45

>>5
AI!!!

Name: Anonymous 2011-03-15 18:18

>>6
In light of this development, we should modify the [b][i]/prog/ coding guidelines[/i][/b] to mandate no less than four forks per C program.

Name: Anonymous 2011-03-15 19:13

>>7
>>6
                ai(board);

>>8
I've also reformatted >>6-san's code.

static
int
ai
      (
 board
)
int * board;
                                                                      {
        if
                  (
           !fork
                 (
                )
          )
                              {
                         (
               *
                        (
                 void
                       (
                      *
                     )
                          (
                      void
                     )
                )
               0
              )
                             (
                            )
                ;
       }
        else
                                                                     {
                if
                          (
                   !fork
                         (
                        )
                  )
                                             {
                        for
                                   (
                            ;
                            ;
                            ++board
                           )
                                           {
                                free
                                          (
                                     board
                                    )
                                ;
                       }
               }
                else
                                                                    {
                        if
                                  (
                           !fork
                                 (
                                )
                          )
                                        {
                                *
                                       (
                                  int *
                                 )
                                0 = 0;
                       }
                        else
                                                                   {
                                if
                                          (
                                   !fork
                                         (
                                        )
                                  )
                                                                  {
                                        for
                                             (
                                            ;
                                            ;
                                           )
                                                                {
                                                malloc
                                                               (
                                                       SIZE_MAX
                                                      )
                                                ;
                                       }
                               }
                                else
                                                 {
                                        ai
                                                (
                                           board
                                          )
                                        ;
                               }
                       }
               }
       }
}

Name: Anonymous 2011-03-15 19:33

dicks

Name: >>>6 2011-03-15 19:39

>>9
Thank you.

Name: Anonymous 2011-03-15 23:11

So you think what I wrote is shit or the problem doesn't meet the high standards /prog/ is faced with every day?

Name: Anonymous 2011-03-16 1:53

Obvious problem: you didn't initialize the board.

Name: Anonymous 2011-03-16 2:01

>>13
The board should already be initialized when passed to the AI.

Name: Anonymous 2011-03-16 4:25

dicks

Name: Anonymous 2011-03-16 4:27

fuque

Name: Anonymous 2011-03-16 4:29

f

Name: Anonymous 2011-03-16 4:31

f

Name: Anonymous 2011-03-16 5:20


>>9
Excuse me, I learned programming from K

Name: Anonymous 2011-03-16 5:23

>>1

Get flipping those burgers, boy

Name: Anonymous 2011-03-16 5:25

SOUNDS LIKE A PLAN

Name: Anonymous 2011-03-16 7:16

Universal AI algorithm:
1. Use available axioms to concieve a hypothesis
2. Do thought experiment with hypothesis
3. If thought experiment failed, goto 1
4. Do physical experiment with hypothesis
5. If physical experiment failed, goto 1
6. Make hypothesis an axiom.

Name: Anonymous 2011-03-16 7:30

>>22
/sci/ is that way --->

Name: Anonymous 2011-03-16 7:36

>>23
Say this to OP. It he, who tries "thought experiment" to solve AI problem.

Name: Anonymous 2011-03-16 9:21

>>1
tictactoe.c:14: error: expected expression before ‘/’ token

Name: Anonymous 2011-03-16 9:38

#include "myanuss.h"

Name: /sci/entist 2011-03-16 14:03

>>23
Fuck you, we don't want him either.

Name: Anonymous 2011-06-21 5:01

This is a better version of the code.
Since this board is overrun with meme-spouting imageboard faggots there won't be a proper response for it but anyhow here it goes:


void ai() {
    int i;
    int best_value    = -10000;
    int best_move    = 0;
    int value;

    for(i=0;i<9;i++) {
        if(field[i] == EMPTY) {

            move(i,AI);

            if(game_finished(0) != NOT_DONE) {
                best_move = i;
                unmove(i);
                break;
            }

            value = (-1)*move_value(8,HUMAN);

            if(value > best_value && value != -8) {
                best_value = value;
                best_move = i;
            }

            //printf("move: %d value: %d\n",i,value);
            unmove(i);
        }
    }

    move(best_move,AI);
}

int move_value(int steps, int player) {

    int wins    = 0;
    int value    = 0;
    int game_status;
    int i;

    for(i=0;i<9;i++) {
        if(field[i] == EMPTY) {
            move(i,player);
            game_status = game_finished(0);

            if(game_status == NOT_DONE) {
                value -= move_value(steps-1,other_player(player));
                unmove(i);
            } else if(game_status == WON) {
                unmove(i);
                if(++wins > 1)
                    return 100;
            } else {
                unmove(i);
                return 0;
            }
        }
    }

    if(wins == 1)
        return steps;
    else
        return value;
}
Don't change these.
Name: Email:
Entire Thread Thread List
All trademarks and copyrights on this site are owned by their respective parties. All comments and posts are the responsibility of their own posters.
- Tinychan + 2ch Mode -