2011-08-23T00:09:53 *** bhasker has joined #aichallenge 2011-08-23T01:26:06 *** okayzed is now known as okay 2011-08-23T01:50:47 *** okay is now known as okayzed 2011-08-23T02:12:42 *** dlila has quit IRC (Quit: Leaving) 2011-08-23T02:17:37 *** okayzed is now known as okay 2011-08-23T02:36:01 *** mleise has joined #aichallenge 2011-08-23T02:56:28 *** okay is now known as okayzed 2011-08-23T02:58:45 *** ibdknox has quit IRC (Remote host closed the connection) 2011-08-23T03:19:19 *** aerique has joined #aichallenge 2011-08-23T03:19:58 *** locutus2 has joined #aichallenge 2011-08-23T03:25:20 *** berak has joined #aichallenge 2011-08-23T03:44:34 *** ltriant has quit IRC (Quit: Computer has gone to sleep) 2011-08-23T03:47:09 *** Palmik has joined #aichallenge 2011-08-23T04:04:37 *** amstan has quit IRC (Ping timeout: 240 seconds) 2011-08-23T04:11:16 I didn't make this, but http://imagebin.org/169272 that gives 5 player symmetry including relative starting positions 2011-08-23T04:39:16 *** doddzy has joined #aichallenge 2011-08-23T04:39:42 antimatroid: so what about that pull request? 2011-08-23T04:40:26 mleise: i'll look later sorry, was at uni before, I'm not really going to know what I'm pulling though.. should I just pull it through? or harrass someone who would know better to? 2011-08-23T04:40:43 (and yes it was the middle of hte night when I responded, I have a terrible sleep pattern) 2011-08-23T04:44:29 if it is an update you could look at a diff and check if the changes are sound 2011-08-23T04:44:36 much like a peer review 2011-08-23T04:46:14 but i don't know go? just check the semantics seems right? 2011-08-23T04:47:06 Let's assume it compiles. Was this the fix for player_seed? 2011-08-23T04:47:43 So, yes. If the changes make sense semantically then pull it :) 2011-08-23T04:48:37 *** Kelt has joined #aichallenge 2011-08-23T04:49:24 *** nnullkuhl has quit IRC (Read error: Connection reset by peer) 2011-08-23T04:50:02 *** doddzy has quit IRC (Ping timeout: 252 seconds) 2011-08-23T04:50:57 seems to change quite a bit to me 2011-08-23T04:51:51 it assumes a max of 10 players i think in the debug.go file they've added 2011-08-23T04:52:39 but i don't think it'd break with more players 2011-08-23T04:53:34 *** Kelt has quit IRC (Quit: Page closed) 2011-08-23T04:54:26 I hadn't looked to deep into it. Just gave a hint that 'int' is too small for parameters like player_seed 2011-08-23T04:56:49 it has PlayerSeed int64? 2011-08-23T04:57:01 antimatroid: Oo *sure* ! 2011-08-23T04:57:33 sorry, I just looked at it, wasn't trying to be annoying :P 2011-08-23T04:57:50 should I just pull it and then someone can revert it if someone complains? 2011-08-23T04:57:58 it overall seems like they know what they're doing 2011-08-23T04:58:15 haha, I wonder if the communication here are lacking a bit :p 2011-08-23T04:58:29 *** delt0r_ has quit IRC (Ping timeout: 245 seconds) 2011-08-23T04:58:32 between us or everyone? 2011-08-23T04:58:58 between everyone working on the project. It is difficult to tell that the parameters are int64. 2011-08-23T04:59:31 I don't know if the wiki has been updated and every starter bot programmer is aware of that 2011-08-23T04:59:48 let me check the go usage count... 2011-08-23T05:00:17 i doubt the wiki has been updated, as I haven't touched it and I was the only one doing it I think 2011-08-23T05:00:54 I'm fairly busy with uni, but I could do that in a day or two once other stuff gets ready, but I don't think I'd be much help with the more vital stuff that needs fixing 2011-08-23T05:04:18 ok, there is a whole lot of ... no wait ... just 1 Go user, so just pull it anyway. The other would be the only one to complain right now ;) 2011-08-23T05:04:19 *author 2011-08-23T05:04:20 this year is extreme with mixed up words for me 2011-08-23T05:10:44 *** b_jonas has joined #aichallenge 2011-08-23T05:10:44 *** Karlo_ has joined #aichallenge 2011-08-23T05:10:52 antimatroid: ah, better 2011-08-23T05:10:52 Oops 2011-08-23T05:11:03 hello sirs :) 2011-08-23T05:11:37 and can you play this game controlling the ants partially by hand (interactively)? 2011-08-23T05:11:53 *** delt0r_ has joined #aichallenge 2011-08-23T05:12:04 aichallenge: Nick epsilon * r5b42032 / (7 files): 2011-08-23T05:12:04 aichallenge: Merge pull request #230 from humanfromearth/epsilon 2011-08-23T05:12:04 aichallenge: Go starter package: fixed player_seed issue, refactored debugging, moved - http://git.io/DHmMog 2011-08-23T05:12:19 I hadn't heard about any of this before tonight -- this bit with the ants, is that referring to a previous game rather than the current one? 2011-08-23T05:12:38 b_jonas: no (t yet), last time someone made a visualiser locally that handled tcp games for people and allowed you to play your own bot 2011-08-23T05:12:50 hopefully something like it is made again, it was by far the best debug tool I ever had 2011-08-23T05:13:09 antimatroid: but does the server allow that, and is the game not too boring by hand? 2011-08-23T05:13:21 Karlo_: the upcoming game is ants, but development has all but come to a stand still, eventually it should launch though 2011-08-23T05:13:38 I see "Planet Wars" on the Web site. 2011-08-23T05:13:41 you can't play as a human on the server, but locally you can make a program that would let you 2011-08-23T05:14:00 Karlo_: http://aichallengebeta.hypertriangle.com/index.php that's the beta site for ants 2011-08-23T05:14:11 *** mceier has joined #aichallenge 2011-08-23T05:14:15 antimatroid: is there a downloadable serveR? 2011-08-23T05:14:34 that is, server software I can download and run on my home computer. 2011-08-23T05:14:39 what do you mean? to run tournaments locally? 2011-08-23T05:14:41 So what's the chronology here -- are *both* ants and planet wars in the queue as games that will be played between bots in the future? 2011-08-23T05:16:54 *** contestbot has joined #aichallenge 2011-08-23T05:17:34 mleise: done if you didn't see :) 2011-08-23T05:18:43 @last seen carlop 2011-08-23T05:18:43 antimatroid: (last [--{from,in,on,with,without,regexp} ] [--nolimit]) -- Returns the last message matching the given criteria. --from requires a nick from whom the message came; --in requires a channel the message was sent to; --on requires a network the message was sent on; --with requires some string that had to be in the message; --regexp requires a regular expression the message must (1 more message) 2011-08-23T05:19:01 @seen carlop 2011-08-23T05:19:01 antimatroid: carlop was last seen in #aichallenge 7 weeks, 3 days, 10 hours, 2 minutes, and 10 seconds ago: mcstar: you are right, sorry for before, usually i don't do stupid calculation, and i do it twice... now time to bed.. bye 2011-08-23T05:19:49 well peoples bots are getting better, my one is down to 38th 2011-08-23T05:20:46 so is this an annual contest somewhat similar to the ICFP contest? 2011-08-23T05:21:33 there was 2 last year, this one was meant to start ages ago, but things have just sort of stalled 2011-08-23T05:21:48 not necessarily annual then 2011-08-23T05:21:52 yep 2011-08-23T05:22:52 I see -- I hadn't noticed the dates on the schedule were 2010. 2011-08-23T05:24:32 antimatroid: ok, and that @last command looks useful in irc 2011-08-23T05:24:37 So the home page is still talking about the 2010 contest, in future tense. Bah. The Google puzzle contest has had the same problem (hopefully fixed by now). 2011-08-23T05:25:01 @last --from antimatroid --with ice 2011-08-23T05:25:01 mleise: Error: I couldn't find a message matching that criteria in my history of 186 messages. 2011-08-23T05:25:25 @last --from mleise --with antimatroid 2011-08-23T05:25:25 antimatroid: [05:25:01] @last --from antimatroid --with ice 2011-08-23T05:25:52 hah, but the FAQ already claims it's "the best programming contest ever made" 2011-08-23T05:26:01 sigh, jeff hehe 2011-08-23T05:26:51 Planet Wars was a great challenge in deed :) 2011-08-23T05:27:17 I recognize PW as being a relative of a game once known as Galaxy. 2011-08-23T05:27:18 @last --from amstan --with launch 2011-08-23T05:27:18 mleise: Error: I couldn't find a message matching that criteria in my history of 193 messages. 2011-08-23T05:27:55 Karlo_: it was based on galcon, which you can play a multiplayer version of online 2011-08-23T05:28:03 Karlo_: That's right and there are many Flash Player clones now as well 2011-08-23T05:28:06 it's not exactly the same (asymmetric information) but still fun 2011-08-23T05:28:40 n-player is very different to 2 player though 2011-08-23T05:28:50 particularly with the complete graph 2011-08-23T05:29:14 In fact, Galaxy is the game for which I wrote that n-player symmetry thing that I mentioned earlier. 2011-08-23T05:29:29 that's pretty coincidental :D 2011-08-23T05:31:37 So... Maybe you already answered this... 2011-08-23T05:32:11 The ai-contest.com page seems to be talking about Planet Wars exclusively. How do I get to a page that talks about Ants? 2011-08-23T05:32:23 with the link i gave above 2011-08-23T05:32:37 it's the beta site, i'm not sure the ai-contest page links to it 2011-08-23T05:32:38 @topic 2011-08-23T05:32:38 antimatroid: Official Google AI Challenge: http://ai-contest.com/ || Channel Logs: http://contestbot.hypertriangle.com/ || Code Repo: http://github.com/aichallenge/aichallenge || Beta testers needed: http://aichallengebeta.hypertriangle.com/ (amstan) || Launch Preparation Meeting http://bit.ly/kYYbD4 (amstan) 2011-08-23T05:32:40 that has it too 2011-08-23T05:32:44 @beta 2011-08-23T05:32:45 antimatroid: beta could be http://aichallengebeta.hypertriangle.com/. 2011-08-23T05:32:50 or that :) 2011-08-23T05:33:06 OK 2011-08-23T05:33:25 i'm off to prepare some dinner, i'm starving 2011-08-23T05:35:22 I haven't entered any sort of bot contest for years... 2011-08-23T05:36:30 it's very fun, and very time consuming :) 2011-08-23T05:36:47 The last one I did, I believe I had an unbeatable bot (as did several other players; the game was solvable), but the organizer said that mine aborted on one of my own bugchecks. 2011-08-23T05:36:51 once it launches it should run for like 2 months or so 2011-08-23T05:37:04 oh don't remind me :P 2011-08-23T05:37:17 I later grabbed the referee source code and all bots, and tried it myself, and it seemed to work just fine. I never did find out what happened. 2011-08-23T05:37:29 i got disqualified in tron because of an arcane rule at the time which said that a single timeout was grounds for disqualification 2011-08-23T05:37:45 i never even got to see the game i timed out on 2011-08-23T05:38:37 http://csclub.uwaterloo.ca/contest/profile_games.php?user_id=2788 that was my (and my friends) bots run until timing out, we were ranked ~10th 2011-08-23T05:39:48 timeouts just meant you lose in planet wars, in ants it means all your ants stop moving and you stop accumulating points (the still ants can spawn if food spawns next to them, the idea being to minimise the advantage to neighbouring bots) 2011-08-23T05:40:18 the relative symmetric / 2-transitive maps could really fix that problem 2011-08-23T05:40:20 How long is the timeout? 2011-08-23T05:40:42 not sure what it currently is, 500 or 1000ms i think, it's passed to the bots at the start of the game as a parameter 2011-08-23T05:40:48 wait... does the game spontanously add new food to the map after the start of the game? how about spontanously removing food (rotting)? 2011-08-23T05:41:05 so that we can change it without people bitching about hard coding stuff, there's quite a few parameters like that because in the past people winge when things change 2011-08-23T05:41:16 Right 2011-08-23T05:41:33 b_jonas: no removal of food that doesn't spawn, but we symmetrically (from starting positions) spawn food 2011-08-23T05:41:58 Did you ever play Core War? 2011-08-23T05:42:09 we find a basis of land squares for the grid, randomly order them, then spawn food at a given rate to those cells, if a cell is "taken" then the food spawns there on the next turn that it isn't 2011-08-23T05:42:16 nope, but it sounded sweet 2011-08-23T05:42:35 basis/generating set 2011-08-23T05:42:37 I'd read the CW rules and didn't like it -- it seemed that offense was way easier than defense. 2011-08-23T05:42:40 I see, thanks 2011-08-23T05:42:42 basis probably isn't the right word :P 2011-08-23T05:43:03 it would be nice if the specification mentioned this 2011-08-23T05:43:27 yes, eventually i'll add it sorry, it's in beta and stuff changes so I got sick of changing things all the time 2011-08-23T05:43:46 once the game is pretty much good to launch I'll go through and make the specs more correct and complete 2011-08-23T05:44:14 thank you 2011-08-23T05:44:22 but I also have to limit the amount of maths terminology in the specs because the game is meant to be easy enough for beginner programmers but deep enough to be interesting to more experienced programmers 2011-08-23T05:44:42 if you have any queries, i think I know most things to do with game mechanics, so just harrass me here 2011-08-23T05:44:54 I should respond within 24 hours if no one else does 2011-08-23T05:46:41 *** mathis has joined #aichallenge 2011-08-23T05:46:47 My understanding (possibly incorrect) is that Core War was invented when someone misremembered the rules to the older game Darwin. I always thought Darwin was the better game, and I've created implementations of it a few times for different architectures. 2011-08-23T05:46:49 My latest one runs as an emulator of an absurdly reduced instruction set; it requires a significant number of instructions to do anything useful at all. I'm hoping this makes it challenging enough to avoid the problems of McIlroy's original game. 2011-08-23T05:47:23 Karlo_: planet wars was probably the most interesting of "our" games mathematically, it was a sweet "problem" but it ended up being quite inpenetrable with respect to really good ai's, except bocsimaco who showed EVERYONE up 2011-08-23T05:47:34 Interesting. 2011-08-23T05:47:54 he had a "2 ply" minimax tree for the first turn then not entirely sure after that 2011-08-23T05:48:24 I have a couple of games on my own machine that I've wanted to write AIs for. 2011-08-23T05:49:06 the "long term" plan is to rewrite everything to handle multiple contests and have old ones set up sort of like project euler 2011-08-23T05:49:15 Nice. 2011-08-23T05:49:27 but at the current rate that isn't happening in the near future 2011-08-23T05:49:29 Have you ever heard of the GGP project at Stanford? 2011-08-23T05:49:34 nope? 2011-08-23T05:49:40 GGP is General Game Playing. 2011-08-23T05:50:01 oh, i would love to do something like that 2011-08-23T05:50:19 The contestants write bots that are designed not for playing a specific game optimally, but for playing *any* game adequately. 2011-08-23T05:50:20 i'm doing my honours thesis on structure properties of normal form games 2011-08-23T05:50:39 So they have to be prepared to deal with games they've never seen before. 2011-08-23T05:50:45 basically playing around with isomorphisms and symmetric games and filling in the few blank steps to set up a category 2011-08-23T05:51:13 and I have a c++ library for game theory stuff, which I would love to use for a ggp type bot and have considered it 2011-08-23T05:51:20 Cool. 2011-08-23T05:51:45 if only I had infinite time to do all the things I want to :( 2011-08-23T05:51:54 Agreed! 2011-08-23T05:53:30 a game I wonder might be interesting to hold AI contests of is single player rubber's rummy where one player controls multiple hands (say four hands) and the goal is to quit in as few turns as possible 2011-08-23T05:54:45 GGP does simultaneous or sequential play, solitaire or two-player or multi-player, cooperative or competitive. 2011-08-23T05:55:01 the real problem I would enjoy tackling is filling in the blanks between obtaining the game rules and constructing a game to choose a (n equilibrium) strategy from 2011-08-23T05:55:57 I programmed a few game descriptions but didn't actually test them on the GGP server with actual playerbots. 2011-08-23T05:56:02 b_jonas: so far we've just dealt with simultaneous games for this, personally I think they're strategically more interesting, but others probably don't agree with me there 2011-08-23T05:56:31 i do however enjoy extensive form games too and have the code for representing those, but it's not clean enough to have up on github 2011-08-23T05:56:33 sure, I like multiplayer games as well 2011-08-23T05:56:47 multiplayer games can be simultaneous :P 2011-08-23T05:56:54 Indeed. 2011-08-23T05:58:19 Liar's Dice would make a good AI testbed, I think. 2011-08-23T05:58:38 one game people are quite interested in is something like risk 2011-08-23T05:58:45 but i don't personally know much about the game 2011-08-23T05:58:57 i think dots and boxes could be interesting too 2011-08-23T05:59:03 Yeah 2011-08-23T05:59:29 do you know anything about dynamical games (aka multiplayer optimal control theory if you ask me?) 2011-08-23T05:59:34 a 3d chasing game would be interesting 2011-08-23T05:59:41 dots and boxes require thinking. it's not the kind of game I like. 2011-08-23T05:59:48 Cosmic Tag? 2011-08-23T05:59:55 Just a sec, let me pull up my notes :-D 2011-08-23T06:00:08 you mean a simple 3d fps? 2011-08-23T06:00:19 well, i'm thinking planes in combat 2011-08-23T06:00:42 so you have motion in 3d and you have to shoot your enemy down or something 2011-08-23T06:01:39 Basic version of Cosmic Tag: Two ships, arbitrary Newtonian acceleration with maximum magnitude A. Maintain position, velocity, acceleration data for each. Tagger wins by getting within distance 1 of Runner. Runner wins by getting within distance K of Origin. 2011-08-23T06:02:10 that gets interesting with many players only, right? 2011-08-23T06:02:40 There are no turns -- you submit orders whenever you like, and specify when they should take effect, if not immediately. 2011-08-23T06:03:05 The original implementation of this concept was done in real time, over a period of months. 2011-08-23T06:03:44 i imagine the solution to that in 3d isn't different to 2d? 2011-08-23T06:03:46 just generalised? 2011-08-23T06:04:02 the chaser/evader problem predator/prey whatever 2011-08-23T06:04:08 also, how many walls? 2011-08-23T06:04:16 A little trickier in 3d, I think. 2011-08-23T06:04:41 although I don't think that puts constraints on change of angle / velocity (I don't know physics very well) 2011-08-23T06:04:42 No walls in this game -- the *only* objects in the universe are the two ships, and the fixed origin. 2011-08-23T06:05:52 ideally i'd want a symmetric game, but such a complicated game would never fly for an ai contest anyway 2011-08-23T06:05:57 so isn't that important 2011-08-23T06:06:57 Strange. I was sure I had another file related to this game, somewhere. 2011-08-23T06:11:02 *** sigh has joined #aichallenge 2011-08-23T06:11:10 *** mceier has joined #aichallenge 2011-08-23T06:13:30 Oh, here's a different (symmetric) game I've toyed with... 2011-08-23T06:14:22 n players, arranged randomly in a circle; each simultaneously chooses either "Attack" or "Defend". 2011-08-23T06:14:46 If someone attacks you and you're not defending, you're eliminated. 2011-08-23T06:15:41 Karlo_: um no, the rules are a bit complicated than that 2011-08-23T06:15:46 (In the original version, you could attack any other player; in the version I was analyzing mathematically, I restricted it only being able to attack the player to your immediate right. So you're defending against the player to your left.) 2011-08-23T06:15:58 Karlo_: you can choose to defend, attack, or charge 2011-08-23T06:16:03 Different game. 2011-08-23T06:16:08 but you can attack only if you have charged since your last attack 2011-08-23T06:18:08 If there's only *one* attacker in some round, then that player wins immediately -- that's the only rule thwarting the "always defend" strategy. 2011-08-23T06:18:46 Otherwise, the attacks are resolved, the circle closes up, it gets a new random ordering for the next round, and the game continues. 2011-08-23T06:19:30 If some round eliminates everybody at once, then those who survived the longest (the participants in the final round) share the win equally. 2011-08-23T06:20:09 that is neat 2011-08-23T06:20:33 i like the graph game where one player tries to join two nodes by "fixing edges" and another tries to separate them by removing non-fixed edges 2011-08-23T06:20:39 not simultaneous though 2011-08-23T06:20:47 I came up with an approximately optimal strategy for n-player... 2011-08-23T06:21:11 but a good AI would probably do opponent modeling, keeping track of what other players have done in the past. 2011-08-23T06:21:30 If a mad attacker is behind you this round, you might just want to defend. 2011-08-23T06:22:01 Ah yes -- that graph game has an unfortunate number of names. 2011-08-23T06:22:13 Bird Cage, Gale, Shannon's Switching Game... 2011-08-23T06:22:42 I rather liked "Short Circuit" as a name, but there's no point in adding another one to the collection. 2011-08-23T06:24:12 in the games we've done so far you don't know who your enemy is 2011-08-23T06:24:23 and you can't write to file on the main servers 2011-08-23T06:24:33 you can of course locally for debugging purposes or training parameters 2011-08-23T06:24:40 We can imagine the graph to be made of resistors; one player is joining the nodes (reducing the resistance to zero) while the other is cutting them (increasing the resistance to infinity). 2011-08-23T06:26:46 Karlo_: a fun problem i had when I was playing around with ants was a* search with multiple sources and targets 2011-08-23T06:27:43 it you use T as the set of targets (say food locations) then the heuristic h(x) = argmin_{* in L}mdist(x, *) is admissible 2011-08-23T06:28:12 and you can just add all of your source locations to the search queue before you start searching 2011-08-23T06:29:35 Do you know the game Arimaa? 2011-08-23T06:29:48 It's like Chess, but better. :-) 2011-08-23T06:29:56 yes, janzert has (I think) the third best bot from the last few years 2011-08-23T06:30:07 he has been one of the bigger contributers here 2011-08-23T06:30:09 OK 2011-08-23T06:30:43 i have thought a little bit about it, but haven't actually written a bot 2011-08-23T06:31:08 i would like to try implementing it as a kind of graphical game (not the normal graphical game def) 2011-08-23T06:31:11 I haven't even seriously considered writing one -- I don't play the game well enough, myself. 2011-08-23T06:31:26 i don't really play games 2011-08-23T06:31:34 i just like writing bots and game theory :P 2011-08-23T06:31:49 Heh, OK 2011-08-23T06:31:59 (I do both game theory and actual games.) 2011-08-23T06:32:12 what kind of game theory stuff do you do? 2011-08-23T06:32:28 Did you see my monolog about the game of Hi-Lo, a week or so ago? 2011-08-23T06:32:34 nope? 2011-08-23T06:32:49 That's my name for the simple number-guessing game, similar to Twenty Questions... 2011-08-23T06:32:53 i'm lucky enough that my advisor will let me play around with game theory but nobody in my maths department really knows anything about it 2011-08-23T06:33:34 have you heard of andy mclennan? i've contemplated trying to do a phd under him, but he's in an economics department, otherwise i might just do a phd where I am (tasmania) 2011-08-23T06:33:34 Hider picks an integer 1 <= x <= n; Seeker guesses numbers one at a time. After each incorrect guess, Hider replies with whether x is higher or lower. The payoff is the number of guesses. 2011-08-23T06:33:50 either on game theory stuff or just category theory/something algebraey 2011-08-23T06:34:15 The naive strategies are (Hider) uniform on 1..n; (Seeker) binary search. But neither one is optimal in the game theory sense. 2011-08-23T06:35:01 what is optimal? 2011-08-23T06:35:13 The smallest interesting case is n=3, where the game value is 1.8. 2011-08-23T06:35:38 is that for the worst case of binary search or..? 2011-08-23T06:35:53 Average case, under optimal play. 2011-08-23T06:36:05 Hider's optimal strategy is ([1] 2/5, [2] 1/5, [3] 2/5). 2011-08-23T06:36:24 Seeker's optimal strategy is ([2] 3/5, [1-3-2] 1/5, [3-1-2] 1/5). 2011-08-23T06:37:00 Game value = 9/5. 2011-08-23T06:37:24 i'm confused 2011-08-23T06:38:06 Ask a question, and perhaps I can unconfuse. 2011-08-23T06:38:10 wouldn't seeker go something like 3/2 -> etc. 2011-08-23T06:38:26 The search space is {1, 2, 3}. 2011-08-23T06:38:27 as in 1.5 -> 1.75 -> 1.875 -> ... 2011-08-23T06:38:48 Hider is in one of those three positions. No fractions. 2011-08-23T06:38:50 oh, so mixed strategies? 2011-08-23T06:38:55 Yes 2011-08-23T06:38:59 okay 2011-08-23T06:39:38 Binary search would be to start at 2; if Hider isn't there, then Seeker can definitely find him on the 2nd guess. 2011-08-23T06:39:46 yep 2011-08-23T06:40:04 fractions would make it a lot harder :P 2011-08-23T06:40:08 But the mixed strategy reduces it to 9/5. 2011-08-23T06:40:30 (countably) infinitely harder 2011-08-23T06:40:46 And difficult to define the goal :-) 2011-08-23T06:41:03 find p,q such that p/q \in [0, 3]? 2011-08-23T06:41:12 and you get high or lower 2011-08-23T06:41:52 With infinitely many hiding places available? I think that every strategy is dominated. 2011-08-23T06:42:30 what about if you constrain p and q? 2011-08-23T06:42:51 I've already considered some other modifications to the game that I think are more interesting, actually. 2011-08-23T06:42:53 it's not necessarily equivalent to just increasing n i don't think? 2011-08-23T06:43:31 (This would actually be more suitable to #math -- shall I go back there?) 2011-08-23T06:43:43 no one will mind here 2011-08-23T06:43:45 OK 2011-08-23T06:44:06 (i hope :P) 2011-08-23T06:44:07 First, let me finish what I found about the basic game. 2011-08-23T06:44:35 For large n, the value is log_2(n) + O(1), as you might expect. 2011-08-23T06:46:23 I have the optimal Hider strategies for 1 <= n <= 23. 2011-08-23T06:47:47 For many of those n, it turns out that it's optimal for Hider to use a uniform distribution except for double-weighting the endpoints -- i.e., the mixed strategy (2 1 1 ... 1 1 2) / (n+2). 2011-08-23T06:48:15 This is true for 3..4, 7..10, 17..23 2011-08-23T06:49:03 that's pretty neat 2011-08-23T06:49:12 And for several values of n, it's optimal for Hider to use a different near-uniform distribution proportional to (5 3 2 2 2 ... 2 2 2 3 5). 2011-08-23T06:49:31 This is true for 4..6, 15..16 2011-08-23T06:50:29 For 11..14, and also 24..31 which I haven't solved, neither of those is optimal. 2011-08-23T06:51:38 Karlo_: this Hider/Seeker game you mention is funny 2011-08-23T06:51:41 (If you were paying attention, you might notice that I listed n=4 in both of those sets -- n=4 is the only known case where there's more than one optimal strategy.) 2011-08-23T06:52:39 Funny how? 2011-08-23T06:52:48 also, it's natural that the value is log_2(n)+O(1) because (a) from the seeker any binary search wins within that much time, but (b) if the hider is uniform then the seeker surely can't be much smarter 2011-08-23T06:52:57 Right 2011-08-23T06:53:58 I conjecture lg(n) - 1 + 2s/(1+s) - lg(1+s) + lg(n)/n + O(1/n) for the asymptotic behavior, which is much more precise... 2011-08-23T06:54:31 what's s ? 2011-08-23T06:54:59 where s = n/2^floor(lg(n)) - 1, which is in [0,1) 2011-08-23T06:55:47 I.e., the O(1) component has a "wobble" that depends on how close n is to being a power of two. 2011-08-23T06:56:13 This was the first game I implemented at school when casio borrowed us those programmable calculators 2011-08-23T06:58:18 So anyway, here are the variants I was considering: 2011-08-23T06:58:57 *** sigh_ has joined #aichallenge 2011-08-23T06:59:22 * Delay Hi-Lo: after each wrong guess, Hider reports the outcome of the *previous* guess rather than the current one. This changes the asymptotic behavior from log_2(n) to log_phi(n). 2011-08-23T06:59:24 *** sigh has quit IRC (Ping timeout: 240 seconds) 2011-08-23T07:00:39 * Liar Hi-Lo: after a wrong guess, Hider is permitted to lie about the direction of x, but only once per game. (Inspired by Ulam's problem.) Asymptotic behavior is log_b(n) for some phi <= b <= 2; I don't know the value yet. 2011-08-23T07:01:21 (Oh, actually that last result is for *worst case* behavior rather than optimal play.) 2011-08-23T07:02:49 * Mover Hi-Lo: after a wrong guess, Hider is permitted to either keep the current value of x, or add 1 to it. (Yes, I know I could make it symmetric by also allowing him to subtract 1, but it turns out that this is already complex enough.) Still asymptotically log_2(n). Smallest interesting case is n=5; it was quite difficult to find the exact solution. 2011-08-23T07:03:01 [end of list] 2011-08-23T07:03:16 i'm interested in the dynamics of the liar version 2011-08-23T07:03:24 how complicated can a contradiction become? 2011-08-23T07:03:47 Seeker's knowledge state is encoded by a 4-tuple. 2011-08-23T07:04:17 a <= x is certain; b <= x is claimed, x <= c is claimed; x <= d is certain. 2011-08-23T07:05:27 Once a contradiction has been revealed -- q <= x and x <= p both asserted, where p < q -- Seeker just switches to binary search on the set of possible points. 2011-08-23T07:06:13 :) 2011-08-23T07:08:31 Maybe Liar Hi-Lo would make a good game for a bot competition? 2011-08-23T07:11:47 not sure people would find it that interesting tbh 2011-08-23T07:12:14 Challenging to program, but pretty boring to watch, I imagine. 2011-08-23T07:12:19 i've found the types of games that interest mathematicians don't interest most people 2011-08-23T07:12:28 Yep 2011-08-23T07:12:47 they want it to be fun to play and watch, i mostly want it to be fun to think about 2011-08-23T07:12:50 to each their own 2011-08-23T07:13:49 During one of the GGP competitions, the bots were moving somewhat randomly, not seeming to make any progress; it was kind of annoying. 2011-08-23T07:14:10 I felt like I was watching the Special Olympics. :-) 2011-08-23T07:14:56 qwopolympics? 2011-08-23T07:15:09 one does not simply qwop anywhere 2011-08-23T07:16:07 I don't know what that means 2011-08-23T07:16:40 let me introduce you to the hardest game ever made 2011-08-23T07:16:43 http://www.foddy.net/Athletics.html 2011-08-23T07:17:54 Liar Hi-Lo for n = 10^6 might actually be interesting to watch.] 2011-08-23T07:22:09 Karlo_: would my relative symmetry thing be equivalent to requiring the game be symmetric for any subset of the players (eliminating the others) (with at least two players) 2011-08-23T07:23:54 Possibly. 2011-08-23T07:25:01 did you play qwop? 2011-08-23T07:25:14 i can't play it to save my life, but... there's a hurdle at 50m 2011-08-23T07:25:41 *** dlila has joined #aichallenge 2011-08-23T07:27:06 Nope. I have Flash disabled on this machine, and the one that can do it is currently in an awkward spot to use. 2011-08-23T07:27:19 I read the description on Wikipedia, though. 2011-08-23T07:32:54 I just scrolled back to my summary of Hi-Lo variants. I misspoke: for Mover Hi-Lo, the first interesting case is n=3, and *that* was difficult to solve. 2011-08-23T07:34:25 i take it you haven't solved greater then? 2011-08-23T07:34:33 Correct. 2011-08-23T07:35:20 Basic up to n=23; Liar up to n=5; Mover up to n=3. 2011-08-23T07:35:47 solve all the things 2011-08-23T07:36:21 Perhaps Delay-Liar-Mover Hi-Lo would make an interesting bot challenge :-D 2011-08-23T07:37:38 same problem :P 2011-08-23T07:37:59 In 3d, with a cool graphics display!! 2011-08-23T07:42:04 There's a game I used to play in college -- and then taught to family members -- that I thought had an excellent fun/complexity ratio. It seemed to me that it should be possible to write a bot for it, but it's yet another item that I never got around to doing. 2011-08-23T07:43:27 My brother did write a bot for a simplified version of the game, and then claimed that the game was no longer playable because the bots always won -- but that was because their primary strategy was "team up with any other bots in the game, and attack the human" 2011-08-23T07:52:56 antimatroid: I found QWOP can crawl on one knee, using the other leg to give little impulses forwards 2011-08-23T08:18:49 mleise: with q and w? so did i, i got like 9 metres :P 2011-08-23T08:18:58 i would have been screwed if i made it to the hurdle though 2011-08-23T08:19:16 there is a hurdle? geez, that's impossible 2011-08-23T08:19:48 http://www.youtube.com/watch?v=VJeJtK7Q2kk 2011-08-23T08:21:10 seems you can just knock it over 2011-08-23T08:28:01 OK, I'm off to bed now 2011-08-23T08:28:15 *** Karlo_ has quit IRC (Quit: zzz) 2011-08-23T08:38:39 *** dr- has quit IRC (Quit: WeeChat 0.3.0) 2011-08-23T08:54:07 *** Palmik_ has joined #aichallenge 2011-08-23T08:57:34 *** Palmik has quit IRC (Ping timeout: 258 seconds) 2011-08-23T09:13:08 *** Byteroot has joined #aichallenge 2011-08-23T09:13:31 Hi 2011-08-23T09:13:47 can someone help me with tools for ants challenge ? 2011-08-23T09:14:00 I'm using windows XP and Python32 installed 2011-08-23T09:14:17 when launcing play_one_game.cmd I'm getting an error 2011-08-23T09:14:33 Traceback (most recent call last): File "D:\php_starter_package_ants\tools\playgame.py", line 11, in import StringIO ImportError: No module named StringIO 2011-08-23T09:18:30 *** mcstar has joined #aichallenge 2011-08-23T09:22:45 Byteroot: i think it needs python >= 2.7 2011-08-23T09:23:12 Python 3.2.1 installed 2011-08-23T09:23:53 Should I install 2.7.x version ? 2011-08-23T09:24:28 *** mathis has quit IRC (Disconnected by services) 2011-08-23T09:24:39 well it works with 2.71 here(xp, too) 2011-08-23T09:25:21 Thank you. I will try it 2011-08-23T09:26:05 you could uncheck the 'install' option in the installer, so it won't override your 3.2 settings 2011-08-23T09:26:50 thanks once more =) I never worked with python before 2011-08-23T09:29:22 *** berak has quit IRC (Quit: ChatZilla 0.9.84 [SeaMonkey 2.0a3/20090223135443]) 2011-08-23T09:30:54 If someone else have same problem - installing 2.7.2 is the solution 2011-08-23T09:49:15 *** aerique has quit IRC (Quit: ...) 2011-08-23T10:02:51 *** Eruonen has joined #aichallenge 2011-08-23T10:04:39 *** onensora has quit IRC (Ping timeout: 250 seconds) 2011-08-23T10:11:43 *** sigh_ has quit IRC (Remote host closed the connection) 2011-08-23T10:18:17 *** Byteroot has quit IRC (Quit: Page closed) 2011-08-23T11:31:48 *** onensora has joined #aichallenge 2011-08-23T11:34:20 *** Eruonen has quit IRC (Ping timeout: 260 seconds) 2011-08-23T11:38:43 *** Kingpin13 has joined #aichallenge 2011-08-23T12:21:44 *** Apophis_ has quit IRC (Ping timeout: 240 seconds) 2011-08-23T12:26:36 *** Apophis has joined #aichallenge 2011-08-23T12:27:45 *** FireFly has joined #aichallenge 2011-08-23T12:41:39 *** KP13 has joined #aichallenge 2011-08-23T12:42:00 *** JamesMG_ has joined #aichallenge 2011-08-23T12:42:21 *** JamesMG has quit IRC (Ping timeout: 240 seconds) 2011-08-23T12:42:41 *** mceier has quit IRC (Ping timeout: 240 seconds) 2011-08-23T12:42:58 *** mceier has joined #aichallenge 2011-08-23T12:43:13 *** Kingpin13 has quit IRC (Disconnected by services) 2011-08-23T12:43:25 *** KP13 is now known as Kingpin13 2011-08-23T12:43:41 *** okayzed is now known as okay 2011-08-23T12:44:11 *** moondust has quit IRC (Ping timeout: 240 seconds) 2011-08-23T12:44:17 *** moondust has joined #aichallenge 2011-08-23T12:52:28 *** javagamer has quit IRC (Ping timeout: 240 seconds) 2011-08-23T12:58:59 *** delt0r_ has quit IRC (Ping timeout: 264 seconds) 2011-08-23T13:00:39 *** javagamer has joined #aichallenge 2011-08-23T13:07:03 *** jako