Entelect AI Challenge ( R100K grand prize)

TheFuntastic

I have no idea how legit this is, but passing it on anyway. Challenge seems to be to build a tron light cycle AI bot. Finale at Rage expo, in association with NAG. Probably worth considering. Sadly teams aren't allowed:

http://challenge.entelect.co.za/

(Still can't figure out why a JAVA enterprise shop wants to drop so much money on something like this, unless they're hoping to turn it into a recruitment drive)

helloserve

.NET is also permitted actually. And it's command line driven, so no excuses of the "I can't make art" type :) I'm definitely going to give it a bash.

edg3

It is probably a recruitment drive, I will be taking part (it is similar to my COMS 2 assignment for this semester, so will be interesting).

Elyaradine

Entrants will be paired off against each other under the supervision of an automated mediator program which will rank the entrants in a tournament style. Each player will play each other player and the winner of the heat will be determined as per the ‘best of 3’ match rules.

Ha, this could be fun to watch! :D

raithza

This seems a bit dumb... isn't Tron AI very much a solved problem? Google had a competition in 2010 with many entrants' source code and thought processes readily available now.... Still, it might be fun to participate..

dislekcia

Yeah, I was thinking pretty much the same thing: This seems like a solved area. Didn't realise there was all that source code available out there though.

Tuism

What, does that mean a bunch of people will be pitting very similar algorithms against each other, with some people trying to be clever about it cos they "know" what other people will be using?

THAT could be interesting :)

dislekcia

@Tuism: Unfortunately not. A solved space means that optimal moves are known, so there's very little room for variation or new strategies, like the ones you're talking about that focus on opponent prediction. Once something is solved, strategy becomes mostly meaningless because not taking the optimal move every turn just means you lose faster.

I'm wondering how Entelect is going to prevent people using the google challenge code? I mean, I'm not seeing many differences in these examples to what I was thinking would be a solid heuristic, but there are bunches of optimisations and stuff that would be really helpful.

Hang on, what the hell does "The game is played on a 30 x 30 board mapped onto the surface of a sphere. This means that the board wraps around on its horizontal ends and meets on its vertical ends." mean? The image they show doesn't help at all... What the crap happens if a player tries to move out the top or bottom of the grid?

TheFuntastic

Don't know if the Google challenge used a spherical map? (too busy at work now to check) That could add a little variance. Otherwise it's a simple game, once you reach the optimum I imagine there aren't a lot of ways to go.

Would be really annoying to see someone walk away with 100k who just ripped the google entries.

TheFuntastic

Snap, dislekcia beat me to my point...

helloserve

I read the sphere mapping as the world wraps, so there's no edges. If you go from (10, 0) to (10, -1) you're actually landing on (10, 29), if that makes sense.

TheFuntastic

Not quite, if you move across the poles it would be a little different, (5, 0) would traverse to (20, 0), i think?

Not really sure how much of a difference this would make to an algorithm. Imagine it would be like world wraps, but with tweaked logic for dealing with top and bottom edges.

helloserve

@TheFuntastic Yeah that's more correct. I wasn't thinking about this clearly.

Jdog

No, I don't think so... I'm assuming they only phrased this badly (and they did... games take a maximum of 5 seconds but moves take a maximum of 10 seconds? whut?), the map just wraps around like in snake, and there are no initial walls.

That changes the problem space somewhat, though I think a lot of the ideas and algorithms used in the prior google challenge (minimax, Voronoi diagrams) will apply here too.

Worth a shot, just for fun ^_^

edg3

It isnt a thing about whether the problem is already solved or not, it is to challenge people to write the AI, the same way that in a competition to make an RPG you are challenged to make an RPG. The analogy isnt perfect, but it is a good way to get people writing AI rather than just talking about it (and there are many ways that the participants could approach the problem from a "solving" perspective)

someone_else

The problem is not "solved". When a game is regarded as solved, it means all possible game states are known a path to a wining end state can be determined at every iteration/depth.

For a 30x30 grid game with two pieces, that's 30^30 game states. But light cycle adds a history mechanic WRT the trailing walls of each player so the possible game states actually increase exponentially in addition to the 30^30 at every iteration.

In any case if the the grid is in fact a sphere with two poles instead of a torus-like structure, it makes it very interesting because the poles would become significant points of control. In what way though, you'd have to decide for yourself.

