10
\$\begingroup\$

Notice

This challenge has ended and will not be re-judged, but feel free to post answers and test your program against the others with the Control Program!

The aim of this challenge is to make an AI to win a fight against another AI by strategically drawing a wall on a 25x25 grid to block the opponent.

Input

25 lines separated by and ending with ; as a command-line argument. This will include:

  • Empty spaces .
  • Walls #
  • Players 1 and 2 (The opponent is always 2)

Example

###############..........;..............#..........;..............#..........;..............#..........;..............#..........;...........1###..........;.........................;.........................;.........................;.........................;.........................;.........................;.........................;.........................;.........................;.........................;.........................;.........................;.........................;...................###...;...................#.##..;2..................#..#..;#..................##.#..;#...................#.###;....................#####;

which represents the following map:

###############..........
..............#..........
..............#..........
..............#..........
..............#..........
...........1###..........
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
...................###...
...................#.##..
2..................#..#..
#..................##.#..
#...................#.###
....................#####

Output

A string written to the console starting with the character representing the direction the AI wishes to turn. This is case sensitive!

  • North N
  • East E
  • South S
  • West W
  • Give up (Anything else)

Example

W

Game Rules

  • As the AIs move, they will leave a solid trail of walls behind them.
  • The players start in the top-left and bottom-right corners
  • The game lasts until any AI hits a wall or the AIs crash into each other.
    • An AI wins if their opponent crashes first
    • There is no winner or loser if the AIs both lose at the same time.
  • If an AI goes off one edge of the grid, they continue in the same direction from the other side.

Rankings

1st Place - FloodBot (Java, 12 wins)

2nd Place - FluidBot (Python, 9 wins)

3rd Place - FillUpBot (C++, 8 wins)

4th Place - AwayBot (Ruby, 5 wins)

5th Place - ArcBot (Python, 4 wins)

6th Place - BlindSnake (Batch, 2 wins)

