Computer Science Canada

Summer AI Challenge

Author:  bugzpodder [ Sun Jun 01, 2003 9:31 pm ]
Post subject:  Summer AI Challenge

this is better than "just make any game you want" cuz we have an objective and in the end we can actually have real tournaments and so forth.

I propose a challenge of snakes game. basically we have an NxN board, and we have some players at random starting locations. for each move you are given the position of the board, and you have to decide which way to go: North, East, South, West. then which ever direction you've chosen, that square will be occupied by you. you lose if you move into a square thats preoccupied (a wall, yourself, someone else).

now coordination, we have basically two choices: stdout or turing. stdout will mean like languages such as C++,Java,Pascal can be used. its hard to connect AI made for stdout with AI made in turing.

i think i better stick to turing cuz everyone here knows turing, and if you know C++ you can always convert it to turing. i'll write up the engine when exams are over. it'll be really fun, we did this in stage 2. if you *really* want to use C++ stick a message here.

i'll run a competition at end of august or something. the basic format is make a class (if you havent made one before, dont worry, i'll write an example up and all you gotta do is modify the main procedure)

Author:  Martin [ Sun Jun 01, 2003 9:33 pm ]
Post subject: 

It's a 1:1 move ratio right?

Author:  bugzpodder [ Mon Jun 02, 2003 7:35 am ]
Post subject: 

yes.

Author:  Martin [ Mon Jun 02, 2003 7:40 am ]
Post subject: 

Alright, just a couple more questions. First of all, are there walls anywhere or just on the borders? And secondly, how do we do this so that it allows for the other player to move?

Author:  bugzpodder [ Mon Jun 02, 2003 4:22 pm ]
Post subject: 

my original plan was to have walls on the sides only but now i changed my mind. it would be *VERY* interesting to have some walls in the middle of the board (i can code up a map editor also hehe), or even randomly generated walls (maybe symmetrical, maybe asymmetrical)!!

and as to the move sequences, the players will be named in some (maybe random) order such that player 1 gets to move first, then player 2 and so on. or maybe i'll decide simutaneous moves, but then its hard to predict if two players will get crashed into each other. but this is always an option

Author:  Catalyst [ Mon Jun 02, 2003 4:31 pm ]
Post subject: 

sounds very interesting im in for sure

Author:  bugzpodder [ Mon Jun 02, 2003 4:43 pm ]
Post subject: 

i'll have sample codes up very soon. in fact i am working on them right now.

Author:  Tony [ Mon Jun 02, 2003 5:27 pm ]
Post subject: 

yeah, I wanted to have some AI challange. It would be really cool to host an AI turnament. I'm going to be in too. Though it would be nice if more people participated.

Author:  bugzpodder [ Mon Jun 02, 2003 6:20 pm ]
Post subject: 

well, we'll see how this one turns out. a simple AI shouldnt even take long to code. 2 days is almost sufficient, but this engine is going to take me a while, depending on if i am busy. i say probably before exams it will be done so you guys can test your AIs.



you cant stop me from using C++ type arrays, comments and semicolons. so bite me

here is a sample AI code that you can use. read the instructions inside

code:

look at later posts for updated code

if you have any questions/comment/concerns feel free to let me know

Author:  bugzpodder [ Mon Jun 02, 2003 8:02 pm ]
Post subject: 

btw i added a function AIName in the code above so I could possibly use that for a rating system.

Author:  Martin [ Mon Jun 02, 2003 8:13 pm ]
Post subject: 

You'd have to be careful about randomly placed walls...wouldn't be too fair if somebody started surrounded. Another cool idea would be to run the ai's through our little maze generator Wink

Author:  Tony [ Mon Jun 02, 2003 9:45 pm ]
Post subject: 

wouldn't be much of a point then... You'd have to specify thing kind of thing in mission statment (cant expect open field AI to run through maze) and then each program just finds the longest path and follows it...

Author:  bugzpodder [ Mon Jun 02, 2003 9:50 pm ]
Post subject: 

i am not talking about a lot of walls, just a few. if they are randomly generated, they could be randomly placed blocks. or else they will be symmetrical about the center of the field so no one gets an advantage

Author:  Tony [ Mon Jun 02, 2003 10:00 pm ]
Post subject: 