dislekcia

Ok, I have a couple of problems with this since thinking about it in the car:

1. The whole "sphere" thing is not properly explained. The behavior for what happens when a player attempts to move out of the top or bottom of the grid is undefined. Either the sphere thing is wrong and they meant that it wraps vertically too, or there's some sort of custom ruleset for vertical grid re-entry: Teleporting to any desired top space if exiting from the top, moving to a mirrored point some fixed offset away along the edge, etc. This shit is not trivial, if you get the ruleset wrong your AI will be disqualified when it does something it thinks is totally legit but the auditing software cries foul at. Nor is the correct interpretation obvious, as it is with horizontal wrapping.

2. @Aequitas pointed out that no testing environment is provided. So people have to build their own take on the contest rules (including the sphere verticality ambiguity) and test that way. That's pretty weird... Presumably they have this legality testing tool already, why not give it to entrants so that they can, y'know, do what you want them to do?

@someone_else: Don't make the mistake of simply counting game states and assuming that means complexity. That's what heuristics are for: Reducing simple state enumeration into related groupings so that searching becomes easier. Remember that your transition space is limited by previous moves, so there are only three possible reachable states from any given state (the three new cells that the current player can move into) so your state space is much more controllable than something like, say, Go - where any particular state has far more transition options.

I'm pretty sure that for a specific board layout like the one specified, the game is indeed solved, the Google AI challenge seems to have relied on random board generation in order to force coders to come up with generalist AIs. Even if the given board has random starting locations, which I don't believe it will (more state space reduction), that's still totally within the bounds of solveability. Here's why: This type of Lightcycles game has 3 distinct phases, the opening phase where players are trying to establish areas that the other player can be locked out of, the maximisation phase where players attempt to increase the amount of space available to them and decrease the space available to enemies before locking them in to whichever spaces have been created, and finally the end-game of using up that space as efficiently as possible so that the other player runs out of space first.

This means that, given a fully wrapping board with no "hard" boundaries, the best thing to do is try to cut the play-space in half and claim the larger half. If you're the first player to move, the best location to do that is to move towards the closest space on the board that you can reach before they do, seeing as you'll always have the move advantage and then keep moving towards the point 1 space away from your starting position, exactly one board-space removed in your current direction of travel. Your opponent will be trying to maximise their space and will have to keep level with you, for every move that they don't, all you need to do is keep moving towards them so that you'll still reach your cutoff point first, but now you've taken a bite out of the space they have available. Then, once you're close to your cutoff point to create the two territories, use up all available move advantages you have over your opponent "on their side" of the cutoff, thus wasting their open space. After you finally close off the territory, you'll simply have to min-max your way to using space efficiently and you'll win.

Of course, I could easily be wrong, having not written an AI to do this (the first game I ever completed was Lightcycles, it sucked turn-based because of the domninance of exactly this type of strategy and only became a game when I figured out how to do the real-time controls) but I suspect that you'll see the winning AI displaying exactly this strategy in a completely mathematically proveable sense... You'll probably also see factors of the board coming into play, emphasising straight territory border lines due to the wrapping :)

TheFuntastic

My first thought was also "halving the board" and then just using remaining space efficiently. Together with the fact they didn't explain edges well enough, there was no mention of starting positions that I could see. That's also a crucial piece of info. Not to mention first mover advantage becomes fairly massive if in fact this is the optimal strategy.

Without a working demo of a valid entry or starter pack (much like other AI challenges), or a forum to raise questions and concerns, I find myself a bit hesitant about diving into this.

Hopefully time will reveal such things.

Jdog

Alright, so it seems like it really is a sphere.... check the FAQ. Why they did it like this, I do not know. "At that point the x dimension ceases to have any meaning, similar to how at the North pole the only direction you can travel is south. Because of that, once you’ve moved onto that extreme point you can move off it again to any point on the x axis." is pretty weird.

The writing to console thing also seems a bit silly, and yes... without a starter kit or test harness, this seems like a waste of effort. So until they release one, I'm on the bench too.

Tuism

Well they say sphere and then they say the edges wrap. Those things are mutually exclusive... Cos you can't have a sphere AND wrapping edges. But hey I guess someone will have to call them and ask.

dislekcia