6th Place - RandomBot (C#, 2 wins)

Control Program (Tested for Python 3.3.3)

The program is run with arguments of the two commands and a single argument ("" if not required) for the AIs eg. Control.py "ruby" "AwayBot.rb" "FillUpBot.exe" "". It can be downloaded here.

import sys, subprocess

Program1, Argument1, Program2, Argument2, Player1, Player2, Grid = sys.argv[1], sys.argv[2], sys.argv[3], sys.argv[4], [0, 0], [24, 24], [['.' for y in range(25)] for x in range(25)]
while True:
    Str  = ''
    for x in range(25):
        for y in range(25):
            if Grid[x][y] == '1' or Grid[x][y] == '2':
                Grid[x][y] = '#'
    Grid[Player1[0]][Player1[1]] = '1'
    Grid[Player2[0]][Player2[1]] = '2'
    for y in range(25):
        for x in range(25):
            Str += Grid[x][y]
        Str += ';'
    if Argument1 == '':
        move = subprocess.Popen([Program1, Str], stdout=subprocess.PIPE).stdout.read().decode('ASCII')[0]
    else:
        move = subprocess.Popen([Program1, Argument1, Str], stdout=subprocess.PIPE).stdout.read().decode('ASCII')[0]
    Lose1 = False
    if move == 'N':
        if Player1[1] > 0:
            Player1[1] -= 1
        else:
            Player1[1] = 24
    elif move == 'E':
        if Player1[0] < 24:
            Player1[0] += 1
        else:
            Player1[0] = 0
    elif move == 'S':
        if Player1[1] < 24:
            Player1[1] += 1
        else:
            Player1[1] = 0
    elif move == 'W':
        if Player1[0] > 0:
            Player1[0] -= 1
        else:
            Player1[0] = 24
    else:
        Lose1 = True
    if Grid[Player1[0]][Player1[1]] == '#' or Grid[Player1[0]][Player1[1]] == '2':
        Lose1 = True
    print('Player 1:', move)
    if Argument2 == '':
        move = subprocess.Popen([Program2, Str.replace('2','3').replace('1','2').replace('3','1')], stdout=subprocess.PIPE).stdout.read().decode('ASCII')[0]
    else:
        move = subprocess.Popen([Program2, Argument2, Str.replace('2','3').replace('1','2').replace('3','1')], stdout=subprocess.PIPE).stdout.read().decode('ASCII')[0]
    Lose2 = False
    if move == 'N':
        if Player2[1] > 0:
            Player2[1] -= 1
        else:
            Player2[1] = 24
    elif move == 'E':
        if Player2[0] < 24:
            Player2[0] += 1
        else:
            Player2[0] = 0
    elif move == 'S':
        if Player2[1] < 24:
            Player2[1] += 1
        else:
            Player2[1] = 0
    elif move == 'W':
        if Player2[0] > 0:
            Player2[0] -= 1
        else:
            Player2[0] = 24
    elif Lose1:
        Lose2 = True
    else:
        Lose2 = True
    print('Player 2:', move)
    print(Str.replace(';', '\n'))
    if Grid[Player2[0]][Player2[1]] == '#':
        Lose2 = True
    if Lose1 and Lose2:
        print('Draw!')
        break
    elif Lose1:
        print('Player 2 wins!')
        break
    elif Lose2:
        print('Player 1 wins!')
        break
\$\endgroup\$
31
  • 5
    \$\begingroup\$ You need to add an API and a test program NOW! How else will we be able to write code to interface with it? Flagging as unclear. \$\endgroup\$ Apr 25, 2014 at 15:37
  • 3
    \$\begingroup\$ Seems like a nice challenge, but eh.., that 'testing program' (its the controller program right?), what language is it and do I have to compile it? Please tell us how to use it. \$\endgroup\$
    – Herjan
    Apr 25, 2014 at 16:39
  • 3
    \$\begingroup\$ Seems like an interesting challenge that I won't compete due to (A) OS restrictions (Linux-only user) and (B) language restrictions (primarily Fortran but working on learning Lua) \$\endgroup\$
    – Kyle Kanos
    Apr 25, 2014 at 18:07
  • 2
    \$\begingroup\$ @Doorknob I am installing Ruby now, and am thinking about learning to use it anyway. \$\endgroup\$
    – kitcar2000
    Apr 25, 2014 at 19:05
  • 2
    \$\begingroup\$ @kitcar2000 ah I see that's fair enough. alternatively you could provide it via stdin, but using a single line as an argument is fair game. That being said, since your map is fixed size, you don't need any delimiter at all. \$\endgroup\$ Apr 25, 2014 at 19:22

8 Answers 8

8
\$\begingroup\$

Floodbot

Java

This guy is all about avoidance. He doesn't care to try to trap the opponent, he just wants to live. To do that, he flood-fills each direction to see which way will lead to the biggest open area.

He also thinks the enemy is unpredictable, so he treats each square immediately surrounding them as already being a wall. If that leads to no possible direction, he falls back to the "actual" map.

public class Floodbot {

    boolean[][] walkable;
    boolean[][] actual;
    boolean[][] map;
    int px;
    int py;
    
    void run(String[] input){
        int direction = 0;
        if(read(input))
            direction = bestPath(findPaths(false), true);
        System.out.print(directions[direction]);
    }

    int bestPath(int[] paths, boolean first){
        if(!first)
            paths = findPaths(true);
        int bestDir = 0;
        int best = 0;
        for(int i=0;i<paths.length;i++)
            if(paths[i] > best){
                best = paths[i];
                bestDir = i;
            }
        if(best==0 && first)
            return bestPath(paths, false);
        return bestDir;
    }

    static int floodCount;
    void flood(boolean[][] visited, int x, int y){
        if(visited[x][y] || !map[x][y])
            return;
        floodCount++;
        visited[x][y] = true;
        for(int dir=0;dir<4;dir++){
            int nx = dir%2==1 ? wrap(x+dir-2) : x;
            int ny = dir%2==0 ? wrap(y+dir-1) : y;
            flood(visited, nx, ny);
        }       
    }
    
    int[] findPaths(boolean useActual){             
        int[] paths = new int[4];
        map = useActual ? actual : walkable;
        for(int i=0;i<4;i++){
            floodCount = 0;
            int nx = i%2==1 ? wrap(px+i-2) : px;
            int ny = i%2==0 ? wrap(py+i-1) : py;
            flood(new boolean[size][size], nx, ny);
            paths[i] = floodCount;
        }
        return paths;
    }
    
    boolean read(String[] input){
        if(input.length < 1 || input[0].length() < size*size)
            return false;
        String[] lines = input[0].split(";");
        if(lines.length < size)
            return false;
        walkable = new boolean[size][size];
        actual = new boolean[size][size];
        for(int x=0;x<size;x++)
            for(int y=0;y<size;y++){
                walkable[x][y] = true;
                actual[x][y] = true;
            }
        for(int y=0;y<size;y++)
            for(int x=0;x<size;x++){
                char pos = lines[y].charAt(x);
                switch(pos){
                case '.':
                    break;
                case '2':
                    actual[x][y] = false;
                    walkable[x][y] = false;
                    walkable[wrap(x+1)][y] = false;
                    walkable[wrap(x-1)][y] = false;
                    walkable[x][wrap(y+1)] = false;
                    walkable[x][wrap(y-1)] = false;
                    break;
                case '1':
                    px = x; py = y;
                case '#':
                default:
                    walkable[x][y] = false;
                    actual[x][y] = false;
                }
            }

        return true;
    }
    
    public static void main(String[] input){new Floodbot().run(input);}
    static int wrap(int c){return (size+c)%size;}   
    static final String[] directions = {"N","W","S","E"};
    static final int size = 25;
}
\$\endgroup\$
3
  • \$\begingroup\$ I think you've got this in the bag. \$\endgroup\$
    – cjfaure
    May 2, 2014 at 9:39
  • \$\begingroup\$ @Trimsty Oh? I haven't tested against all of the competition yet, so I wasn't sure how it fared against a couple of them. Good to know :) \$\endgroup\$
    – Geobits
    May 2, 2014 at 12:47
  • \$\begingroup\$ Congrats for winning! :) \$\endgroup\$
    – tomsmeding
    May 4, 2014 at 11:21