I think for it to be completely fair, starting positions should be random, but symetrical, and walls should also be symetrical along the same axis.

Author:  bugzpodder [ Mon Jun 02, 2003 10:05 pm ]
Post subject: 

even when there is no walls in the middle of the game, you still cant guarentee it to be "fair" maybe some algorithms like to be closer with an opponent and some algorithms would be better off starting away from others. some maybe be better closer ot the walls some may like the center more. so its hard to be "fair" and only random is really fair.

Author:  bugzpodder [ Mon Jun 02, 2003 10:06 pm ]
Post subject: 

a good AI should deal with a lot of situations, at least i would think so.

Author:  Tony [ Tue Jun 03, 2003 10:10 am ]
Post subject: 

yeah... and you could determine your relative starting position and execute different strategies if you'd like 8)

Author:  bugzpodder [ Tue Jun 03, 2003 8:12 pm ]
Post subject: 

i am trying to write the snake engine and i am stuck on some problems. i want to have easy access of everyone's AI (ie store the pointers in an array) but stupid turing cant handle this. so in the end, i will probably put the whole engine into the SampleAI. but for now I'll leave it be. anyone have other bright ideas?

Author:  Catalyst [ Tue Jun 03, 2003 8:34 pm ]
Post subject: 

what type of pointers are you talking about (to store in the array)
cpp or turing?

Author:  bugzpodder [ Tue Jun 03, 2003 8:56 pm ]
Post subject: 

turing. everyone is going to have seperate classes and i am trying to find a way to combine everything.

here is the *NEW* samplesnake code, which i added one line of label 0:

and the engine, which allows you to test your own AI. its not finalized.

the simpliest way to use it is to not modify the name of the SampleSnakeAI and just modify the Think() procedure in it.


code:

look at later posts for updated code

code:

look at later posts for updated code


Author:  Catalyst [ Tue Jun 03, 2003 9:19 pm ]
Post subject: 

i like the ; and () Very Happy

u could write a generic class
and have the users classes overide the base (like virtual functions)
class using deferred

or

you could have the functions and procedure outside the program
and brought in using parameters to the class

Author:  bugzpodder [ Tue Jun 03, 2003 9:27 pm ]
Post subject: 

well these things sound promising i am going to try it in the next few days. anywayz here is a screen shot of my AI, based on the one i made in stage 2 (the 2nd zig-zag one, its my trademark Wink). the main part was only 10 lines Wink
Posted Image, might have been reduced in size. Click Image to view fullscreen.
Posted Image, might have been reduced in size. Click Image to view fullscreen.

Author:  Catalyst [ Tue Jun 03, 2003 9:30 pm ]
Post subject: 

ur sample ai stops after a few turns

Author:  Catalyst [ Tue Jun 03, 2003 9:33 pm ]
Post subject: 

nvr mind, didnt know they turned on themselves

Author:  Tony [ Tue Jun 03, 2003 9:38 pm ]
Post subject: 

thats because his sample AI moves randomly... so it crashes into itself and stops

Author:  bugzpodder [ Tue Jun 03, 2003 9:52 pm ]
Post subject: 

well i hurriedly made these things so everyone could start making their AI and use the program to test it out. let me know when you've made something.

Author:  Catalyst [ Tue Jun 03, 2003 11:35 pm ]
Post subject: 

edit: see below

Author:  bugzpodder [ Wed Jun 04, 2003 7:43 am ]
Post subject: 

dead link.

Author:  Catalyst [ Wed Jun 04, 2003 2:52 pm ]
Post subject: 

two ai's i tried out

new algo:

Posted Image, might have been reduced in size. Click Image to view fullscreen.

old algo:

Posted Image, might have been reduced in size. Click Image to view fullscreen.

Author:  bugzpodder [ Wed Jun 04, 2003 5:07 pm ]
Post subject: 

Catalyst wrote:
i like the ; and () Very Happy

u could write a generic class
and have the users classes overide the base (like virtual functions)
class using deferred

or

you could have the functions and procedure outside the program
and brought in using parameters to the class


I basically want something that without modifying my code, I could specify which AIs to use. or if thats not possible then i need to at least have the pointers/functions stored in an array so i could loop through them in my code. i am not interested in having seperate calls to each AI using their name. anyone?

