[2005] need algorithm to solve puzzle

I posted this under Games, figuring someone there would see this as an AI challenge. Guess not.

So I'll try giving the programmers a shot at it! :)
I am attempting to create an app (in VB 2005) that will allow me to solve a mini game that is part of Bethesda’s Elder Scrolls IV: Oblivion game (Which I HIGHLY recommend).

If you’ve not played it, this is how it works.

The game consists of several rounds. The number of rounds isn’t important to the solution. Each round consists of a number of turns.

The game 'board' consists of a wheel. There are 4 quadrants. The “spokes” of the wheel form an X shape.

Each quadrant is assigned one emotion: Love, Like, Dislike or Hate. This assignment remains consistent for each character and throughout the entire game.

At the start of the round, each quadrant is assigned an additional value, a percentage of how much the quadrant is “filled”: 25%, 50%, 75% or 100%. The position of these values is different for each round and the sequence is randomly assigned.

At the start of each turn, the percentage values rotate (clockwise). That is, on the first turn, if 50% is in the top quadrant, 75% in on the right, then on the second turn, 50% is on the right, and 75% is on the bottom, etc.

Each emotion can only be selected once per round. The object of the game is to select the highest values for Love and Like, while selecting the lowest values for Dislike and Hate. The best case scenario would therefore be 100% for Love, 100% for Like, 25% for Dislike and 25% for Hate. Of course that isn’t always possible.

Now, to make things a bit more complex, once you reach a certain level, you have the option to rotate the quadrants one time per round without making a selection.

Doing all this in the game without the assistance of an outside aid (be it paper or app) is very difficult, because the score is constantly dropping as you are selecting quadrants. Since the object of the game is to score the most points possible, I pause the game after I determine the emotion quadrants and the round's initial Fill quadrants.

To manually go through one round, I do this:

1) On a piece of paper, I write a big X on top of the page
2) Below it I create 5 smaller Xs in a row
3) In the big X I indicate which emotion is in each Quadrant
4) In the far left smaller X, I indicate in each quadrant the percentage it is filled
5) For each subsequent X, I fill in the quadrant with the values rotated. (Note: the last one is the same as the first)
6) I try to select the best values for each emotion.
7) On the computer, I then select the quadrants based on the values selected; for example: R, T, X,L, B (X being a rotate without selection).

I will not be using a database to store values, so all the calculations will need to be done “on the fly”

I've been trying to come up with a way to brute-force my way to a solution for this, but am having a difficult time getting my head around it.

Please give it a go.

Thanks!

I've played the game and know it well. I actually have a pattern that will win every time, but it is probably not the absolute optimal solution. However, the problem with the sub-game is that you have to decide which quadrant to take very rapidly, or else the constant drop will undo your gain. For that reason, I feel that a fast system is superior to a technically superior system. Thus a fast system may be more optimal than an optimum solution.

My system is to first find which are the two negative and which are the two positive quadrants. I make no distinction between the different negatives and the different positives, I just need to know negatives and positives. At that point, the key is to track the smallest wedge. If the small wedge is on a negative, take it. If the small wedge is on a positive, then take the OTHER positive, no matter what it is.

Since the choices are so simple, they can be made quickly:
1) If small wedge is on negative, take it.
2) If small wedge is on positive, take other positive.


That will work for the first round, and the first choice will work for all rounds. However, after the first round, the second option may not be possible, because the other positive may already have been taken, in which case take the remaining positive (which will necessarily be the small wedge).

What this means is that some patterns will gain very little, because you will get a modest positive and the smallest possible positive, while you will always get the smallest possible negative. However, again, because the system is so simple, you can choose very fast, which means that in every game you will come out ahead, and sometimes you will come out WAY ahead (whenever the positives are across from each other and the small wedge is across from the biggest wedge).

I don't have such a good system for the higher levels when you can skip a round, since I have rarely bothered building that skill high enough. Why bother building the skill when you win every time, and do so quickly? However, the system would work just as well at every level, so the ability to skip a turn would be used when the small wedge is on a positive to get a better wedge onto the other positive....or something like that.

Thanks for the response. Taking the other positive when one is the smallest is something I didn't think of. How do you remove the selected quadrant from the selection process for turn 2 and 3? I think I'm beginning to see.

The skipped turn is advantageous for quick and highest scores, but I can see including it in the calculation doesn't pan out when you compare the complexity of the algorithm to the fact that you really have an unlimited number of rounds.

As far as solving the puzzle quickly, you don't have to. Once you know the emotional set up, and the filled quadrant set up, you can pause the game (ESC key). You have all day to do the calculations. The after you solve you un-pause them click the quads fast. Don't wait to hear the responses, just GO. Worst case, you loose a couple points getting the setup.

I never thought of pausing the game, which is probably why I opted for speed. My strategy works every time with minimal thought, but it is not the optimum strategy for every situation.

I'm not sure whether your first statement was really a question or not, but the strategy works in all situations.

However, I don't think there is any sound algorithm to optimize this game. After thinking it over a bit, I came up with this design:

First off, I number the quadrants from 0to 3 (don't use 1 to 4) starting with the top one and progressing clockwise. You can then designate the four emotions based on the quadrant they occupy. Thus, you could write a function that took the four emotions as four arguments, or you could write a function that took a single integer which was four digits long, where the thousands place held the quadrant of the ++, the hundreds place held the quadrant for the +, the tens place held the quadrant of the - and the ones place held the quadrant for the --.

The thing is that if you find ++ and read clockwise, there can only be six unique sequences of the four emotions, though those six sequences can each be rotated into four different orientations. That isn't all that important, though, becauce there can also only be six different sequences of wedges, also in four rotations. Therefore, there are only 6*6*4 possible unique patterns, which is 146 unique patterns. With that small a number, trying to calculate an actual algorithm seems like a waste of time.

Instead, you can fill an array with 146 integers, then write a function that takes the sequence of emotions read clockwise and starting with ++. So find the ++ emotion (call that 3), then if the next emotion clockwise is +, then --, then -, the argument for emotion would be 3,2,0,1. Since you always start with ++, the number will always start with 4, so you can actually drop that, and use a three digit number.

You can do the same thing with the weges, starting with the largest wedge as 4. Again, you only need a three digit number for the same reason.

So write a function like so:

Quote:

---

Public Function GetSequence(emotion as integer, reward as integer, emoStart as integer, rewardStart as integer) as integer

Dim RewardAdj = rewardStart - emoStart

If RewardAdj < 0 then
RewardAdj += 4
End If
'Look up the values here.
End Function

---

Pass in the three digit number for the emotion sequence as the first argument, the three digit number for the wedge sequence as the second argument, the starting quadrant for the emotion sequence as the third argument, and the starting quadrant for the wedge sequence as the fourth argument. The function would then rotate the emotion sequence to the top. Thus if the emotion sequence starts in the bottom quadrant (the ++ emotion is in the bottom quadrant, which is quadrant 2), then to rotate it back to the top, subtract 2. Apply the same rotation to the wedge sequence. This gets rid of the rotational symmetries such that there are only 146 combinations. These combinations can now be looked up in the array. I would be tempted to make a 3D array, with the first dimension being the difference between the wedge sequence and the emotion sequence. Unfortunately, that can't be done with sufficient efficiency, so instead I would make either a single List (Of MyStructure), or four of them:

Quote:

---

Public Structure MyStructure
Public emoSequence as Integer
Public wedgeSequence as Integer
Public rotationalOffset as Integer
Public OptimalPattern as Integer
End Structure

---

If I used four lists, I could get rid of the rotationalOffset member. Otherwise, I would just be looking through the list matching the rotationalOffset to the rewardAdj variable, and matching the two sequence arguments to the member variables. Searching a list of 146 items would take virtually no time.

So how would I fill the array? Brute force. I would loop through each of the 146 different unique patterns, then test each of the 24 different options for each sequence looking for which one has the highest total value. This could be done as a massively nested loop, or you could build the array then loop through the array finding the optimal pattern using something like this:

Code:

---

'Assumes the list MyList exists
'Assumes the array MyPatterns exists.
Public sub FillOptimals
  Dim x as integer
  Dim y as integer
  Dim n as integer

  For x = 0 to 145
  for y=0 to 23
    'This line is not quite right (see below)
    n = CInt(string.Substring(MyList(x).emoSequence,string.Substring(MyPatterns(y),1)))
    n -=2 'A significant adjustment.

'Also not quite right.
    n = n *  CInt(string.Substring(MyList(x).wedgeSequence-offset,string.Substring(MyPatterns(y),1)))
 
  Next Y
  Next x
End Sub

---

The problem with the above code is that String.Substring won't work. Instead, you would need to use MyList(x).emoSequence.ToString.Substring in place of the first string, and MyPatterns(y).Substring in place of the second string.

In the second line, it would be a bit worse. In fact, it couldn't be written in one line. You would have to un-rotate the wedge sequence, which would take a conditional.

In any event, that's pretty close. To go further I'd want to test it. The point of the whole thing is that you could fill the array by brute force, and when you got any pattern you could get the sequence of quadrants to select. It wouldn't be slow to operate, but it isn't a good idea anyways. After all, you gain skill in persuasion by the number of times you play the game, not the rate of increase. Therefore, to get the maximum skill boost, you want the game to take a long time, not a quick time. Doing something like this would give you the optimum persuasion in the minimum game time, but it would also minimize the persuasion skill increase. My strategy will give you the maximum persuasion, but not at the absolute fastest rate.

If you want me to complete the brute force filling of the list, let me know.