4
\$\begingroup\$

BlindSnake

Batch

This bot only watches its close surroundings. If there isn't a wall, it moves there.

@echo off
setlocal enableextensions enabledelayedexpansion
set map=%1

REM find position
set I=0
set L=-1
:l
if "!map:~%I%,1!"=="" goto ld
if "!map:~%I%,1!"=="1" set L=%I%
set /a I+=1
goto l
:ld
set /a pos = %L%
set /a row = %pos% / 26
set /a col = %pos% %% 26

REM find surroundings
If %row%==0 (
    set /a northPos = 24 * 26 + %col%
) else (
    set /a rowDown = %row% - 1
    set /a northPos=!rowDown! * 26 + !col!
)
If %row%==24 (
    set /a southPos = %col%
) else (
    set /a rowDown = %row%+1
    set /a southPos=!rowDown!*26+!col!
)
If %col%==0 (
    set /a westPos = %row% * 26 + 24
) else (
    set /a westPos = %pos% - 1
)
If %col%==24 (
    set /a eastPos = %row% * 26
) else (
    set /a eastPos = %pos% + 1
)

REM choose move
if "!map:~%northPos%,1!" neq "#" (
    echo N
    goto end
)
if "!map:~%eastPos%,1!" neq "#" (
    echo E
    goto end
)
if "!map:~%southPos%,1!" neq "#" (
    echo S
    goto end
)
if "!map:~%westPos%,1!" neq "#" (
    echo W
    goto end
)
echo N
:end

I just wanted to create a bot in batch... And will never do it again

\$\endgroup\$
4
\$\begingroup\$

FluidBot

Python 3

Takes path of least resistance and attempts to predict opponent

import sys, math

def mvs(j,x,y,d,*args):
    score = sum([
                    ((j[y-1][x]=='.') * ((j[rgpos[1][1]+1][rgpos[1][0]]=='#')/3+1)) /
                        ([j[y-1][x+1], j[y-1][x-1]].count('#')+1)
                        * (d != 'S'),
                    ((j[y+1][x]=='.')*((j[rgpos[1][1]-1][rgpos[1][0]]=='#')/3+1)) /
                        ([j[y+1][x+1], j[y+1][x-1]].count('#')+1)
                        *(d != 'N'),
                    ((j[y][x-1]=='.')*((j[rgpos[1][1]][rgpos[1][0]+1]=='#')/3+1)) /
                        ([j[y+1][x-1], j[y-1][x-1]].count('#')+1)
                        *(d != 'W'),
                    ((j[y][x+1]=='.')*((j[rgpos[1][1]][rgpos[1][0]-1]=='#')/3+1)) /
                        ([j[y-1][x+1], j[y+1][x+1]].count('#')+1)
                        *(d != 'E')
                ]) * (j[y][x]=='.')
    if len(args):
        if args[0] > 0:
            mvx = {'N': [x, y-1], 'S': [x, y+1], 'E': [x+1, y], 'W': [x-1, y]}
            nscr = score * (args[0] + mvs(j,mvx[d][0],mvx[d][1],d,args[0]-1))
            return(nscr)
        else:
            return(score)
    else:
        return(score*mvs(j,x,y,d,[len(g),len(g[0])][d in ['E','W']]-1))

g = sys.argv[1].split(';')[:-1]
fg = sys.argv[1].replace(';', '')

pos = [fg.index('1'), fg.index('2')]
pos = [
        [pos[0]%len(g[0]), math.floor(pos[0]/len(g[0]))],
        [pos[1]%len(g[0]), math.floor(pos[1]/len(g[0]))]
    ]
rg = ';'.join(g).replace('1', '#').replace('2', '#').split(';')
mg = [c+c+g[i]+c+c for i,c in enumerate(rg)]
rg = [i*5 for i in rg]

rg = rg + rg + mg + rg + rg
rgpos = [
        [pos[0][0]+len(g[0]), pos[0][1]+len(g)],
        [pos[1][0]+len(g[0]), pos[1][1]+len(g)]
    ]
relpos = [
            rgpos[1][0]-rgpos[0][0],
            rgpos[1][1]-rgpos[0][1]
        ]

moves = {
        'N': ((relpos[1]>0)/3+1)*mvs(rg, rgpos[0][0], rgpos[0][1]-1, 'N'),
        'S': ((relpos[1]<0)/3+1)*mvs(rg, rgpos[0][0], rgpos[0][1]+1, 'S'),
        'E': ((relpos[0]<0)/3+1)*mvs(rg, rgpos[0][0]+1, rgpos[0][1], 'E'),
        'W': ((relpos[0]>0)/3+1)*mvs(rg, rgpos[0][0]-1, rgpos[0][1], 'W')
        }