Author:  PaddyLong [ Wed Jun 04, 2003 5:07 pm ]
Post subject: 

from what I found from trying this, your values for north and south are backwards..

Author:  bugzpodder [ Wed Jun 04, 2003 5:08 pm ]
Post subject: 

Catalyst wrote:
i like the ; and () Very Happy

u could write a generic class
and have the users classes overide the base (like virtual functions)
class using deferred

or

you could have the functions and procedure outside the program
and brought in using parameters to the class


I basically want something that without modifying my code, I could specify which AIs to use. or if thats not possible then i need to at least have the pointers/functions stored in an array so i could loop through them in my code. i am not interested in having seperate calls to each AI using their name. anyone?

Author:  bugzpodder [ Wed Jun 04, 2003 5:13 pm ]
Post subject: 

i can think of one way, is where we can have compiled programs and I'll use Sys.Exec to execute the programs, which will read in a file and output to a file. but then again, i think turing does not way the command executed by Sys.Exec to finish and goes on, right?

Author:  bugzpodder [ Wed Jun 04, 2003 5:15 pm ]
Post subject: 

PaddyLong wrote:
from what I found from trying this, your values for north and south are backwards..
i dont think so. 0,0 is at the top left corner.

Author:  Catalyst [ Wed Jun 04, 2003 5:19 pm ]
Post subject: 

you can have the users load their Think funcs into a generic class


oh, and in turing bottom-right is 0,0

Author:  PaddyLong [ Wed Jun 04, 2003 5:26 pm ]
Post subject: 

I think what catalyst suggested is probably the best way.

oh yeah, you can have an array of pointers to classes which I think you said you couldn't in a previous post...

ex...
code:

var classarray : array 1 .. 4 of ^someclass
for q:1..4
  new classarray (q)
end for


so just have like a Snake or Player class that has their X, Y position as well as their current direction

then for the think function, just pass up the X, Y positions of the other players as a parameter (probably need to have getPos functions in the Snake class that just results the X and Y position - this is so that cou can actually fill this array that you are passing to the think function with the data from all of the Snake objects)

Author:  bugzpodder [ Wed Jun 04, 2003 5:33 pm ]
Post subject: 

Catalyst, could you give an simple example?
PaddyLong, I am well aware of that. but since every AI have a *different* class name, then it is impossible to do what you suggested, since I want an array of pointers to *different classes*. inheritance/implementation of classes still results a different class (ie a class of different name) and therefore i cant put them in an array, at least i dont think. a run-time solution is even more impossible, since now i have to basically replace class names with strings.

Author:  PaddyLong [ Wed Jun 04, 2003 5:45 pm ]
Post subject: 

lol I just figured out what you were talking about... wasn't thinking of how each of the things wouldn't have its unique AI if they all were one class

what is the maximum number of AI's you plan to have competing at once? Like are you going to do it as a sort of tournament ladder or just have everyone in on a big free for all?

Author:  bugzpodder [ Wed Jun 04, 2003 5:50 pm ]
Post subject: 

i'd like to have a big free for all but looks like that its not really possible unless manually modify the Engine for all AIs. which is not good.

but pointers, boiled on to the end, are really only integers/addresses. i was wondering if i could exploit this fact so i could at least have an areaay of pointers to different classes

Author:  PaddyLong [ Wed Jun 04, 2003 5:59 pm ]
Post subject: 

maybe... but each class might take up a different amount of memory and so you might not be able to

Author:  bugzpodder [ Wed Jun 04, 2003 6:00 pm ]
Post subject: 

pointers are not classes, they are merely pointers, that stores an address (just a simple integer) of a memory. at least thats how it works in C++

Author:  PaddyLong [ Wed Jun 04, 2003 6:12 pm ]
Post subject: 

yeah I know what pointers are... but liek you might not just be able to guess where the addresses of the different classes are based on what the address of a given class is

Author:  bugzpodder [ Wed Jun 04, 2003 6:18 pm ]
Post subject: 

i have no idea what you mean by "guessing" in C++ you dont need to guess, just declare it and you have the address (i mean, you either know the address or you dont, you cant "guess"). cept turing wont let you do this...

Author:  PaddyLong [ Wed Jun 04, 2003 6:19 pm ]
Post subject: 

nm, I now udnerstadn what you were talking about by having an array of pointers

