0

I'm writing a program for an embedded device based on the game of Darts, I'm writing code for a "Computer" player, basically I generate a series of random scores so that the computer tries to go from 501 down to zero, all is pretty straight forward till the score goes below 170, this is the number which in Darts you can checkout and finish on a double for example "40 = double 20, 16 = double 8 and so on...", I have an array "Checkoutcodes" which I can query for combinations of numbers which will allow the computer to finish the game, for example 145 = "t20t15d20" which translates to (3x20, 3x15, 2x20) which is 145 and game over. Now obviously in the real world it's not possible to get out every time so I have wrote code to mimic an attempt to checkout.

These numbers represent the order on a dart board in a circular pattern, note the 5 is beside the 20 20,1,18,4,13,6,10,15,2,17,3,19,7,16,8,11,14,9,12,5

In order to mimic an attempt I randomly select the number needed or a number to the left or right, so for 145, and for the first part "t20", The computer could potentially hit a 1,20,5 or (3x1),(3x20),(3x5). Now if it selects a number other than "t20" then I'd have to retrieve a new checkout code, so if a (3x5) was hit, the score remaining would be 130 and the new checkout code would be "t20t20d5". This would repeat until 3 darts were thrown and at the end my code would evaluate the total score remaining against what it expected to be remaining. If they don't equal then I loop back and try again, this works ok when tested on a PC but when loaded onto an embedded device it's sluggishly slow. Below further explains the flow of how my code works.

    //Successful mimic
    145 - "t20t15d20" - (3x20) hit
    85  - "t19d14" - (1x7) hit
    78  - "t18d12" - (3x4) hit
    Outcome is 66, expected was 66 so (3x20),(1x7),(3x4) is a valid combination

    //Unsuccessful mimic
    145 - "t20t15d20" - (1x5) hit
    140  - "t20t20d10" - (3x20) hit
    80  - "t20d10" - (1x1) hit
Outcome is 79, expected was 66 so (1x5),(3x20),(1x1) is not a valid combination, so code will loop till a valid combination is found.

Surely there must be a smarter way of figuring out valid mimic combinations quickly, I think at this point I have tunnel vision and hope that a fresh set of eyes may spot something I haven't

123 456 789 0
  • 10,565
  • 4
  • 43
  • 72
chillydk147
  • 385
  • 1
  • 10
  • Why do you need to know *all* combinations? You really only need to know one that will work. Is the number a multiple of three and 60 or less? Throw for that triple. If less than 60 and not a multiple of 3, how about 2? Bigger than 60? Throw for triple 20 and go back to step one. Double-in/out would complicate things, but not too much. This "algorithm" would need work, but again, I don't think you need to check every single permutation. Selecting larger spots on the board over smaller targets is also something I would do to increase my chances. – Steve Jul 15 '14 at 21:40
  • How much memory do you have in the device? Cannot you store a map from (sum of points) to a list of combinations? – Tomas Grosup Jul 15 '14 at 21:43
  • I'm working off a development board at the moment Fez Raptor, I need only 1 random combination of numbers to achieve the effect of a mimic, I think a map would be too large – chillydk147 Jul 15 '14 at 21:45
  • @Steve "Selecting larger spots on the board over smaller targets is also something I would do to increase my chances", what do you mean by this? – chillydk147 Jul 15 '14 at 21:46
  • Well, if I had to score 20 points, I would throw for a single 20 over a double 10, since the target is physically larger and I would be more likely to hit what I want and not bust. I would assume your computer AI would have some noise built in (otherwise it would always win) and may want to try to do the same. – Steve Jul 15 '14 at 21:48
  • @Steve - unfortunetley you have to finish on a double, it works really well on a PC, very realistic but needs to be more refined for embedded device – chillydk147 Jul 15 '14 at 21:51
  • Try looking at [this SO question](http://stackoverflow.com/questions/4632322/finding-all-possible-combinations-of-numbers-to-reach-a-given-sum) – Icemanind Jul 15 '14 at 22:13

0 Answers0