Tantrix Tournament Reports

[Pellepen]

I think some of us are participating in the Roll Out Competition:
http://www.tantrix.com/english/TantrixRollout.html

But is there anyone who is working on a program so we will have a winner in this competition?

Perhaps there is a lot of people working on it now?

Please let us know if there are some programmers out there somewhere who are capable of making a "roll out" program.

[fafa]

i was a bit confused by this competition, because i thought the aim was to come up with a good, efficient roll out program, but as we aren't allowed to use any of the existing programs, it seems like a huge waste of time to start building something from the ground up, when dave (or anyone using the goodbot program as a basis) could much more easily do so.

So i think this should either be about guessing, and then, at a set deadline, you could just let goodbot play that particular game (from the given starting point) say, 1000 times. (which is the most basic way of determining the odds). Or it's about making a good, fast (because playing a game 1000 times probably isn't the most efficient way) roll-out program, but then i think we should be able to use goodbot as a basis.

But i'm very curious too if anyone is working on it.

[blick]

I have been thinking about this problem, and of course, my first idea was goodbot as well. But, goodbot uses the same algorythm, so in every game, only luck would make difference, not the first move, or sg. But i don't have a better idea - yet.

[galca]

i think there is a conceptual difference between robot and rollout:
in rollout the tile sequence is known and this knowledge can be (and should be) used when the best move is chosen. robot program, however, decides on the best move over all possible tile sequences. These two "best moves" can be different: for example, the move which is best in the given position when we know the tile sequence can be too risky in general.
I am not trying to say that using existing robot is not an advantage (it is), but maybe it is not such a big advantage: there are a lot more things that a good rollout program can do to improve its decisions which i assume don't exist in the lobby robots.
As for the people working or planning to work on rollout program: i had some thoughts of turning my endgame program (which is used so far only by me and a couple of other players - AC's in fact - because of it's huge cheating potential) into rollout program, but i am not sure i'll have enough time for it in the nearest future.

[Zormac]

[galca]

[Zormac]

[galca]

[Mikem]

For me, the whole point of a roll out is to analyse something which varies. If the sequence of tiles was fixed as suggested then this would be like solving a puzzle...certainly still difficult but not what Tantrix is about.

Perhaps it is unfortunate that applet gives the ability to control the tile sequence, with the confusion added to by the "Challenge Room".
But in theory Tantrix is like backgammon..ie there is no control over what the dice will say next, or in what order the tiles will come out.

[galca]

If i understand you, Mike, the goal of rollout is not to find probability to win but to find the move with maximal probability to win? (and submit this number?) (the difference is explained above in my previous post)

[Mikem]

Well, if it were possible I would play the game (ie roll out) the game from the position one million times using the two best players in the world. The question is what % would each player win. This is the type of decision you need to be evaluating constantly when a doubling cube is involved...as in the tournament we played last weekend http://www.tantrix.com/english/tournaments/Tantrix2008Vauban.html

[Zormac]

[fafa]

i agree with the non-fixed sequence here. Like Zormac said (as far as i can follow all this mathematical talk) if the sequence would be known, hypothetically (as mike pointed out, it would be quite a difficult puzzle) the chances of red winning would indeed be 100 or 0% (depending on whether or not red can find a series of moves which blue cannot counter.)

and i'm not sure i can follow the logic to get to that percentage of 95% in your example earlier, because if you would compute blue's chances of winning in the same way (if red plays A, he has 10% chance of winning, if red plays B, 50%) blue wins (10+90/2) 55% of the times, so the odds would be 95-55 so if move A gives red a 90% chance of winning, that is the optimal move, and should therefor always be played, countered by blue's optimal move etc.

the point made about bot making the same mistake every time is a valid one though, but then it's a matter of improving bot, which is a good idea then anyway, so we have a 'bestbot' to do the rollout with

And apparently (as mike makes the comparison with a cube-game) the aim is to win, and not to maximise margin. Which would then indeed (if bot does go for maximum margin, at risk of losing) require some modification of bot.

[galca]

[Mikem]

Yes sorry, this subject sprang from the idea of applying doubliing cube theory to Tantrix and I should have made it more clear that we do mean that both players must maximise their chance to win, as in in 'cube' games margins are not taken into account.

[Retro]

Obviously we need a robot to run through a sample of the 15! permutations of draw sequences; as well as Backgammon I believe this technique is also used in televised poker.
Another question is, how accurate does the robot's win% prediction need to be? We are allowed to guess in units of 0.1%, but if rollouts of 500 or 1000 samples were done multiple times we would get a different answer every time!

If Galca's program can do 1,000 runs in a day, this would estimate a win% to within a range of 5%* (with 90% confidence), which doesn't seem that good, i.e. if you run the program again with a different set of 1000 tile sequences, you would probably get a different answer (and if you get the same it would be coincidence).

To be 90% sure a rollout program has the 'true' win% to within 1% may require 27,000 runs** - to get it within 0.1% requires 2,700,000! Is this possible?

On another slightly cynical point, surely whoever develops the accepted rollout program has a distinct advantage in the competition, by being able to see in advance what result to expect?

---
Appendix:
I'm sure some select people may want to know where those figures came from, so here's my working:
Suppose the 'true' winning proportion is p. Then, on a rollout of n trials, the observed success rate is P, where P = (number of wins)/n.
nP has a binomial distribution with parameters (n,p), but as n will be very large we approximate nP to the normal distribution with mean np and variance npq, thus P~N(p,pq/n)
Calculations:
(*) If n=1000 and p is about 0.5, then the standard error in P is sqrt(0.25/1000)=0.0158 (1.58%). From statistical tables we can see the size of the equitailed 90% confidence interval is 3.29 this amount [Phi(.95)-Phi(.05)], or 5.2%.
(**) If we want to be 90% sure our guess P is within x(=0.01), then we must run enough trials such that the standard error is only x/3.29. We already know the standard error can be up to sqrt(0.25/n), so we can solve algebraically to find x=0.01 => n=27056, and x=0.001 => n=2.7e+6

[Metallor]

[galca]

Thanks Ben for the confidence calculations!
Even with 1 min per the whole game (which is i think is not so much for a good robot) it will take about a month

and, since this subject was opened and i found myself looking at it, here is one of the possible endgame positions that can happen :



How much time will it take you to find 10 tiles win for Mike?

[lytnin]

My solution has been PM'd to galca. So that others will also have a go.

I think this may even end up an 11 or 12 tile win.

[galca]

this was fast! (and simpler than my solution)
but it is only 10 (and you already know why so I am removing it from this post )

[lytnin]

Cool

[galca]

ok, this one is quite easy, but when this game was played (L8 of WTC 2006) Cat didn't spot her killer move (can imagine Matt's relief when another move was played: he wouldn't probably go to L4 otherwise ...)

well i hope it was so long time ago that I will be forgiven for publishing it here



and the goal is 10 tiles win again

[lytnin]

PM'ing solution

[Zormac]

[lytnin]

Z , the puzzles haven't been removed, just my answer and response to what the final score could/would have been, so that others will get to have a look and put some thought in as well. I'm sure Galca will publish them in a short time.