sys.stdout.write(sorted(moves, key=lambda x:-moves[x])[0])

Worked on this for about an hour. ._.

Tested against AwayBot:

Player 1: E
Player 2: W
#.....#####.......##.....
#.....###1.........##...#
....................#####
.........................
.........................
.........................
......######.............
......#....####..........
......#.......##.........
......#........###.......
.....##..........#.......
.....#...........#.......
.....#...........#.......
....##......##...#.......
....###.....##...#.......
......#...#####..#.......
....###...#...#..#.......
....#..####...##.##......
....#..#.......#..##.....
....##2#.......#...##....
.......#.......##...##...
.......#........#....##..
.......#........#.....##.
.......##.......##.....##
........###......##.....#

Player 1 wins!

FillUpBot:

Player 1: W
Player 2: E
#......................#2
#......................##
......................##.
......................#..
.....................##..
....................##...
....................#....
...................##....
..................##.....
..................#......
.......1###########......
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
#########################
.......................##

Player 1 wins!

EDIT 5: More future-conscious; tries to avoid closing off areas (unless, of course, the opponent is in it).

EDIT 4: Cleaned up code.

EDIT 3: Works better for rectangular playing areas.

EDIT 2: Cleaner code, algorithm is more logical and predicts some moves into the future

EDIT: More defensive algorithm, doesn't count ghost self as empty space.

\$\endgroup\$
3
\$\begingroup\$

AwayBot

written in Ruby (1.9)