Author:  bugzpodder [ Wed Jun 04, 2003 6:27 pm ]
Post subject: 

got it, turing use pointer to "anyclass" to do this. but i still have to modify my program each time i want to use a class of different name. anyone know how to avoid this?

Author:  bugzpodder [ Wed Jun 04, 2003 7:07 pm ]
Post subject: 

we'll see how this works out. if all else fails, i'd have to go with C++.

Author:  Catalyst [ Wed Jun 04, 2003 7:08 pm ]
Post subject: 

I dont think this can be done with fcns but im not sure
you should be able to workaround using a proc tho
code:
proc blank
end blank

class AIDemo

    export Load, Think

    var Think : proc blank

    proc Load (proc f)
        Think := f
    end Load

end AIDemo

var demo : ^AIDemo
new demo

proc RThree
    put "It Works"
end RThree

demo -> Load (RThree)

for i : 1 .. 2
    demo -> Think
end for

just loadup the instances then they can be run thru the array

Author:  bugzpodder [ Wed Jun 04, 2003 7:58 pm ]
Post subject: 

then i guess it isnt as different as this. anywayz here is the newest version of code where i've made use of inheritance to solve this problem. there will probably be no further changes made to the BaseAI.

the only thing you should be changing is the include file name and the stuff in the Reset procedure (class name) for your own Class

code:


/*Coded by Bugz Podder
 Version 0.02 (look at version number to see if you have latest code!)

 --Ver 0.02 if a player has no moves, the engine now takes care of it
 --Ver 0.01 first official version
 */

randomize
View.Set ("graphics:550;550");


class BaseSnakeAI

    /*
     This is a sample AI for Bugz' Snake Game

     for each move you have 4 directions, NORTH EAST SOUTH OR WEST
     you lose if you attempts to go into a square that is not free (occupied by a wall or a snake)
     Draws are possible.

     in the beginning of the game, you are given the number of players, your player number, board size
     the board state (could potentially have some walls in the middle but definately an outer wall,
     location of all the players, as well as game type)

     for each move you are given a list of updated positions (which the procedure
     already took care of) as well as you are asked for a direction to go.

     Real-Time game has one extra rule that Turned-Based doesnt have is if two snakes
     attempts to go onto the same square at the same turn, both will *DIE*


     what you *CANT* change
     values for NORTH, EAST, SOUTH, WEST
     the AIName, Reset and Move procedure's name as well as what they do

     anythin else you can pretty much change, including variable names and so on.


     */

    export Reset, Move, AIName;
    const SOUTH := 1;
    const EAST := 2;
    const NORTH := 3;
    const WEST := 4;

    var NUM_PLAYERS, MY_NUMBER, BOARD_SIZE, GAME_TYPE : int;
    var board : array 0 .. 251, 0 .. 251 of int;
    var playerX, playerY : array 1 .. 50 of int;
    var playerAlive : array 1 .. 50 of boolean;


    /* your id number is MY_NUMBER, and playerX, playerY stores X and Y values of every player
     playerAlive tells you if a player is alive.  to access your info, such as your
     current location, use playerX(MY_NUMBER) and playerY(MY_NUMBER)

     board (i,j) has a value of -1 if its a wall, 0 if its empty, or 1..50 depending on the
     player who occupied it

     GAME_TYPE: - 0 if it is Turn-Based
     - 1 if it is Real-Time

     */
    deferred fcn AIName () : string

    proc Reset (gtype : int, nump : int, mynum : int, size : int, brd : array 0 .. 251, 0 .. 251 of int,
            Xcrd : array 1 .. 50 of int, Ycrd : array 1 .. 50 of int)

        GAME_TYPE := gtype;
        NUM_PLAYERS := nump;
        MY_NUMBER := mynum;
        BOARD_SIZE := size;
        board := brd;
        playerX := Xcrd;
        playerY := Ycrd;

       for i : 1 .. NUM_PLAYERS
            playerAlive (i) := true;
        end for

    end Reset

    deferred fcn Think () : int


    fcn Move (dir : array 1 .. 50 of int) : int
        for i : 1 .. NUM_PLAYERS
            case dir (i) of
                label 0 :
                label 1 :
                    playerY (i) -= 1;
                label 2 :
                    playerX (i) += 1;
                label 3 :
                    playerY (i) += 1;
                label 4 :
                    playerX (i) -= 1;
                label :
                    playerAlive (i) := false;
            end case

            board (playerX (i), playerY (i)) := i;
        end for

        result Think ()
    end Move