Ok, I emailed them with the following:

@dislekcia said:

Hi

Cool idea and I love these sorts of competitions, but I have a couple of questions for you, some specific to your ruleset and some general:

1. Can you please provide defined behavior for what happens when a player attempts to move out of the grid vertically? Horizonally is obvious from your example, it wraps to the other side of the board (so x = x mod width), but the y direction is confusing: Mapping to a sphere doesn't make sense: Is the top of the board a hard boundary? Can a move exiting the top move to any other cell on the same row (singularity movement)? Is there an offset to where the move ends up (y = y + 1, x = x + width / 2) for instance? Is it just supposed to wrap the same as horizontally?

2. Can you provide a testing environment for people that want to work on this? Obviously this would automatically answer the point above, as entrants wouldn't have to whip up their own legal/illegal and end state evaluations anymore. It would also remove one more barrier to entry, so you'll get more entries :)

3. Are you aware that Google did a very similar AI Challenge in 2010? http://forums.aichallenge.org/viewforum.php?f=7
How do you plan to prevent the winning implementations (whose source is available) from that challenge from dominating this competition?

And got back this reply:

Hey Danny,

Thanks for your interest and questions :) we've recently update the site to answer a lot of these questions. There's a new FAQ section. Will pass on your question to our tech people though.

In terms of the google ai challenge - yeah we are aware of this. Most of the winning strategies from that competition are based on who gets to the centre first. We changed our approach to play the game on a sphere, which because it has no centre renders a lot of those strategies inappropriate.

We're hoping this will generate some exciting new approaches!

Good luck and looking forward to your entry!
Tim

So I went and read the FAQ which, of course, raised another question about the sphere thing... The whole sphere thing appears to be a reaction to the Google challenge, but I'm pretty sure that we're simply looking at a degenerate case where the players will have to define boundaries and thus center points to fight over first.

@dislekcia said:

Hi Tim

Just read your FAQ. One more question on the sphere thing:

Is the entire top and bottom row 1 single cell or a complete row of cells? Would it be legal to move from (5; 1) to (5; 0) and then (7; 1) or is (0; 0) the only cell in that entire row? Could moves like (6; 0) -> (4; 1) -> (4; 0) -> (15; 1) be legal?

If it's a special single-cell row, can it be a wall? Meaning you wouldn't be able to travel through it a second time?

Looks like the test environment will appear in September. Also wondering about the map specification and file format thing. Why don't they just have a sequential move thing where you'd write the grid co-ordinates of your next move to, like chess? ... Unless they want to define random changes to the board, but there's no real scope for non-player walls in their definition anyway.

someone_else

@dislekcia I'd rather not have a sequential move thing, because it would require me to keep my own history whereas with having the entire game state written out the players' "walls" intrinsically keep move history.

A more concise way to ask the question would be, are we dealing with a Torus or a Sphere? See pics attached.

Torus: all the lines of an axis will always remain parallel
Sphere: there will always be two poles where seemingly parallel lines converge.

[Edit: Never mind, read the FAQ and it's quite clear now that it's a sphere.]

dislekcia

@someone_else: The data file would have all moves, sequentially. So reading it in would tell you the game state AND give you a valid move history at the same time, instead of forcing you to keep a history in another file, like they said you should on the rules page. Exactly how a move sequence can tell you the current (and all previous) game states in Chess... I'm a stickler for determinism.

Even if they've explained the sphere, they've left ambiguities in the state of the (x, 0) row: Is it essentially the same cell, so that you can move in there and then you have to move out of that row next move, or is a whole row that you can simply EXIT to any cell in the adjacent row from. What happens when there are walls there? Why did they use (1, 0) and then move to (x, 1), instead of somewhere ELSE on row 0? That isn't a spec I can code to ;)

dislekcia

Just got a response to my email from earlier, here's what I sent:

@dislekcia said:

Hi Tim

Just read your FAQ. One more question on the sphere thing:

Is the entire top and bottom row 1 single cell or a complete row of cells? Would it be legal to move from (5; 1) to (5; 0) and then (7; 1) or is (0; 0) the only cell in that entire row? Could moves like (6; 0) -> (4; 1) -> (4; 0) -> (15; 1) be legal?

If it's a special single-cell row, can it be a wall? Meaning you wouldn't be able to travel through it a second time?