Aptly named, AwayBot tries to go away from any obstacles. It searches a 15x15 square around itself, weights the directions accordingly, and chooses the direction with the least amount of obstacles. (This also means that it avoids the edges, which is good so it doesn't get trapped in them.)

It also considers walls closer by to be more of a danger. Walls right next to it are weighted much more than walls far away.

For your sample input, it outputs S. The weights for each direction of the sample input are [["N", 212], ["E", 140], ["S", 0], ["W", 84]].

Interjection: I just noticed that the arena wraps. Well then, my edge-avoiding technique is somewhat pointless now, but meh. Maybe I'll fix it later.

arena = ARGF.argv[0]

# we're considering the enemy a wall, for simplicity.
# no need to weight him any more than the other walls because he will
# always be surrounded by walls anyway.
arena = arena.sub(?2, ?#).split(?;)

# pad the arena with extra walls (edges of the arena)
searchRadius = 7
arenaSize = arena.first.size

verticalEdgeWalls = [?# * arenaSize] * searchRadius
arena = verticalEdgeWalls + arena + verticalEdgeWalls

horizontalEdgeWalls = ?# * searchRadius
arena.map! {|row| (horizontalEdgeWalls + row + horizontalEdgeWalls).split('') }

# now get the area around the bot
botRow = arena.index{|row| row.index ?1 }
botCol = arena[botRow].index ?1

searchZone = arena.slice(botRow-searchRadius..botRow+searchRadius)
searchZone.map! {|row| row.slice(botCol-searchRadius..botCol+searchRadius) }

# second to last step: assign values to each square depending on how far away they are
# from the player (Manhattan distance)
# this is so that the player avoids running directly into a wall; higher value means closer tile
# 0123210
# 1234321
# 2345432
# 1234321
# 0123210
centerSquare = searchRadius
searchZone = searchZone.each_with_index.map {|row, rowIndex| row.each_with_index.map{|tile, tileIndex|
    [tile, searchRadius*2 - ((rowIndex - centerSquare).abs + (tileIndex - centerSquare).abs)]
} }
puts searchZone.map{|x|x.map{|y|y[1].to_s.rjust(2, ?0)}.join ' '} * "\n"

# finally, assign weights to each direction
# first, create a map of directions. each direction has an array, the first element being
# what rows to slice and the second being what column.
sBeg = 0
sMdl = searchRadius
sEnd = searchRadius*2
directions = {
    ?N => [sBeg..sMdl-1, sBeg..sEnd],
    ?E => [sBeg..sEnd, sMdl+1..sEnd],
    ?S => [sMdl+1..sEnd, sBeg..sEnd],
    ?W => [sBeg..sEnd, sBeg..sMdl-1]
}
# then, create another hash of weights
weights = directions.map{|dir, arr|
    section = searchZone.slice(arr[0]).map{|x| x.slice(arr[1]) }.flatten(1)
    [dir, (section.select{|tile| tile[0] == ?# }.map{|tile| tile[1] }.reduce(:+) || 0)] # return the sum of the values of the walls in the area
}
# yay! we have our weights! now just find the smallest one...
dirToGo = weights.min_by{|_, walls| walls }
# and output!
print dirToGo[0]
\$\endgroup\$
6
  • \$\begingroup\$ "This also means that it avoids the edges, which is good so it doesn't get trapped in them." - Don't the edges wrap? \$\endgroup\$
    – Hovercouch
    Apr 26, 2014 at 7:14
  • 1
    \$\begingroup\$ @Hover Umm, yes, didn't you read the last paragraph? ;-) \$\endgroup\$
    – Doorknob
    Apr 26, 2014 at 10:19
  • \$\begingroup\$ @Doorknob Make sure you're getting your input via the command-line, thus ARGF.argv[0].chomp instead of gets.chomp in the first line! \$\endgroup\$
    – tomsmeding
    Apr 28, 2014 at 5:24
  • \$\begingroup\$ @Doorknob you should probably specify your Ruby version. I think this uses some features that are not universal \$\endgroup\$ Apr 28, 2014 at 18:35
  • \$\begingroup\$ @tomsmeding Ah, didn't realize that. Thanks, editing \$\endgroup\$
    – Doorknob
    Apr 28, 2014 at 20:57
3
\$\begingroup\$

FillUpBot

written in C++

Don't think I'm going to win, but here's my go at it anyway:

#include <iostream>
#include <cassert>
#include <cmath>
#include <cstdlib>

#define SIZE 25

using namespace std;

class Board{
public:
    unsigned long long walls[SIZE]; //each int is a bitmap with the LSbit being the left side
    int p1x,p1y,p2x,p2y;
    void read(const char *arg){
        int map,i,j;
        for(i=0;i<SIZE;i++){
            for(map=1,j=0;j<SIZE;map<<=1,j++){
                if(arg[(SIZE+1)*i+j]=='1'){
                    p1x=j;
                    p1y=i;
                } else if(arg[(SIZE+1)*i+j]=='2'){
                    p2x=j;
                    p2y=i;
                }
                walls[i]=(walls[i]&~map)|(map*(arg[(SIZE+1)*i+j]=='#'));
            }
        }
    }
    bool operator==(const Board &other){
        int i;
        for(i=0;i<SIZE;i++)if(walls[i]!=other.walls[i])return false;
        if(p1x!=other.p1x||p1y!=other.p1y||p2x!=other.p2x||p2y!=other.p2y)return false;
        return true;
    }
};

inline int mod(int a,int b){return (a+b)%b;}
inline int min(int a,int b){return a<b?a:b;}

int main(int argc,char **argv){
    assert(argc==2);
    Board B;
    B.read(argv[1]);
    //cerr<<"KOTW: read"<<endl;
    if(hypot(B.p2x-B.p1x,B.p2y-B.p1y)<=3||hypot(mod(B.p2x+SIZE/2,SIZE)-mod(B.p1x+SIZE/2,SIZE),mod(B.p2y+SIZE/2,SIZE)-mod(B.p1y+SIZE/2,SIZE))<=3){
        double maxdist=-1,d;
        int maxat=-1; //0=E, 1=N, 2=W, 3=S
        //cerr<<B.walls[B.p1y]<<endl;
        if(!(B.walls[B.p1y]&(1<<mod(B.p1x+1,SIZE)))){
            d=min(hypot(mod(B.p2x-(B.p1x+1),SIZE),mod(B.p2y-B.p1y,SIZE)),hypot(mod(B.p1x+1-B.p2x,SIZE),mod(B.p1y-B.p2y,SIZE)));
            //cerr<<"E: "<<d<<endl;
            if(d>maxdist){
                maxdist=d;
                maxat=0; //E
            }
        }
        //cerr<<B.walls[mod(B.p1y-1,SIZE)]<<endl;
        if(!(B.walls[mod(B.p1y-1,SIZE)]&(1<<B.p1x))){
            d=min(hypot(mod(B.p2x-B.p1x,SIZE),mod(B.p2y-(B.p1y-1),SIZE)),hypot(mod(B.p1x-B.p2x,SIZE),mod(B.p1y-1-B.p2y,SIZE)));
            //cerr<<"N: "<<d<<endl;
            if(d>maxdist){
                maxdist=d;
                maxat=1; //N
            }
        }
        //cerr<<B.walls[B.p1y]<<endl;
        if(!(B.walls[B.p1y]&(1<<mod(B.p1x-1,SIZE)))){
            d=min(hypot(mod(B.p2x-(B.p1x-1),SIZE),mod(B.p2y-B.p1y,SIZE)),hypot(mod(B.p1x-1-B.p2x,SIZE),mod(B.p1y-B.p2y,SIZE)));
            //cerr<<"W: "<<d<<endl;
            if(d>maxdist){
                maxdist=d;
                maxat=2; //W
            }
        }
        //cerr<<B.walls[mod(B.p1y+1,SIZE)]<<endl;
        if(!(B.walls[mod(B.p1y+1,SIZE)]&(1<<B.p1x))){
            d=min(hypot(mod(B.p2x-B.p1x,SIZE),mod(B.p2y-(B.p1y+1),SIZE)),hypot(mod(B.p1x-B.p2x,SIZE),mod(B.p1y+1-B.p2y,SIZE)));
            //cerr<<"S: "<<d<<endl;
            if(d>maxdist){
                maxdist=d;
                maxat=3; //S
            }
        }
        if(maxat==-1){ //help we're stuck!
            cout<<"ENWS"[(int)((double)rand()/RAND_MAX*4)]<<endl;
            return 0;
        }
        cout<<"ENWS"[maxat]<<endl;
        return 0;
    }
    //cerr<<"KOTW: <=3 checked"<<endl;
    //cerr<<B.p1x<<","<<B.p1y<<endl;
    if(!(B.walls[B.p1y]&(1<<mod(B.p1x+1,SIZE))))cout<<'E'<<endl;
    else if(!(B.walls[mod(B.p1y+1,SIZE)]&(1<<B.p1x)))cout<<'S'<<endl;
    else if(!(B.walls[mod(B.p1y-1,SIZE)]&(1<<B.p1x)))cout<<'N'<<endl;
    else if(!(B.walls[B.p1y]&(1<<mod(B.p1x-1,SIZE))))cout<<'W'<<endl;
    else cout<<"ENWS"[(int)((double)rand()/RAND_MAX*4)]<<endl; //help we're stuck!
    //cerr<<"KOTW: done"<<endl;
    return 0;
}

Your standard C++ compiler should be able to handle this.

\$\endgroup\$
7
  • \$\begingroup\$ Can't seem to compile. GCC 4.8.1, Windows 7. Throws errors about rand and RAND_MAX not being defined. \$\endgroup\$
    – cjfaure
    May 1, 2014 at 14:15
  • \$\begingroup\$ @Trimsty Does a #include <cstdlib> help? (Just insert it at the top as a new line) \$\endgroup\$
    – tomsmeding
    May 1, 2014 at 14:24
  • \$\begingroup\$ Indeed! It compiles now. Thanks. \$\endgroup\$
    – cjfaure
    May 1, 2014 at 14:26
  • \$\begingroup\$ Ran it against FluidBot, failed to produce output on this move: pastie.org/private/azmwkybqrxqlfvpwidlpw (FluidBot is player 1) \$\endgroup\$
    – cjfaure
    May 1, 2014 at 14:31
  • \$\begingroup\$ @Trimsty Um... gist.github.com/tomsmeding/96060c7db3f1c3483668 (1 and 2 swapped; if I don't swap them it gives the same output) \$\endgroup\$
    – tomsmeding
    May 1, 2014 at 17:19
3
\$\begingroup\$

Arcbot

Python 3

Plays with aggression-based algorithm as enemy and bruteforces answer with influence

This algorithm is kind of 'emotion-based', I guess. In developing this, I realized that FluidBot beat it nearly every time. Arcbot isn't the fastest algorithm nor the best, but it has it's strengths.

It does crash into walls. No idea why.

FLUIDBOT IS BETTER

#   Arcbot
#   
#   This is a more dynamic bot than the earlier Fluidbot.
#   I'm also commenting on the code to make my algorithm
#   more clear.

#** Some intial definitions **#

import math, sys # math for the 'arc' part

class edgeWrapList: # yay, such efficient
    def __init__(self, l):
        self.l = list(l)
    def __getitem__(self, i):
        it = i%len(self.l)
        if it == i: # no wrapping, include players
            return(self.l[i])
        else: # wrapping, replace players with walls
            if not isinstance(self.l[it], str):
                return(self.l[it])
            else:
                return(self.l[it].replace('1', '#').replace('2', '#'))
    def __len__(self):
        return(len(self.l))
    def __str__(self):
        return(''.join(str(i) for i in self.l))
    def __setitem__(self, i, v):
        self.l[i%len(self.l)] = v

grid = edgeWrapList([edgeWrapList([j for j in i]) for i in sys.argv[1].split(';')[:-1]]) # a 2D edgeWrapList. Access via grid[y][x]

attackStr = 1 # distance to attack from
attackEnd = 12 # distance to avoid again

predictTurns = 6 # how many turns to play as the opponent as well. Keep low for performance.

#** Arcbot's main class **#

class arcbot:
    def __init__(self, g, astr, aend):
        self.g = g # g is a 2D edgeWrapList
        self.p1p = str(g).index('1')
        self.p1p = [self.p1p%len(g[0]), math.floor(self.p1p/len(g[0]))] # x, y of player 1
        self.p2p = str(g).index('2')
        self.p2p = [self.p2p%len(g[0]), math.floor(self.p2p/len(g[0]))] # x, y of player 2
        self.astr = astr
        self.aend = aend
    def getAggr(self, d):
        if self.astr < d < self.aend:
            return(0)
        else:
            return(math.cos((d-self.astr)*(math.pi*2/self.aend))) # sort-of bell curve between -1 and 1
    def getMove(self, p): # p is either 1 or 2
        scrg = edgeWrapList(self.scoreGridGen(p)) # get dem position scores
        pos = self.p1p if p==1 else self.p2p
        dir = {
            'N': scrg[pos[1]-1][pos[0]], 
            'S': scrg[pos[1]+1][pos[0]],
            'E': scrg[pos[1]][pos[0]+1],
            'W': scrg[pos[1]][pos[0]-1]
            }
        o = sorted(dir, key=lambda x:-dir[x])[0]
        return([o, dir[o]]) # return direction with highest scoring position and it's score
    def getScore(self, x, y, p, d='*'):
        epos = self.p2p if p == 1 else self.p1p
        dist = math.sqrt((y - epos[1])**2 + (x - epos[0])**2)
        return((sum([
                (self.g[y][x-1] == '.') * (((self.g[y][x+1] == '.')+1) * ((self.g[y][x-2] == '.')*4+1)),
                (self.g[y][x+1] == '.') * (((self.g[y][x-1] == '.')+1) * ((self.g[y][x+2] == '.')*4+1)),
                (self.g[y-1][x] == '.') * (((self.g[y+1][x] == '.')+1) * ((self.g[y-2][x] == '.')*4+1)),
                (self.g[y+1][x] == '.') * (((self.g[y-1][x] == '.')+1) * ((self.g[y+2][x] == '.')*4+1))
            ]) * 2 + 1) * (self.getAggr(dist) / 10 + 1) * (self.g[y][x] == '.'))
    def scoreGridGen(self, p): # turn .s into numbers, higher numbers are better to move to
        o = []
        for y,r in enumerate(self.g.l): # y, row
            o.append(edgeWrapList(
                    self.getScore(x, y, p) for x,v in enumerate(r.l) # x, value
                )
            )
        return(o)
    def play(self, turns, movestr): # movestr is [p1moves, p2moves]
        p2move = self.getMove(2)
        movestr[1] += [p2move[0]]
        p1move = self.getMove(1)
        if len(movestr[0]) == turns:
            return([p1move[1], p1move[0]]) # Score for final block
        scores = {}
        for i in 'N S E W'.split():
            movestr[0] += [i]
            og = self.simMoves(movestr)
            if og == 'LOSE:2':
                scores[i] = 1000000 # we win!
            elif og == 'LOSE:1':
                scores[i] = -1000000 # we lose!
            else:
                scores[i] = og[1] * ((i == p1move[0]) / 1.2 + 1) * (turns-len(movestr[0])) * (self.play(turns, movestr)[0]+1)
            movestr[0] = movestr[0][:-1]
        hst = sorted(scores, key=lambda x:-scores[x])[0]
        return([scores[hst], hst]) # highest scoring turn in total and it's score
    def simMove(self, p, d): # move player p in direction d
        pos = self.p1p if p == 1 else self.p2p
        target = {
            'N': [pos[0], pos[1]-1],
            'S': [pos[0], pos[1]+1],
            'E': [pos[0]+1, pos[1]],
            'W': [pos[0]-1, pos[1]]
            }[d]
        v = self.g[target[1]][target[0]] # contents of target block
        if v == '.': # yay let's move here
            self.g[target[1]][target[0]] = str(p)
            self.g[pos[1]][pos[0]] = '#'
            if p == 1:
                self.p1p = [target[0], target[1]]
            else:
                self.p2p = [target[0], target[1]]
        else: # nuu crash
            raise(ValueError) # doesn't matter, caught later
    def simMoves(self, mvl): # return simmed copy
        op = [self.p1p, self.p2p]
        og = self.g
        finalScore = 0
        for i in range(len(mvl[0])):
            try:
                if i == len(mvl[0])-2:
                    finalScore = {
                        'N': self.getScore(self.p1p[0], self.p1p[1]-1, 'N'),
                        'S': self.getScore(self.p1p[0], self.p1p[1]+1, 'S'),
                        'E': self.getScore(self.p1p[0]+1, self.p1p[1], 'E'),
                        'W': self.getScore(self.p1p[0]-1, self.p1p[1], 'W')
                        }[mvl[0][i]]
                self.simMove(1, mvl[0][i])
            except:
                return('LOSE:1')
            try:
                self.simMove(2, mvl[1][i])
            except:
                return('LOSE:2')
        o = self.g
        self.g = og
        self.p1p, self.p2p = op
        return([o, finalScore])

arcbotMove = arcbot(grid, attackStr, attackEnd)
sys.stdout.write(arcbotMove.play(predictTurns, [[], []])[1])

EDIT: Adjusted the numbers and the formula, it plays better now but still loses to Fluidbot.

EDIT 2: Whoops, forgot to change some code.

\$\endgroup\$
1
\$\begingroup\$

RandomBot

C#

RandomBot randomly selects a direction until it's route is free. If there is no safe direction it simply types * and loses.

using System;

class AI
{
    static void Main(string[] args)
    {
        char[,] grid = new char[25, 25];
        char[] directions = { 'N', 'E', 'S', 'W' };
        string map = args[0];
        Random rand = new Random();
        int[] pos = new int[2];
        for (var x = 0; x < 25; x++)
        {
            for (var y = 0; y < 25; y++)
            {
                grid[x, y] = map.Split(';')[y][x];
                if (grid[x,y] == '1') {
                    pos[0] = x;
                    pos[1] = y;
                }
            }
        }
        if (grid[(pos[0] + 1) % 25, pos[1]] != '.' && grid[pos[0], (pos[1] + 1) % 25] != '.' && grid[(pos[0] + 24) % 25, pos[1]] != '.' && grid[pos[0], (pos[1] + 24) % 25] != '.')
        {
            if (grid[pos[0], (pos[1] + 24) % 25] == '2')
            {
                Console.Write("N");
            }
            else if (grid[(pos[0] + 1) % 25, pos[1]] == '2')
            {
                Console.Write("E");
            }
            else if (grid[pos[0], (pos[1] + 1) % 25] == '2')
            {
                Console.Write("S");
            }
            else if (grid[(pos[0] + 24) % 25, pos[1]] == '2')
            {
                Console.Write("W");
            }
            else
            {
                Console.Write("*");
            }
        }
        else
        {
            while (true)
            {
                char direction = directions[Convert.ToInt32(rand.Next(4))];
                if (direction == 'N' && grid[pos[0], (pos[1] + 24) % 25] == '.')
                {
                    Console.Write("N");
                    break;
                }
                else if (direction == 'E' && grid[(pos[0] + 1) % 25, pos[1]] == '.')
                {
                    Console.Write("E");
                    break;
                }
                else if (direction == 'S' && grid[pos[0], (pos[1] + 1) % 25] == '.')
                {
                    Console.Write("S");
                    break;
                }
                else if (direction == 'W' && grid[(pos[0] + 24) % 25, pos[1]] == '.')
                {
                    Console.Write("W");
                    break;
                }
            }
        }
    }
}

This is only an example AI - it is not designed to win!

\$\endgroup\$
-1
\$\begingroup\$

Fill Up Bot (turns 90 degrees anticlockwise, when faces an obstacle

C++

In my code, the two players (1 and 2) try to flood. Meaning whenever they face an obstacle, they turn anti-clockwise.
Remember, The lines in input are separated by a space or newline and not by ;

#include<iostream>
#include<conio.h>
#include<windows.h>
char draw(char plot[][25],char dir,char num)
{
    int a=1,i,j;
    for(i=0;i<25;i++)
    {
        for(j=0;j<25;j++)
        {
            if(plot[i][j]==num&&a)
            {
                a--;
                switch(dir)
                {
                    case 'S':{
                        if(i==24||plot[i+1][j]=='#')
                        {
                            dir='E';
                            plot[i][j]='#';
                            plot[i][j+1]=num;
                        }
                        else if(i<24||plot[i+1][j]=='.')
                        {
                            plot[i][j]='#';
                            plot[i+1][j]=num;
                        }
                        break;
                    }
                    case 'E':{
                        if(j==24||plot[i][j+1]=='#')
                        {
                            dir='N';
                            plot[i][j]='#';
                            plot[i-1][j]=num;
                        }
                        else if(j<24||plot[i][j+1]=='.')
                        {
                            plot[i][j]='#';
                            plot[i][j+1]=num;
                        }
                        break;
                    }
                    case 'N':{
                        if(i==0||plot[i-1][j]=='#')
                        {
                            dir='W';
                            plot[i][j]='#';
                            plot[i][j-1]=num;
                        }
                        else if(i>0||plot[i-1][j]=='.')
                        {
                            plot[i][j]='#';
                            plot[i-1][j]=num;
                        }
                        break;
                    }
                    case 'W':{
                        if(j==0||plot[i][j-1]=='#')
                        {
                            dir='S';
                            plot[i][j]='#';
                            plot[i+1][j]=num;
                        }
                        else if(j>0||plot[i][j-1]=='.')
                        {
                            plot[i][j]='#';
                            plot[i][j-1]=num;
                        } 
                        break;
                    }
                }
            }
        }
    }
    return dir;
}
void run()
{
    int i,j,crash=1,count,k,a;
    char plot[25][25],dir1='S',dir2='N';
    for(i=0;i<25;i++)
        std::cin>>plot[i];
    plot[0][0]='1';
    plot[24][24]='2';
    while(crash)
    {
        system("cls");
        dir1=draw(plot,dir1,'1');
        dir2=draw(plot,dir2,'2');
        count=0;
        for(i=0;i<25;i++)
            for(j=0;j<25;j++)
                if(plot[i][j]=='.')count++;
        if(count==1)
        {
            crash--;
            plot[12][12]='*';
            plot[11][12]='#';
            plot[13][12]='#';
        }
        for(i=0;i<25;i++)
        {
            for(j=0;j<25;j++)
                std::cout<<plot[i][j];
            std::cout<<'\n';
        }
        Sleep(25);
    }
}
int main()
{
    run();
    getch();
    return 0;
}
\$\endgroup\$
1
  • 2
    \$\begingroup\$ I will not be able to test this program as it is because it does not comply with some essential specifications and cannot be used by the control program. \$\endgroup\$
    – kitcar2000
    May 1, 2014 at 14:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.