I find another approach to solve the test set. I would call it "Playing greedily by *picking even moves* and starting in a better place", It would win ~90% of games, which is enough to pass test set 3. The approach is similar to "picking non-randomly", but with some improvement. Instead of picking the least (x, y) when breaking ties, pick a rope which can be crossed even times in the future. For example, if you pick (3, 5) in an empty board, then this rope can be crossed at most 6 times in the future (and probably it will be 6 times as both you and opponent are playing greedily). This can be calculated by how many trees are left in the east and west in O(1) time. This method assures most of your moves will offer same points for you and opponent in the future. As opponent is playing randomly, they have a ~50% change to pick a odd move, which gives you 1 point advantage. This method alone will raise the win percentage to ~65%, which is enough for test set1. With a better starting place, such as (1, 3), the win percentage is raised to ~90%, which is enough to pass test set 3.
-- -- You received this message because you are subscribed to the Google Groups Code Jam group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at https://groups.google.com/d/forum/google-code?hl=en --- You received this message because you are subscribed to the Google Groups "Google Code Jam" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To view this discussion on the web visit https://groups.google.com/d/msgid/google-code/bce9e919-937f-49d6-98bb-48d09e1190a8n%40googlegroups.com.
