Non-solve moves in Caravan Game

[churd]

I came across this situation today, when goofing around with the game.

The person I was trying to beat had a score of 89. After a little bit of practice, I came to the pathing he had used to get that score of 89. It was

_, SW, SE, SE, NE, NE, |, |, |

I was then able to beat it, posting a score of 84, with the following

NW, _, SW, SE, SE, NE, NE, |, |, |

The NW piece in the above string was not placed on the path from start to finish. It was thrown away, placed somewhere else in the puzzle. It was used as a way to reduce the cost of the pieces that would then double in cost. I still haven't figured out a true algorithm for this, but I think the cost savings is = ( (number of doubled pieces) + 2(number of tripled pieces) + 3(number of quadrupled pieces) )

[random user]

And this is why I don't play the caravan game :P

(good info, thanks!)

[robin74]

Using a piece to throw away, just to reduce the total cost, is something which comes up in more than a half of all cases, and the more complex the game becomes, the more often it will be beneficial. Often I would use more than one such piece to reduce the cost several times.

[ShuShu62]

What Robin Said...

I am in a game now where two folks are pantsing me. Its good to know the caravan game is still fun when you lose. I still beat the road graders a couple times a day. I find this MUCH more enjoyable than the old caravan game.

[robin74]

My most enjoyable game, caravan-wise, was in a game with another player who could actually beat me legitimately. That created some challenge to try and actually optimise, or else I would expect him to come and do better. Little tricks like understanding in which order you need to put the tiles or that sometimes it's cheaper to waste a tile completely helped a lot.

[churd]

Alright, I can accept that I am late to the party on this topic. It was a great revelation to me, but I guess people already knew about it.

With that in mind, let me ask you this: does the cost saving of a throw-away piece only apply on puzzle solutions with <10 moves? It seems to me like it might. I think it has something to do with the 1 cost alternation between the two most populous pieces, which I outlined for myself here.

P.S. Isn't it great that we can actually talk about Caravan Game strategy? That's possible when the thing actually works correctly. Yay!

[robin74]

My guess would be - no.
Consider the puzzle in which the optimal path uses 4 types of tiles, 3 pieces of each. I'm quite sure you can do better by wasting one of the remaining two types than by sticking to the four required. I can easily get down to 138 in this case, and I don't think you can do it without wasting some of the pieces. And I'm not even sure it's actually the best score in this situation.
Edit - and it's not, I found a 117 solution for this situation.

[churd]

Man, this really has me working too hard. I can clearly see that wasting pieces is the right thing to do, but beyond that, it gets really complicated. For the sake of simplicity, I'm going to make it so that _ and | are the pieces that aren't involved in the solution, and the [NW, NE, SW, SE] are the pieces that are repeated 3x.

No waste is clearly wrong.
NW, NW, NW, NE, NE, NE, SW, SW, SW, SE, SE, SE =
10, 20, 40, 7, 14, 28, 4, 8, 16, 1, 2, 4 =
10x7, 7x7, 4x7, 1x7=
154

However, the amount of waste is something that has me contemplating. Because wasting 1 of each piece is actually not optimal either. There's something in the way that the waste pieces interact with the alternating 1 cost pieces that I can't exactly figure out.

_, |, NW, NW, NW, NE, NE, NE, SW, SE, SW, SE, SW, SE =
10, 9, 8x7, 5x7, 2, 1, 3, 1, 5, 1 =
123

_, |, |, NW, NW, NW, NE, NE, NE, SW, SE, SW, SE, SW, SE =
10, 9, 18, 7, 14, 28, 4, 8, 16, 1, 1, 1, 1, 1, 1 =
10, 9x3, 7x7, 4x7, 1, 1, 1, 1, 1, 1 =
120

Wasting pieces to get to the alternating 1 situation is optimal in this case. I still can't figure out if you got 117 some other way, or whether that was part of the puzzle you're seeing (rather than the abstract)

[ShuShu62]

Waste is beneficial based on the pieces used after the waste and increases incrementally.

If you are going to waste a piece, waste it early.

You will save 1 on every piece you use once fter that
you will save an additional 2 you use twice after that
you will save and additional 4 ....

so for your 8 piece map that uses only 4 pieces...

you will have 4 1's saved per wasted piece and 4 2's saved.

This means you should waste the 10 and the 9 piece first as the cost of 19 is offset by the savings of 24.

I have never wasted pieces as first moves before. Lesson learned.

even wasting a second move early (cost 20) pays for itself very quickly if you need 13 or more moves (6* (1+2) + 4).

Road graders be ware... hehehe

[robin74]

I still can't figure out if you got 117 some other way, or whether that was part of the puzzle you're seeing (rather than the abstract)

Here you go. I'm not sure how that fits into your algorithm, but yes, essentially the key is to get to alternating 1 - but once I do, I skip the remaining tiles and come back for them at the end:
_, _, |, |, NW, NW, NW, NE, NE (twice only), SW, SE, SW, SE, SW, SE, NE (remaining third)
10, 20, 8, 16, 6, 12, 24, 3, 6, 1, 1, 1, 1, 1, 1, 6.

I have never wasted pieces as first moves before. Lesson learned.

Neither have I. I actually improved my caravan skill quite a lot due to this discussion

[churd]