end BaseSnakeAI

include "SampleSnakeAI.t"




class SnakeEngine
    import BaseSnakeAI, SampleSnakeAI
    export Run, Reset


    const SOUTH := 1;
    const EAST := 2;
    const NORTH := 3;
    const WEST := 4;

    const dir : array 1 .. 4, 0 .. 1 of int := init (0, -1, 1, 0, 0, 1, -1, 0);


    var NUM_ALIVE, NUM_PLAYERS, BOARD_SIZE, GAME_TYPE, NUM_TURN, DELAY_TIME, OFFSET : int;

    var board : array 0 .. 251, 0 .. 251 of int;
    var playerX, playerY, playerDir, beginDir : array 1 .. 50 of int;
    var playerAlive : array 1 .. 50 of boolean;
    var ptr : array 1 .. 50 of ^BaseSnakeAI

    proc Reset (nump, brdsize, gametype, delaytime : int)
        NUM_PLAYERS := nump;
        BOARD_SIZE := brdsize;
        GAME_TYPE := gametype;
        DELAY_TIME := delaytime;

        OFFSET := 20;

        %calculate offset

        var ptr1 : ^SampleSnakeAI
        var ptr2 : ^SampleSnakeAI
        var ptr3 : ^SampleSnakeAI
        var ptr4 : ^SampleSnakeAI
        new ptr1
        new ptr2
        new ptr3
        new ptr4
        ptr (1) := ptr1;
        ptr (2) := ptr2;
        ptr (3) := ptr3;
        ptr (4) := ptr4;

    end Reset

    fcn freesp (x, y : int) : int
        var w := 0;
        for i : 1 .. 4
            if board (x + dir (i, 0), y + dir (i, 1)) = 0 then
                w += 1;
            end if
        end for
        result w
    end freesp

    proc Run ()
        for i : 1 .. BOARD_SIZE
            for j : 1 .. BOARD_SIZE
                board (i, j) := 0;
            end for
        end for
        for i : 0 .. BOARD_SIZE + 1
            drawfillbox (i * 10 - 5 + OFFSET, -5 + OFFSET, i * 10 + 5 + OFFSET, 5 + OFFSET, black);
            drawfillbox (-5 + OFFSET, i * 10 - 5 + OFFSET, 5 + OFFSET, i * 10 + 5 + OFFSET, black);
            drawfillbox (i * 10 - 5 + OFFSET, (BOARD_SIZE + 1) * 10 - 5 + OFFSET, i * 10 + 5 + OFFSET, (BOARD_SIZE + 1) * 10 + 5 + OFFSET, black);
            drawfillbox ((BOARD_SIZE + 1) * 10 - 5 + OFFSET, i * 10 - 5 + OFFSET, (BOARD_SIZE + 1) * 10 + 5 + OFFSET, i * 10 + 5 + OFFSET, black);
            board (0, i) := -1;
            board (i, 0) := -1;
            board (i, BOARD_SIZE + 1) := -1;
            board (BOARD_SIZE + 1, i) := -1;
        end for
        for i : 1 .. NUM_PLAYERS
            var RandX, RandY : int
            loop
                RandX := Rand.Int (1, BOARD_SIZE);
                RandY := Rand.Int (1, BOARD_SIZE);
                exit when board (RandX, RandY) = 0
            end loop
            playerX (i) := RandX;
            playerY (i) := RandY;
            playerAlive (i) := true;
            playerDir (i) := 0;

        end for

       

        for i : 1 .. NUM_PLAYERS
            drawfillbox (playerX (i) * 10 - 5 + OFFSET, playerY (i) * 10 - 5 + OFFSET, playerX (i) * 10 + 5 + OFFSET, playerY (i) * 10 + 5 + OFFSET, i);
            ptr (i) -> Reset (GAME_TYPE, NUM_PLAYERS, i, BOARD_SIZE, board, playerX, playerY)
        end for

        var move : int := 0;
        NUM_ALIVE := NUM_PLAYERS;
        NUM_TURN := 0;
        var winner := -1;
        loop
            NUM_TURN += 1;
            exit when NUM_ALIVE = 0
            if NUM_ALIVE = 1 and winner = -1 then
                for i : 1 .. NUM_PLAYERS
                    if playerAlive (i) then
                        winner := i;
                    end if
                end for
            end if
            if GAME_TYPE = 0 then
                beginDir := playerDir;
            end if
            for i : 1 .. NUM_PLAYERS
                if playerAlive (i) = true then
                    if freesp (playerX (i), playerY (i)) = 0 then
                        playerAlive (i) := false;
                        playerDir (i) := -1;
                        NUM_ALIVE -= 1;
                    else
                        if GAME_TYPE = 0 then
                            move := ptr (i) -> Move (playerDir);
                        elsif GAME_TYPE = 1 then
                            move := ptr (i) -> Move (beginDir);
                        end if
                        playerDir (i) := move;
                        if move > 0 and move < 5 and board (playerX (i) + dir (move, 0), playerY (i) + dir (move, 1)) = 0 then

                            playerX (i) += dir (move, 0);
                            playerY (i) += dir (move, 1);
                            board (playerX (i), playerY (i)) := i;
                            drawfillbox (playerX (i) * 10 - 5 + OFFSET, playerY (i) * 10 - 5 + OFFSET, playerX (i) * 10 + 5 + OFFSET, playerY (i) * 10 + 5 + OFFSET, i);
                            if NUM_TURN > 1 then
                                drawline (playerX (i) * 10 + OFFSET, playerY (i) * 10 + OFFSET, (playerX (i) - dir (move, 0)) * 10 + OFFSET, (playerY (i) - dir (move, 1)) * 10 + OFFSET, black);
                            end if
                            delay (DELAY_TIME);
                        else
                            playerAlive (i) := false;
                            playerDir (i) := -1;
                            NUM_ALIVE -= 1;
                        end if
                    end if
                end if
            end for
        end loop

        if winner = -1 then
            put "Tie game!";
        else
            put "Winner is " + ptr (winner) -> AIName ();
        end if
    end Run