And here are the two responses I got back:

No problem – thank you for your interest in the challenge.

To answer your question: It would be legal – all cells exist on that row, but they have the same position as one another. A wall on any of those cells also blocks all of them – something to keep in mind is that we’re moving on the lines, not the blocks themselves.

Your singularity movement idea is correct – on the top of the sphere for y=0 the x-position ceases to have meaning so all x positions share the one position. From this single point you can move to any non-walled point as usual, which would be any point on the y=1 line, similar to moving to the top of a sphere and then moving down again in any direction.

So that explains that then... I'm now wondering what "moving along the lines" means. Is it essentially a 31x31 grid instead?

D3zmodos

I went to the FAQ page and counted the lines on their diagram. There were 30 horizontal ones so as a flat plane it's still a 30x30 grid, you're just moving along the lines, stead of the blocks in between. However surely the line on the sides are the same line when on a sphere so that would make it a 30x29 grid wouldn't it?

TheFuntastic

From the faq: (0, x) and (29, x) are next to one another, so you can travel between the two in one move.

I take that as being 30 total

edg3

Technically it is a 30x28 grid with 2 points attached to the row 0 and row 27 of that grid's points respectively.

EtienneK

They should really provide us with a test project. There is too much confusion.

EtienneK

Ok, so tell me if I'm wrong:

This is not actually a sphere, it's an ellipsoid.

Doing a full rotation over the poles will take 30 + 28 = 58 moves.
But doing a full rotation over the horizontal will only take 30 moves.

Thus this "sphere" is twice as long as it is wide.

Am I correct in thinking this?

edg3

No... Don't know where you are getting that math from.

The image @someone_else posted with the sphere with longitude and latitude lines is correct. It is a sphere.

EtienneK

No, I don't think I am wrong.

Let's say you want to make a full vertical (over the poles) rotation. You start at (0; 1) moving in a straight line upwards. Thus your next moves will be (0; 0), then (15; 1), (15; 2) ... (15; 28), (15; 29), (0; 28), (0; 27) ... (0; 3), (0; 2) and finally you are back at (0; 1) where you started.

Count all those moves, it's 58. Contrast that with moving horizontally which is only 30 moves.

Legion

This whole idea reminds me of AT robots.
http://necrobones.com/atrobots/
https://sites.google.com/site/atr3portal/info

dislekcia

@EtienneK is right, it's not a sphere. The horizontal distance needs to be twice the height if you have wrapping at the horizontal edge but not the vertical one. Just look at the Mercator projection of the Earth: We don't think it's strange that the map isn't square...

It's more like a cylinder though, the whole top and bottom rows being the same cell and all that feels hacky and horrible... Still, it does point towards establishing a horizontal line in order to dictate space separation as a successful strategy: It's the shortest distance before you can start controlling space without your opponent being directly involved.

edg3

@dislekcia yeah when I read the math I realised what he meant (I misunderstood originally), but Im halfway though making a runner to use for testing.

Currently I have the "Board" drawing, with a free camera to move around (horizontal, vertical, zoom in or out) and my storage structure in place, the next step is to validate moves as well as run an "agent" via bat files to play (with their specified time restrictions).

Im still reading up on the methods I want to use for my AI, so nothing there. I wonder if I am allowed to share the runner under their rules?

EtienneK

@edg3 Looking good.

I just have a flat 2D grid representation, though. Makes it a bit easier to see what's going on in my opinion.

dislekcia

I've been toying with setting up a genetic-alg-style neural net pruning mechanism and letting it run wild for a few days. Goal would be to see if it could fit the entire gamespace and never make a poor move ;)

edg3

I like seeing the proper spatial representation (it is just my person preferance) which is why I built the runner using a 3D view.

@dislekcia Im looking at a more deterministic machine learning approach, Im specifically looking at a modified Markov chain for my AI.

raxter

For CPT ppl (or really adventurous non-CPT ppl :p), a mate of mine has an awesome hacker/dev/startup space called codebridge (for it is situated underneath Claremont bridge - really cool location!) and he's hosting a big collaborative hacker day with an Entelect competition flavour. Ought to be a party ^_^

facebook page: SuperHappyDevHouse Cape Town - Entellect R100K Challenge / Arduino / ...

In case you don't have facebook, here is the description:

We're finally hosting the first SuperHappyDevHouse at codebridge on Saturday, August 11th.

It is a non-exclusive event intended for creative and curious people interested in technology. We're about knowledge sharing, technology exploration, and ad-hoc collaboration. Come to have fun, build things, learn things, and meet new people. It's called hacker culture, and we're here to encourage it. (borrowed from superhappydevhouse.org).

You're free to come past and hack away on whatever you want. We'll have a whole lot of people working on entries to the Entelect Challenge[1] (hopefully with a visual interface to challenge each other), likely some people working on hardware/arduino tools, and whatever you plan on working on.

It will be hosted at codebridge in Claremont (directions at [2]). We'll have the doors open by 8:30am, hopefully we'll find a sponsor for some lunch/snacks/beers. We're also in dire need of additional tables/chairs so if anyone knows a cheap source *please* let us know. If you can bring along some networking equipment that would help too.

We'll get a wiki set up in the next couple days with more detail.

[1] http://challenge.entelect.co.za/Home/Rules
[2] http://www.codebridge.co.za/directions.htm

edg3

I would like to take part (could have brought a raspberry pi), but its so far :( You guys have fun though! :D

timkroon

HI Guys,

A large majority of the questions that we have received have been around behaviour at the poles. It looks like we've got to the bottom of this question here already though (polar row collapsing to a single 'logical' point). Your bots are responsible for marking the entire polar row (X, 0) (in the case of the north pole) with your wall or player, depending on whether you're moving to or from a polar row point.

In terms of the test-harness, we're putting up a cool visualisation on the website in the next 2 weeks (holding thumbs!) Although we've formally said this will be available by 1st September. You will be able to upload your .zip solution and watch your bot play-off in real time against a reference player. If there are any problems with your solution, it will let you know. It will also inform you of any invalid move attempts etc.

In terms of the clarity of the rules and details regarding the competition - the rules & FAQ on the website is growing on a daily basis. We're updating it as the questions come through, as we realize where the gaps are and where descriptions can be improved.

Please feel free to drop us an email on challenge@entelect.co.za. I'll ensure that we respond within 24 hours.

Good luck!
Tim

[Deleted User]

House4Hack (a hackerspace) in Randburg (http://www.house4hack.co.za/about for directions) is having regular meetups on Wednesday and currently lot of discussion and interest in this challenge. We have a playoff server up in dev and hopefully soon live so you can watch online and pitch your bot against others.

We have had playoffs (http://www.house4hack.co.za/first-tron-bot-play-off) the previous two weeks and the next one is scheduled for coming Wednesday the 8th.

Everyone is welcome to stop by from 18:00 onwards.

In case there is some confusion, we have Randburg and Centurion chapters, but most of the action on the bots currently at H4H Randburg :)

[Deleted User]

Hi everyone,

It is now a couple of hours before the deadline. Have anyone else experienced problems with the test harness?

I want to test my bot one final time before I'm 100% confident in my submission, but at the moment I'm unable to do so. Considering the amount of effort I put into it it would be a pity if there's some problem in my submission that I didn't pick up because I couldn't test that causes it to fail during the competition.

I'm pretty confident my Bot plays by the rules, but I've seen some strange behaviour, such as:
* Thelma being declared the winner as soon as she reaches the pole, despite my bot still having plenty of room to maneuver.
* Thelma bot losing at arbitrary points in time by not moving.
* My own bot running out of time within the first couple of seconds of the game or being declared the loser because it didn't move. I've been very careful to make sure that it makes a decision within 4.5 seconds and if can't that it returns the best move it has. If it's a problem on my side it is difficult to troubleshoot anyway because there's no feedback other than what you see in the visualisation.
* The test harness failing to display anything at all. Firefox seems to be the best browser to use. It sometimes works on Chrome. I've never seen it working on Internet Explorer 9.

I've sent several emails to challenge@entelect.co.za, but there's no indication anywhere of whether or not they've actually been received.

In the meantime I'll submit what I believe to be a working version, but as it stands I'm really nervous about it.

[Deleted User]

It seems my panicking was premature. Tim sent an email explaining that their servers have been experiencing high loads, which is understandable.

I still feel uncomfortable about submitting an entry which haven't been tested on their servers, since I've been tuning it a lot over the weekend.