Here you go. I'm not sure how that fits into your algorithm, but yes, essentially the key is to get to alternating 1 - but once I do, I skip the remaining tiles and come back for them at the end:
_, _, |, |, NW, NW, NW, NE, NE (twice only), SW, SE, SW, SE, SW, SE, NE (remaining third)
10, 20, 8, 16, 6, 12, 24, 3, 6, 1, 1, 1, 1, 1, 1, 6.

Neither have I. I actually improved my caravan skill quite a lot due to this discussion

Man, that is absolutely disgusting. In a good way. You're right that there's no way to create an algorithm for wrap-around, end-of-string placement. Or at least, none that I know of at a "college math minor" level. I'm sure someone at the doctorate level could figure it out... as soon as we find that person. As it is, you'd just have to experiment with it and tweak it to see situations where that applies. But that's what makes it fun.

And yes, I've learned a lot from this too.

[ShuShu62]

I think we can codify it...

to get to alternating 1's, you need to spend 9 tiles.

Step 1 --- identify the alternating 1 tiles.
Step 2 --- identify the triple tile
step 3 --- spend all double tiles in pairs
step 4 --- spend triple tile
step 5 --- alternate 1 tiles


If you need two triple tiles, it is better to place a second dead tile and place the second triple tile as the last piece

[ShuShu62]

Neil --- Is this the discussion you were refferring to... because it hs been really unfair of you to be using it against me.

Oh... and I promise to be better competition after my story is finished and I am back from vacation.

[Monqi]

http://forums.2kgames.com/showthread...van-game-cheat

no, it was this one, just a quick discussion before the civbucks question hijacked it!

[ShuShu62]

Ahhhhh.... Monqi, I am glad to see your in game persona is as formidable as your forum person would lead one to believe.

[Monqi]

I'm at a bit of a loss in our current game, though. Any suggestions?

[Monqi]

preferably ones that don't involve attacking baby guild + nazgul

[ShuShu62]

wellllll... now that you have gone public, just post the game here and I am sure you will get many recruits.

Not sure where that game is headed. It was a sleepy farm game. But the kids recruited more and more fire power into it, and then stopped playing so it is in flux at the moment. It is such Chaos that Treebeard is there (unaligned when last I looked, but in our chat). Weather Goddess is using it to recruit the Nazgul Hunter. The Weather Goddess has been collecting hammers and Ursa Minor threatened to start collecting beakers (but couldn't make good on that threat). One baby has meritocracied out and the other two plus myself are on the verge of meritocarcying out today.

Maybe just wait it out.

[LauriH]

ShuShu, that algorithm can usually be improved by 1 stone. It goes as follows:
Step 1 --- identify the alternating 1 tiles.
Step 2 --- identify the triple tile
step 3 --- spend all double tiles in pairs
step 4 --- spend two triple tiles
step 5 --- spend one of each of the remaining tiles
step 6 --- spend third triple tile
step 7 --- spend the tile costing 1
step 8 --- alternate 1 tiles

With your process, if the amounts of different tiles is (2, 2, 2, 2, 3, 3), you use
10+20+8+16+6+12+4+8+16+1+1+1+1+1+1=106 stones,
while the improved process spends
10+20+8+16+6+12+4+8+2+1+14+1+1+1+1=105 stones.

[ShuShu62]

ShuShu, that algorithm can usually be improved by 1 stone. It goes as follows:
Step 1 --- identify the alternating 1 tiles.
Step 2 --- identify the triple tile
step 3 --- spend all double tiles in pairs
step 4 --- spend two triple tiles
step 5 --- spend one of each of the remaining tiles
step 6 --- spend third triple tile
step 7 --- spend the tile costing 1
step 8 --- alternate 1 tiles

With your process, if the amounts of different tiles is (2, 2, 2, 2, 3, 3), you use
10+20+8+16+6+12+4+8+16+1+1+1+1+1+1=106 stones,
while the improved process spends
10+20+8+16+6+12+4+8+2+1+14+1+1+1+1=105 stones.

Adding a little exposition... I added what the single tile does when you jump it forward. It is also counter intuitive as it means you should use the tile that you need fewer of... first.

10+20+8+16+6+12+4+8+2+1+14+1+1+1+1=105 stones
x9xx8x7xx6xx5xx4x3xx2 4 3 2 1 2 1 2 1

So now I know why you keep beating me by 1
Thankyou for sharing, this.


Side note. This technique also comes into play if you need a second tile 3 times... defer THAT tiles usage until after all the 1's have been played.

Lauri has laid out a detailed analysis along these lines... here : http://www.facebook.com/groups/33959...3222304381216/

[ShuShu62]

So now I know why you keep beating me by 1

That statement just does not reflect just how magnanimous Lauri's post was. He literally has been beating me by one in the games I have played against him. I was able to beat him last night as a direct result of what he posted here. Furthermore, I know I am not the only competitive caravaner who was ignorrant of the Lauri Technique. They two will have a shot at beating him now.

Forums are always full of pesimists talking about how cheaters will always do anything to win and ultimately ruin any game.

The forums rarely talk about people like Lauri who care so much about the competition yet so little about winning that he shared a secret that gave him a powerful competitive advantage, just to level the playing field, despite it meaning he would win less often.

I salute you!