end SnakeEngine

var x : ^SnakeEngine
new x

x -> Reset (4, 50, 0, 0);  /* number of players, board size, game type (leave it at 0 for now), delay)*/
x -> Run ();



here is a sample of the AI
code:

/*
**************************************************************
*  AI Name: SampleAI                                         *
*  Coder:   Bugz Podder                                      *
**************************************************************
*/
class SampleSnakeAI
inherit BaseSnakeAI

   body fcn AIName():string
       result "SampleAI"
   end AIName

   
    body fcn Think () : int
        /*This is your main AI, do whatever you want*/
        if GAME_TYPE = 0 then  /* Turn-Based */
            result Rand.Int (1, 4)
        elsif GAME_TYPE = 1 then  /* Real-Time */
            result Rand.Int (1, 4)
        end if

    end Think

end SampleSnakeAI

Author:  Catalyst [ Sat Jun 07, 2003 3:51 pm ]
Post subject: 

this would be cool if it ran over the net

Author:  Martin [ Sat Jun 07, 2003 7:50 pm ]
Post subject: 

Apparently the net module works a bunch better now, so we might be able to.

Author:  PaddyLong [ Sat Jun 07, 2003 8:04 pm ]
Post subject: 

can we add functions to our class? just ones for checking things for our AI ... like boolean ones to see if something more than a basic if statement is true

Author:  bugzpodder [ Sun Jun 08, 2003 1:18 pm ]
Post subject: 

of course, you can add anything you'd like. net module ehh, i'll take a look at that.

Author:  bugzpodder [ Thu Aug 07, 2003 8:47 pm ]
Post subject: 

My AI and the engine (i dont know if its the same as as posted b4)
anyways to use your own engine, you have to change two places in the code (Thats what i mean when i said in the other post, the problem was)

one place is a bunch of replace codes, and one place is a bunch of pointer declaration. just change the class name to your own class. or you can do a search and replace (search for FunAI)

Author:  Catalyst [ Thu Aug 07, 2003 9:56 pm ]
Post subject: 

heres the one i coded some of the code is unecessary im not gonna edit it now

Author:  PaddyLong [ Fri Aug 08, 2003 1:19 pm ]
Post subject: 

here's my snake ai


: