7 ms·

Vindinium: An artificial intelligence programming challenge

158 points by gren 12y ago

kornork 12y ago
This looks promising. Will this fill the hole in my soul that Google Ants left behind?
- phillc 12y ago
  I share your pain.
  - le_meta 12y ago
    Only if there were some other way to donate our time to big corporations.
- Scaevolus 12y ago
  This doesn't have that magical "coordinate an army" feeling that the Ants contest had. :( The rules are very simple -- you control a hero, and you fight other heros to capture mines which give you gold. You can trade gold for health in taverns. Not too much strategic depth.
  - gren 12y ago
    I was also perplex the first time I entered this project. You would be surprise how this simple rules is already quite challenging. This game is fully observable and also determinist, which give way to make much more complex AI I think. I see it a bit like Chess: Pretty simple rules but there is still a fight to have the best AI in chess.
jbarrow 12y ago
If you're interested in this kind of thing and want a gentle introduction, I highly recommend CodeCombat [1], which offers both a single player version for learning the system and a multiplayer version for writing AI code. [1] http://codecombat.com http://codecombat.com
- codezero 12y ago
  I might have accidentally downvoted your comment, sorry about that :(
- digitalzombie 12y ago
  Can you recommend other resources and reading materials other than this? I would like more on top of the provided links thank you. OP's url have got me interested in AI now, but mainly for solving puzzles like this.
  - jbarrow 12y ago
    What you're asking for is actually pretty broad. A lot of CodeCombat can be played with traditional Game AI strategies to try and defeat the opponent. It's one subfields of AI I've done very little research in, so take what I say with a grain of salt, but it's my understanding that the best resources for learning Game AI are actual books on the subject. I would love for someone to prove me wrong, but I don't remember too many great online sources when I was trying to learn the it. Before you start reading about different AI tactics, I would recommend just going through CodeCombat and trying out some of your own strategies. You'll get a much more intuitive sense for why things work, as well as how you would apply different strategies to your particular game.
  - Houshalter 12y ago
    http://www.reddit.com/r/programminggames/ http://www.reddit.com/r/programminggames/ http://www.reddit.com/r/gameai/comments/v86kk/list_of_games_suitable_for_msc_ai_project_ai/ http://www.reddit.com/r/gameai/comments/v86kk/list_of_games_...
  - lobo_tuerto 12y ago
    Some years ago I really enjoyed this book: Programming Game AI by Example http://www.ai-junkie.com/books/toc_pgaibe.html http://www.ai-junkie.com/books/toc_pgaibe.html
- nnoitra 12y ago
  codecombat is awful. Lags a lot, has a bad UI and a lot of bugs.
jxm262 12y ago
Dude, this is awesome! I like it
vutekst 12y ago
Can anyone comment on general strategies that would be applicable to this game? Has anyone tried some kind of crazy machine learning stuff, or is it dominated by relatively simple algorithms?
- gren 12y ago
  This game is fully observable and determinist so that is not the hardest situation. However there is still a lot of possible game states. I've started an attempt to have a tree of all possible actions and using a minimax algorithm (with a score function + alpha-beta pruning) but this is not yet conclusive because I can't explore so much deep (was able to explore up to 20 next player decisions but that is just 5 moves of your hero). I think this game is enough simple to try to have this approach but also challenging because there is still up to 5 possible actions per turn so it is a max of 5^1200 total of possible state for a game – a lot. My current approach is now to try to have a minimax with pre-explored interesting path in the tree (e.g. all path which leads to tavern and mines), that is still a lot of computations.
  - hrjet 12y ago
    > This game is fully observable and determinist Off-topic, but are there any AI games which are not-observable and / or non-deterministic? That would be also a lot of fun!
    - sabirc 12y ago
      theaigames.com has a risk-like game (with fog of war) and a poker competiton.
  - baddox 12y ago
    When I saw the premise, I was expecting that the server would provide a line of sight for your hero each turn. You could even make the map initially undiscovered, and leave it up to the bot to "remember" what it discovers. I think that would make the game a lot more interesting, although also probably much more difficult to program bots for with standard techniques.
Rexxar 12y ago
Does someone here has already created a bot for the game ?
- serf 12y ago
  there are starter kits available on the site.
  - Rexxar 12y ago
    I don't ask for help, I just want to know if people are really trying to create a bot. Currently 90% of games are between only two AI. ("wolfie vs wolfie vs arthropod vs arthropod"). A competition like this one is much more interesting if there is a lot of players.
roryokane 12y ago
I saw this a while ago and thought that I would love to try playing this game as a human, so I could explore different strategies, or just have fun. Well, that is finally possible. I just created LiveHumanBot – a “bot” that really just lets you, a human, type in directions to control your character. Here is its code, with instructions: https://github.com/roryokane/vindinium-live-human-bot https://github.com/roryokane/vindinium-live-human-bot. I fare pretty well against other bots: http://vindinium.org/ai/p20qptiv http://vindinium.org/ai/p20qptiv.
- Revex 12y ago
  Now this is brilliant. I was thinking the same thing, "Man I'd like to play as a real person, before I build a bot." I feel silly now that I didn't think of building a software controller like you did. Also thanks for sharing the code. I'm gonna have to try it out.
kosinus 12y ago
Oh, neat to see this here! This was part of a local competition I participated in several months ago. Nice to see it has improved quite a bit since. I'm far from knowledgable on AI stuff, but I found this a great way to learn about some very basics, like pathfinding.
cheepin 12y ago
I would recommend having bot names be case sensitive, as well as a limit on how many a user can register. I really like the first use UX, and how easy it is to get started, but you can register as many names as you want.
ClayFerguson 12y ago
Seems like something that Google or Microsoft would ask as an interview question. You have all day to complete it, on your laptop, but once done, no matter how much code it is, they want it transcribed from your computer onto a physical white-board, because the only thing they know how to read is white-boards. If you tell them they are crazy and try to end the interview right then and there, you are hired, because you have guts, and you know what can and cannot be done, and will not waste your time with jerks.
- mrqwerty 12y ago
  I don't get this. I could easily transcribe anything I could write in a day into a diagrammatic representation. Hell, I could do it for anything I could write given a large enough whiteboard. It might consist of complicated flow diagrams or fragments of mathematics, but it would convey the salient points. This seems like fanatical code worship, "code is the only appropriate representation for all analytic thought". Nonsense. Maths, state diagrams, uml, even prose are useful and in combination adequate languages.
  - jebediah 12y ago
    He said transcribed, I guess he meant letter by letter
  - ClayFerguson 12y ago
    I was making fun of how in love some interviewers are with the whiteboard. I can write great code, but not up on a damn whiteboard -- kina because I do this thing called "typing". Also I'm making fun of the absolutely ridiculous complexity of many of the 'brain teaser' type interview questions. IMO the correct response to a brain-teaser interview question is to talk out. Better yet, tell them BEFORE the interview you WILL walk out IF the try that route.
    - ClayFerguson 12y ago
      Typo: "Talk out" was supposed to be "Walk out". Looks like you only have limited time to edit or something, because it won't let me fix that. Somebody please ding my karma again, I'm trying to see if I can make it go negative.
tylerpachal 12y ago
This reminds me of a the Student Starcraft AI Tournament: http://www.sscaitournament.com http://www.sscaitournament.com
dom96 12y ago
This looks really fun. Always wanted to participate in one of these. Good job on making it programming language agnostic :)
sytelus 12y ago
Over use of term "AI" is back. It's 80s all over again :). These kind of "challenges" are no where close to AI. They are just bit complex program whoes behavior is fully programmed by humans and they are only good at for very very specific "challange". These programs would be unable to hold a conversation with humans or read a newspaper and create their internal belief system. Stop calling these things "AI".
- witty_username 12y ago
  AI encompasses various things—simple AIs playing games, more complicated ones acting like humans.
- Houshalter 12y ago
  Video game bots have been called "AI" for decades now, it's a little late to dispute the term. The word "AI" doesn't imply "strong AI", there is "weak AI" as well: https://en.wikipedia.org/wiki/Weak_AI https://en.wikipedia.org/wiki/Weak_AI Also see the AI effect, where something is called "AI" until we actually solve it or understand it, then it is no longer called AI. "AI is whatever hasn't been done yet." https://en.wikipedia.org/wiki/AI_effect https://en.wikipedia.org/wiki/AI_effect
Tjgjfhguej 12y ago
It would be nice if the Java library allowed you to simply download the .jar instead of forcing you to use maven. This is supposed to be a game, not some massive web-scale project.
Twirrim 12y ago
Is it normal for x to reference the vertical, and y the horizontal in such games? Maybe I don't understand how they're normally represented. take this map: http://vindinium.org/4mx1xu9j http://vindinium.org/4mx1xu9j it returns the locations of the mines as: {(5, 9): u'-', (4, 9): u'-', (5, 0): u'-', (4, 0): u'-'} So that top left most mine is 4,0 instead of 0,4 that I'd would expect. It also has the location of my hero (althalus, right at the top left) as (0,1) vs my expected (1,0)
- lobo_tuerto 12y ago
  Maybe it's a (row,column) metaphor.
_lce0 12y ago
I've found this great project some months ago. I written a couple of robots which end up on this robot runner[1] mainly as a toy project for trying the game with some friends. [1] https://github.com/eridal/Vindinium https://github.com/eridal/Vindinium

158 points by gren 12y ago

kornork 12y ago

This looks promising. Will this fill the hole in my soul that Google Ants left behind?

phillc 12y ago
I share your pain.
- le_meta 12y ago
  Only if there were some other way to donate our time to big corporations.
Scaevolus 12y ago
This doesn't have that magical "coordinate an army" feeling that the Ants contest had. :( The rules are very simple -- you control a hero, and you fight other heros to capture mines which give you gold. You can trade gold for health in taverns. Not too much strategic depth.
- gren 12y ago
  I was also perplex the first time I entered this project. You would be surprise how this simple rules is already quite challenging. This game is fully observable and also determinist, which give way to make much more complex AI I think. I see it a bit like Chess: Pretty simple rules but there is still a fight to have the best AI in chess.

jbarrow 12y ago

If you're interested in this kind of thing and want a gentle introduction, I highly recommend CodeCombat [1], which offers both a single player version for learning the system and a multiplayer version for writing AI code. [1] http://codecombat.com http://codecombat.com

codezero 12y ago
I might have accidentally downvoted your comment, sorry about that :(
digitalzombie 12y ago
Can you recommend other resources and reading materials other than this? I would like more on top of the provided links thank you. OP's url have got me interested in AI now, but mainly for solving puzzles like this.
- jbarrow 12y ago
  What you're asking for is actually pretty broad. A lot of CodeCombat can be played with traditional Game AI strategies to try and defeat the opponent. It's one subfields of AI I've done very little research in, so take what I say with a grain of salt, but it's my understanding that the best resources for learning Game AI are actual books on the subject. I would love for someone to prove me wrong, but I don't remember too many great online sources when I was trying to learn the it. Before you start reading about different AI tactics, I would recommend just going through CodeCombat and trying out some of your own strategies. You'll get a much more intuitive sense for why things work, as well as how you would apply different strategies to your particular game.
- Houshalter 12y ago
  http://www.reddit.com/r/programminggames/ http://www.reddit.com/r/programminggames/ http://www.reddit.com/r/gameai/comments/v86kk/list_of_games_suitable_for_msc_ai_project_ai/ http://www.reddit.com/r/gameai/comments/v86kk/list_of_games_...
- lobo_tuerto 12y ago
  Some years ago I really enjoyed this book: Programming Game AI by Example http://www.ai-junkie.com/books/toc_pgaibe.html http://www.ai-junkie.com/books/toc_pgaibe.html
nnoitra 12y ago
codecombat is awful. Lags a lot, has a bad UI and a lot of bugs.

jxm262 12y ago

Dude, this is awesome! I like it

vutekst 12y ago

Can anyone comment on general strategies that would be applicable to this game? Has anyone tried some kind of crazy machine learning stuff, or is it dominated by relatively simple algorithms?

gren 12y ago
This game is fully observable and determinist so that is not the hardest situation. However there is still a lot of possible game states. I've started an attempt to have a tree of all possible actions and using a minimax algorithm (with a score function + alpha-beta pruning) but this is not yet conclusive because I can't explore so much deep (was able to explore up to 20 next player decisions but that is just 5 moves of your hero). I think this game is enough simple to try to have this approach but also challenging because there is still up to 5 possible actions per turn so it is a max of 5^1200 total of possible state for a game – a lot. My current approach is now to try to have a minimax with pre-explored interesting path in the tree (e.g. all path which leads to tavern and mines), that is still a lot of computations.
- hrjet 12y ago
  > This game is fully observable and determinist Off-topic, but are there any AI games which are not-observable and / or non-deterministic? That would be also a lot of fun!
  - sabirc 12y ago
    theaigames.com has a risk-like game (with fog of war) and a poker competiton.
- baddox 12y ago
  When I saw the premise, I was expecting that the server would provide a line of sight for your hero each turn. You could even make the map initially undiscovered, and leave it up to the bot to "remember" what it discovers. I think that would make the game a lot more interesting, although also probably much more difficult to program bots for with standard techniques.

Rexxar 12y ago

Does someone here has already created a bot for the game ?

serf 12y ago
there are starter kits available on the site.
- Rexxar 12y ago
  I don't ask for help, I just want to know if people are really trying to create a bot. Currently 90% of games are between only two AI. ("wolfie vs wolfie vs arthropod vs arthropod"). A competition like this one is much more interesting if there is a lot of players.

roryokane 12y ago

I saw this a while ago and thought that I would love to try playing this game as a human, so I could explore different strategies, or just have fun. Well, that is finally possible. I just created LiveHumanBot – a “bot” that really just lets you, a human, type in directions to control your character. Here is its code, with instructions: https://github.com/roryokane/vindinium-live-human-bot https://github.com/roryokane/vindinium-live-human-bot. I fare pretty well against other bots: http://vindinium.org/ai/p20qptiv http://vindinium.org/ai/p20qptiv.

Revex 12y ago
Now this is brilliant. I was thinking the same thing, "Man I'd like to play as a real person, before I build a bot." I feel silly now that I didn't think of building a software controller like you did. Also thanks for sharing the code. I'm gonna have to try it out.

kosinus 12y ago

Oh, neat to see this here! This was part of a local competition I participated in several months ago. Nice to see it has improved quite a bit since. I'm far from knowledgable on AI stuff, but I found this a great way to learn about some very basics, like pathfinding.

cheepin 12y ago

I would recommend having bot names be case sensitive, as well as a limit on how many a user can register. I really like the first use UX, and how easy it is to get started, but you can register as many names as you want.

ClayFerguson 12y ago

Seems like something that Google or Microsoft would ask as an interview question. You have all day to complete it, on your laptop, but once done, no matter how much code it is, they want it transcribed from your computer onto a physical white-board, because the only thing they know how to read is white-boards. If you tell them they are crazy and try to end the interview right then and there, you are hired, because you have guts, and you know what can and cannot be done, and will not waste your time with jerks.

mrqwerty 12y ago
I don't get this. I could easily transcribe anything I could write in a day into a diagrammatic representation. Hell, I could do it for anything I could write given a large enough whiteboard. It might consist of complicated flow diagrams or fragments of mathematics, but it would convey the salient points. This seems like fanatical code worship, "code is the only appropriate representation for all analytic thought". Nonsense. Maths, state diagrams, uml, even prose are useful and in combination adequate languages.
- jebediah 12y ago
  He said transcribed, I guess he meant letter by letter
- ClayFerguson 12y ago
  I was making fun of how in love some interviewers are with the whiteboard. I can write great code, but not up on a damn whiteboard -- kina because I do this thing called "typing". Also I'm making fun of the absolutely ridiculous complexity of many of the 'brain teaser' type interview questions. IMO the correct response to a brain-teaser interview question is to talk out. Better yet, tell them BEFORE the interview you WILL walk out IF the try that route.
  - ClayFerguson 12y ago
    Typo: "Talk out" was supposed to be "Walk out". Looks like you only have limited time to edit or something, because it won't let me fix that. Somebody please ding my karma again, I'm trying to see if I can make it go negative.

tylerpachal 12y ago

This reminds me of a the Student Starcraft AI Tournament: http://www.sscaitournament.com http://www.sscaitournament.com

dom96 12y ago

This looks really fun. Always wanted to participate in one of these. Good job on making it programming language agnostic :)

sytelus 12y ago

Over use of term "AI" is back. It's 80s all over again :). These kind of "challenges" are no where close to AI. They are just bit complex program whoes behavior is fully programmed by humans and they are only good at for very very specific "challange". These programs would be unable to hold a conversation with humans or read a newspaper and create their internal belief system. Stop calling these things "AI".

witty_username 12y ago
AI encompasses various things—simple AIs playing games, more complicated ones acting like humans.
Houshalter 12y ago
Video game bots have been called "AI" for decades now, it's a little late to dispute the term. The word "AI" doesn't imply "strong AI", there is "weak AI" as well: https://en.wikipedia.org/wiki/Weak_AI https://en.wikipedia.org/wiki/Weak_AI Also see the AI effect, where something is called "AI" until we actually solve it or understand it, then it is no longer called AI. "AI is whatever hasn't been done yet." https://en.wikipedia.org/wiki/AI_effect https://en.wikipedia.org/wiki/AI_effect

Tjgjfhguej 12y ago

It would be nice if the Java library allowed you to simply download the .jar instead of forcing you to use maven. This is supposed to be a game, not some massive web-scale project.

Twirrim 12y ago

Is it normal for x to reference the vertical, and y the horizontal in such games? Maybe I don't understand how they're normally represented. take this map: http://vindinium.org/4mx1xu9j http://vindinium.org/4mx1xu9j it returns the locations of the mines as: {(5, 9): u'-', (4, 9): u'-', (5, 0): u'-', (4, 0): u'-'} So that top left most mine is 4,0 instead of 0,4 that I'd would expect. It also has the location of my hero (althalus, right at the top left) as (0,1) vs my expected (1,0)

lobo_tuerto 12y ago
Maybe it's a (row,column) metaphor.

_lce0 12y ago

I've found this great project some months ago. I written a couple of robots which end up on this robot runner[1] mainly as a toy project for trying the game with some friends. [1] https://github.com/eridal/Vindinium https://github.com/eridal/Vindinium