- Updated Wednesday, June 22nd 2016 @ 00:07:00
Since the competition is still in beta I wanted to give my thoughts on the current state of the game. At the moment there are a couple things which bother me and I think a lot of this could be fixed by lowering the time per move and/or timebank. There are a couple of reasons for this.
Firstly, when games take less time the rate of games played on the server could go up without taking up extra resources. Right now rating converges very slowly. This is partly due to the imbalance between first and second player and also because there are many participants in this challenge and the number is still rising.
Secondly, I think this change would make the choice of programming language less important. I'm not using C++ in this challenge so perhaps I'm a bit biased on this.
And lastly I think it would make developing bots more enjoyable as you can test the performance of a new implementation/modification quickly without the need of a large amount of computation time. It also allows for more interesting heuristics that don't necessarily scale that well with time.
Update: I no longer think less time per move is the right solution.
- Created Friday, June 17th 2016 @ 01:39:10
I agree with a lot of the concerns raised in this post, but I think some of the conclusions are backwards and that there are a lot of problems with reducing the time per turn.
Regarding the number of games bots get to play, I think a lot of my dislikes would be resolved with changes to how the game queue is managed. It's really frustrating to sometimes go 8 to 12 hours without my bot playing any games. There are approximately 350 bots in the game now, and (it seems like) two games running at any given time. That means that we should be getting a game about once every 90 minutes. I think changing the game queue to make sure people are fed a steady drip of games instead of the current "feast or famine" method we have now would make it much less frustrating (to me at least!).
The time to converge is also a problem, though, I agree--it does seem to take forever (I seem to finally have stabilized after around 80 games), but I believe there are other ways to try and fix the problem. Two completely untested suggestions off the top of my head are to have context sensitive K values in the ELO update formula. Winning as player 1 or losing as player 2 would use a lower K than losing as player 1 or winning as player 2. Draws could stay the same as they are now. Another option (which has been suggested by others in other threads) is to simply play two games in a row, once as player 1 and once as player 2. This would remove the RNG factor from the rankings and would make sure the player 1 bias was, not removed, but spread evenly. Or, there's the obvious one and they could just throw more servers at it. Since it's not my money, that's what I think they should do. :P
I also think the choice of language would become MORE important as the time was reduced. Compiled languages will always be x% faster and no matter how much time you give them they will always be able to do x% more. In many cases, the difference between being able to do a thing 100 times vs 150 times is hugely more beneficial than going from, say, 10,000 to 15,000. Speaking to Java (since that's what I'm most familiar with), garbage collection pauses are frequently longer than your proposed 100ms turn, which means bots may time out with no opportunity to perform any useful work. For perspective, I have to allow a buffer of 2 full seconds in order to avoid random timeouts from garbage collection pauses. These are problems, of course, that C++ and its ilk simply don't have to contend with.
Do you do any local testing or do you rely entirely on "live" games? I do essentially all of my testing locally, and run my tests with a fraction of the time and processing that the actual system provides. On average, my test games take just a hair over 1 second per game. I've found these results are just as useful for comparing versions of my bot as full-length games and allow rapid turnaround when trying out a new change. It does require writing the engine for the game, but especially for this one, it's so simple that it shouldn't be a problem for anyone capable of seriously competing in this game.
Finally, my strongest disagreement is that limiting the time per turn somehow allows for more "interesting" techniques and heuristics. By very definition, less time (and everything else being equal) means you can do less work, and less work means you are limiting the sort of things your bot can practically do.
Personally, the short time per turn has always been one of my biggest pet peeves of this site. When I started doing these sorts of competitions it was in the general game playing field (www.ggp.org for anyone interested). While I realize there are limits to the comparison, games there were run with tens of seconds of "startup" time and then tens of seconds of time per move. To me, 500 milliseconds per turn feels like handcuffs.
I'm very curious what other people think on this topic.
- Created Friday, June 17th 2016 @ 11:09:49
Alright I think I was wrong about the programming language issue. I was thinking too much about the absolute time difference and forgot early time is way more valuable. I don't entirely agree with your "strongest disagreement" though as wisely choosing how to limit your bot can still contribute to the competition. At current time controls there seems to be little benefit to apply these sort of restrictions, but perhaps I'm just too inexperienced to figure out how to do it.
- Created Friday, June 17th 2016 @ 11:58:50
@melsonator Perhaps a bit of a personal question, but do you mind telling me what exactly you are doing while my bot is thinking that makes my bot perform much worse in the same time than it usually does? Do you allocate huge amounts of memory?
- Created Friday, June 17th 2016 @ 14:25:18
I have a (probably controversial) Idea for reducing the advantage of the first Player:
The first move gets played randomly.
I think the games would be much more even then, probably it would become a little advantage for player2.
- Created Friday, June 17th 2016 @ 17:15:12
@Daporan, I absolutely agree that there is still skill involved at the super constrained times, but it's not the same kind of skills required when you have more time available. I believe there are three overarching skills that go into making a top bot: the botmaker's skill at the game being played, skill in algorithm design, and skill at implementation. If you have super fast turns I think it would favor the first skill, because people who are good at the game can encode their knowledge directly into a very simple bot and still be one of the best. As the amount of time available increases, the benefit starts to go to the better algorithms and implementations. Of course, the ultimate combination is to both have a good algorithm, a good implementation, AND be good at the game. In the extreme, you have something like AlphaGo, which was made by highly skilled amateur Go players who were top tier algorithm designers and implementers. It still took over an average of a minute per move on absolutely ridiculous hardware to be able to beat a top human player.
Regarding your question about my bot, I actually think we should be talking about what our bots do (to a certain extent; I don't think we should be sharing source code or anything), since I think it increases the level of play of everyone participating. So, to answer your question, I do the same thing I do during my turn. I start my search immediately upon startup and continue almost straight through the entire game, stopping only to update the game state when the engine tells me it's my turn to make a move and then again when I am actually responding with the move I wish to make. I have almost zero "downtime" when I'm not searching.
@supinf I thought that was an interesting idea, so I decided to implement it this morning. :) However, preliminary results (160 games) show that it swings the pendulum too far in the other direction. Using the current rules, my wins/loss/draw %s are about 30/30/40 (when I test, I play N games as player 1 and N as player 2 and then combine the results, as player 1, the results are split more like 50/10/40). With the "first player moves randomly" rule, the combined results were around 30/40/30. Unfortunately, I'm at work right now and don't recall the exact specifics, but the gist is right. I'm running a longer test while I'm at work of 1600 games, and I'll update this post when I get home with the real numbers.
Your idea did remind me of another technique that I think I remember from the general game playing guys. Basically, player 1 goes first, then player 2 goes twice, and then it continues its usual alternating between player 1 and player 2. I'm going to see if I can find some more information on this technique and if I can find it, I'll post it here, too.
- Created Friday, June 17th 2016 @ 17:44:20
@melsonator Thanks for sharing your approach. I guess it's a bit better than what I'm doing now which is starting a new thread for ponder purposes right before my main thread returns a move. This probably brings some overhead, although it's unlikely to make a big difference. I am wondering if you also notice some performance drop when playing against my bot. You could print measurements to stderr to confirm this, but I figure you're probably already doing that. Also, congratulations on rank 1 :)
@supinf Interesting idea, but I don't think the imbalance of first and second player is a problem if two conditions are met. The first one being that we need enough/more games being played and the second one being that the semi-finals and finals must be played in pairs of two games where each bot gets the opportunity to go first. I think it's unreasonable to try to perfectly balance the game. It's a lot safer to go with the above than to have finals that are skewed with a couple % advantage for one player.
- Created Saturday, June 18th 2016 @ 05:59:51
@Daporan, Thanks! And yeah, I print out all sorts of good stuff. :) I just went back and looked and it seems like I perform about 35% fewer operations against you and other top tier bots than I do against the random lower tier bots that occasionally challenge me.
Re: random player 1 moves - I checked my test and after 1600 runs, I have a slight revision from what I stated earlier. I'm not sure if I was misremembering or if the results were actually just different, but I got approximately a 40/30/30 win/loss/draw split as player 1, so there's still a bit of an advantage, but it is less. I think it also might make for some more varied games besides player 1 always just starting with "4,4".
- Created Sunday, June 19th 2016 @ 01:38:09
thx for the simulation! - I am mildly surprised, that player1 still has advantage. But thats probably because there are not a lot of bad moves among the 81 possibilites. And besides, if bots are too deterministic, that would introduce a bit of randomness
- Updated Wednesday, June 22nd 2016 @ 01:46:34
So this confirms other posts about pondering, that both bots share the same single CPU. So, if you are pondering, you limit the amount of processing done by your opponent. That is a shame, I found out that pondering was practically neutral for my bot when running locally so I left it turned off. I may turn it on to level it against bots that do ponder.
- Updated Monday, June 20th 2016 @ 22:21:41
Yes, I agree it's a shame, and I was thinking the same thing... to detect if the opponent is pondering, and if so, start doing it in my bot. At least this has allowed me to figure out why my bot was quite often losing on time against Jaeger -- I've been using clock() for timing -- doh! :) What do other bots use for timing real time instead of cpu time (in c++)?
- Updated Monday, June 20th 2016 @ 23:35:07
The steady__clock from the standard chrono library is the best solution for that. It is a standard library introduced in C++11 and it is OS agnostic. Although I must say I'm not a fan of the API design. See http://www.cplusplus.com/reference/chrono/steady_clock/
- Updated Tuesday, June 21st 2016 @ 23:26:38
Thanks, rahenri, I'll give that a go for my next release.
I'll add a bit to the random first moves discussion by posting the 1st player percentage win rate over 180,000 odd games for each of the possible 1st moves:
52.9 52.5 53.1 50.3 53.3 0.0 0.0 0.0 0.0 0.0 51.4 52.2 51.7 50.8 0.0 0.0 0.0 0.0 0.0 0.0 51.5 51.0 49.3 0.0 0.0 0.0 0.0 0.0 0.0 0.0 56.5 57.1 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 59.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0
So as you can see, apart from one of the possible moves, the 1st player still retains the advantage (albeit only small for some moves.)
- Created Wednesday, June 22nd 2016 @ 00:36:19
That is not surprising. Even though pondering is valid, it does affect the opponent. Me and others already noted that playing against Jaeger requires a larger time reserve. (Probably extra if you also use java like melsonator, because of the shared garbage collect.) Like I said before, this means that calculating PI in the time of your opponent makes your bot play better. Not what we want. Nothing against melsonator of course. If pondering is valid, it should simply not affect the opponent.
- Created Wednesday, June 22nd 2016 @ 02:04:53
I think pondering should just be banned. It is largely neutral for my bot, even if that is my implementation's fault, I don't think pondering can be very positive. It is a poor use of resources because a bot is very likely to spend most of the time analyzing a position that will never happen. Allowing it without side effects to your opponent would require them to double the number of cpus available to run the matches, or halve the number of matches that run at a time. Either way, it doesn't look like it is worth it.
Although I must say that it looks like it could be difficult to enforce it.