I think choosing a strategy completely at random is optimal.
That was my thought also.
In the Kaiji anime they go on about psychological aspects of the game, and they use one specific rule to enforce this: you must look at the card you play in a turn before playing it, and players play their cards in sequence rather than simultaneously, with the player to play first swapping in each subsequent turn. The idea is that if they are playing first a player may give away a "tell" if they play a game-ending card (Emperor or Slave), and then the other player may make use of this. Of course, in the anime there is also cheating involved, since it is Kaiji after all, but we're setting that aside for the math problem.
In the purest sense, though, I do agree that the optimal strategy is random choice. That's why I said this:
The real math problem is the optimal betting strategy.
You haven't solved that one yet ^_~
Nonetheless, the human aspect does raise at least this question - how would one best implement the random choice, given human limitations?
Can Kaiji legally wager over 30mm on the first bet (or any other bet)? If 30mm is negative infinity utility, than any number greater than 30mm is equal to 30mm for loss (but the gain continues increasing). If Kaiji has already had, say, 20mm drilled, can Kaiji wager a distance that exceeds 10mm?
The maximum extension of the drill is 45mm, which limits your bets and hence you're limited to a finite gain in utility. By assumption, even the maximum amount of money you could gain from this match would not be worth as much as your eardrum - that's why I expressed it as negative infinity utility, since that's the simplest way to put it.
In the purest sense, though, I do agree that the optimal strategy is random choice. That's why I said this:
The real math problem is the optimal betting strategy.
Well the betting strategy could be integrally tied to the play strategy; a certain play strategy that always wins would imply reduced risk and higher bets. Confirming that random choice was optimal for play was necessary to moving forward with the betting strategy.
Nonetheless, the human aspect does raise at least this question - how would one best implement the random choice, given human limitations?
That is a pretty great question. If you have a watch, this would be useful for making decisions. For example, divide the face into 5 sections and choose your strategy based on which section the second hand is in just after you pick up your hand. Anything that changes in the environment might be similarly used to make arbitrary decisions. Arguing the "randomness" of any conscious choice or algorithm might become a bit too philosophical, so I'll simply say you could feasibly come up with a pseudo-random decision making process that is not based on your opponent or your hand. Hell if the drill is always running, you might even be able to use some kind of acoustic disturbance pattern to decide a number.
By assumption, even the maximum amount of money you could gain from this match would not be worth as much as your eardrum
If you are at 29mm and you must play another round, then you should wager 45-29=16mm, not 1mm. The negative infinite loss is the same with either bet if you lose the round, but the gain is quite different. Once you are at 29mm, you should bet 16mm every time until you lose your eardrum, given the negative infinity clause.
I would question whether the further distance would be "worse" damage, and if so, should the negative infinite utility be modified from 30mm? If drilling from 30mm to 45mm really doesn't do any more damage functionally, then we can leave the standing assumption.
That is a pretty great question. If you have a watch, this would be useful for making decisions. For example, divide the face into 5 sections and choose your strategy based on which section the second hand is in just after you pick up your hand.
Such an approach could be predicted by your opponent. Since they also have access to the time, they can exactly predict your strategy. Granted, they would have to know that you were doing this, but they would at the very least see you looking at your watch. It seems to me that the best source of randomness you have available to you is simply shuffling the cards in your hand. For example, you could either shuffle the cards once and play them in order, or shuffle the cards every turn in order to randomly pick one from your hand.
If you are at 29mm and you must play another round, then you should wager 45-29=16mm, not 1mm. The loss is the same either way, the gain is different.
Technically speaking, in the anime it's said that 45mm could result in death, but for the sake of the problem it doesn't really matter, because you can 100% avoid ending up in a situation where you are at 29mm and must keep playing. For example, you could bet 2mm each round for all 12 rounds, and if you lost every round the drill would still only be at 24mm.
Kaiji will win the round with 100,000 moneys with p = 4/5 and will "win" the round with 1mm with p = 1/5 (and these are mutually exclusive). This will happen for 3 rounds, then Kaiji changes to Slave holder. Kaiji will then win the round with 500,000 moneys with p = 1/5 and will "win" the round with 1mm with p = 4/5 (also mutually exclusive cases). This will happen for 3 rounds (6 have elapsed total). Kaiji will switch back to King holder for 3 more rounds (9 total), and back again to Slave holder for the final 3 rounds.
To start thinking about the expectations, I am going to use complex numbers to separate moneys from mm penetration. Real numbers will represent moneys; imaginary numbers will represent total mm penetration. I am also going to begin considering a minimum bet of 1mm is always chosen. Since Kaiji risks a maximum loss of 12mm in the worst possible case, he cannot possibly lose his eardrums (which I think terminates the game?) nor lose his life (which terminates the game).
Assuming I didn't screw up my decimal places, he can expect 1.08 million moneys and 6 mm penetration with minimum bet and starting as King holder. Note that the expectations are additive, which carry the property of being commutative.
If we swap all the order of the expectation calculation such that the King expectations are replaced with Slave expectations and vice versa, the result will be the same as if we had not swapped them. This holds so long as all 12 rounds are guaranteed to be played, so that both special cards are held for 6 rounds each: E(payout | always minimum bet, starts as Slave holder, random strategy) = 1080000 + 6i.
Let's consider that Kaiji wants to get as close to 30mm without going over, and Kaiji wants to try to spread those mm evenly across the board! 30mm is fail, but 29mm is not. Kaiji will bet 2mm on all but 5 bets, and 5 bets will be placed at 3mm, for 29mm total bet. The higher bets will be placed as King holder only as an experiment. Since all 12 rounds will be played, it doesn't matter whether Kaiji begins as Slave holder or King holder (commutative property of addition).
In this case, Kaiji can expect 2.56 million moneys and 13 mm penetration.
This is obviously becoming a pattern. We want one bid strategy as Slave holder and one bid strategy as King holder. Since expectations are commutative, it cannot matter what order the bids are placed so long as each classification of bid is played in the correct scenario (King bets as King holder, Slave bets as Slave holder).
Let us bid BS mm as Slave holder and BK mm as King holder. We must first guarantee all 12 rounds can be played for this simpler math, so 6*BS + 6*BK <= 29mm. This is constraint 1. The minimum bet for any round is 1mm, so constraints 2 and 3 are B<sub>S >= 1, BK >= 1.
We want to maximize the real value of the expectation over BK and BS while adhering to all constraints; the real value of the expectation represents the objective function to be maximized. Constraint 1 guarantees that Im[Expectation] <= 29mm, and it also guarantees (even in the worst case), that Kaiji really loses nothing, thus we don't really care about the imaginary value of the objective function.
Re[Expectation] = B<sub>K * 480000 + BS * 600000
Clearly BS is worth more payout per mm, so maximizing BS while adhering to all constraints will maximize the objective function. To do this, BK must be minimized (due to constraint 1), so BK = 1 (the minimum possible due to constraint 3).
Assuming you find a way to divvy out that fractional part over Slave bets: Re[Expectation] = 1*480000 + 3.8333...*600000 = 2.78 million
If I did all of this correctly, 2.78 million is the most Kaiji could earn without putting an eardrum at any actual risk.
Next chapter: putting the eardrum and/or life at risk. This one gets complicated because all 12 rounds might not be played; it also might make a difference whether King holder or Slave holder is chosen first. In that case, constraint 1 would be dropped, and be replaced with Im[Expectation] < 30mm.
Does the game end necessarily when the eardrum is pierced?
This is obviously becoming a pattern. We want one bid strategy as Slave holder and one bid strategy as King holder. Since expectations are commutative, it cannot matter what order the bids are placed so long as each classification of bid is played in the correct scenario (King bets as King holder, Slave bets as Slave holder).
Wrong. You've missed one critical property of this game - bets are not necessarily independent of one another. For example, consider this scenario: It's the second last round, and the drill is at 27mm. If you win, you will get to the last round at 27mm, and so you clearly will bet 2mm on the last round. If you lose, you're at 28mm, and so you will obviously bet 1mm on the last round.
If I did all of this correctly, 2.78 million is the most Kaiji could earn without putting an eardrum at any actual risk.
Consequently, this is also wrong. Also, even if your calculations were correct, that value wouldn't be the most he could earn, but rather the maximum expected value across all strategies.
Also, even if your calculations were correct, that value wouldn't be the most he could earn, but rather the maximum expected value across all strategies.
Err I meant to say "maximum Kaiji could expect", but "maximum expected" is more clear.
Wrong. You've missed one critical property of this game - bets are not necessarily independent of one another. For example, consider this scenario: It's the second last round, and the drill is at 27mm. If you win, you will get to the last round at 27mm, and so you clearly will bet 2mm on the last round. If you lose, you're at 28mm, and so you will obviously bet 1mm on the last round.
I don't see how this is an issue. With the betting schedule I arranged, the drill will go at most 29mm if Kaiji lost every single round. That was constraint 1. Constraint 1 maintains bets are not independent of each other. It, however, does not matter what order in which the bets are placed, so long as King bets are placed while being King holder, Slave bets are placed while being Slave holder, and so long as constraint 1 is maintained. This is explained pretty verbosely in my description of the mathematics. Perhaps I am misunderstanding your issue?
If your example addresses an issue of rounding, where Kaiji might end on 28mm instead of 29mm because 29 does not divide evenly, I will assure you that the final expected calculation I presented does not account for rounding as was mentioned quite clearly (3.833 must be divided out in some clever way). However, you can only have a worse expectation if you round that wager, because you must round down; to round up breaks constraint 1 allowing more than 29mm to be wagered.
No, it's not an issue of rounding. My point is that if you win, the drill does not advance, which means you can use that extra distance on subsequent bets. For example, if you bet 18mm every round and won every time, the drill would still finish at 0mm, but your total bets would be 18*12=216mm. Hence your constraint
6*BS + 6*BK <= 29mm</p>
is completely wrong - the amount you can bet is in fact dependent on the outcomes of previous rounds. Consequently, the optimal betting strategy could bet different amounts on the same round, depending on the outcome of previous rounds.
No, it's not an issue of rounding. My point is that if you win, the drill does not advance, which means you can use that extra distance on subsequent bets.
I understand what you mean now. Yes, I made an assumption, expressly described, to simplify the math. The betting strategy I calculated cannot conceivably put Kaiji's in danger no matter what occurs.
Constraint 1 guarantees that Im[Expectation] <= 29mm, and it also guarantees (even in the worst case), that Kaiji really loses nothing,</p>
You are correct in that there are other strategies that can do better which probably do not put Kaiji in danger. Such strategies would maximize Im[Expectation] < 30, which I haven't touched ... yet:
Next chapter: putting the eardrum and/or life at risk. This one gets complicated because all 12 rounds might not be played; it also might make a difference whether King holder or Slave holder is chosen first. In that case, constraint 1 would be dropped, and be replaced with Im[Expectation] < 30mm.
No, you still don't get it, so I'll try to give you a simplified example. Let's say you have to play 2 rounds, and the drill will hit your eardrum at 3mm. Clearly, you can lose at most 2mm and still be safe.
By your reasoning, the best strategy would be to bet 1mm on the first and second rounds.
However, consider the following strategy: Bet 1mm on the first round. If you win the first round, bet 2mm on the second round, otherwise bet 1mm on the second round. Like the previous strategy, this one can lose at most 2mm and hence is perfectly safe. However, it has a higher expected gain, and hence it is better!
However, you are proposing "changing the strategy" on a round by round basis. I am speaking of a single strategy, chosen at the start, and employed through the entirety of the game.
When I say that I guarantee no harm, I mean that, even if Kaiji loses every single round, the Strategy proposed still prevents harm.
What you describe is changing strategies as the game goes on, and is predicated on "but what if Kaiji doesn't lose every single round?" Such a strategy obviously does not account for the possibility of losing every round; it is in another class. So let me discuss this class of strategy:
When I offer to calculate a Strategy that maximizes Im[Expectation] < 30, what I am saying is that this Strategy would expect (just under) 30mm by game end. The changing strategy you talk about forces (just under) 30mm by game end. In effect, the strategy you are talking about is part of the strategy which maximizes Re[Expectation] moneys and maximizes Im[Expectation] < 30.
However, you are proposing "changing the strategy" on a round by round basis. I am speaking of a single strategy, chosen at the start, and employed through the entirety of the game.
That's rather a poor definition of strategy - by any reasonable definition you can make different moves depending on factors other than yourself as part of the same strategy. In any case, regardless of what you call a "strategy", you were wrong when you said this:
If I did all of this correctly, 2.78 million is the most Kaiji could earn without putting an eardrum at any actual risk.
Kaiji can have an expected gain of far more than 2.78 million - my math says it's around 8 million - without any risk whatsoever of losing his eardrum.
What you describe is changing strategies as the game goes on, and is predicated on "but what if Kaiji doesn't lose every single round?" Such a strategy does not account for the possibility of losing every round.
It does. As soon as you start losing, you can switch to 1mm bets and finish safely.
In your own words,
Next chapter: putting the eardrum and/or life at risk. This one gets complicated because all 12 rounds might not be played; it also might make a difference whether King holder or Slave holder is chosen first. In that case, constraint 1 would be dropped, and be replaced with Im[Expectation] < 30mm.
Indeed, such an approach would put your eardrum/life at risk, and hence is clearly not optimal.
When I offer to calculate a Strategy that maximizes Im[Expectation] < 30, what I am saying is that this Strategy would expect (just under) 30mm by game end. The changing strategy you talk about forces (just under) 30mm by game end. In effect, the strategy you are talking about is part of the strategy which maximizes Re[Expectation] moneys and maximizes Im[Expectation] < 30.
There is a difference between forcing less than 30mm, and having an expectation of less than 30mm. The former is 100% safe, while the latter could possibly hit 30mm in the wrong circumstances; you yourself said "putting the eardrum and/or life at risk".
However, as I said before, by my calculations, with the correct approach you should expect a gain of ~8 million with no risk whatsoever.
I've got a algorithm/statistics/math problem I was experimenting with for a while. This was almost two years ago. I already have a reasonably good solution to the smaller problem. The larger problem, however, is still needing improvement. Here's an instance of the simpler problem.
So you have a 3x3 matrix. It contains random integers. Those integers can be duplicated, in case that matters. For example:
07|08|12 16|13|11 07|17|13
You want to pick one value from each row, and one value from each column. You cannot pick any specific number twice. Your goal is to pick the highest possible total set value.
The brute force method here would be to try every possible combination of valid picks and find the one with the highest total value. There is a significantly faster (in terms of how fast my computer gets an answer) solution to this problem.
The value is going to be equal to the sum of the total minus the three lowest values, unless those values are in a single row or column, in which case you subtract the two lowest values and the fourth lowest value. This works really well for me, and wasn't a pain to code once I realized it.
- - - - -
The larger problem involves solving the slightly more complex 4x4 matrix. The faster solution I used for the 3x3 doesn't work anymore, because you are discarding just as many values as you are including (8 or each). So-far, I havn't found a faster method than brute forcing. There are methods that seemed like they should be faster, like checking the sum of each valid template that can exist and comparing those (reduces the complexity by about 1/2) but the extra operations ended up being more computationally expensive by about 10% in the specific language and method I was using at the time. It could have just been my own execution that failed. Since you can rotate the matrix freely, you might be able to manipulate it down to only 1/16th the total problem size in theory... but I havn't quite solved that.
Obviously this is more "algorithm & programming" than math, but I found it interesting. It's no-longer something I need to solve for any reason, but I'm still curious. A fast general solution to the nxn sized matrix would be even better.
You want to pick one value from each row, and one value from each column. You cannot pick any specific number twice. Your goal is to pick the highest possible total set value.
So if you have a 3x3 matrix, you are picking 6 total numbers and summing them. I see why you would want to find the 3 smallest ones in that case, and I also see why that is harder than simply choosing the 3 smallest values from the entire data (because you cannot ignore the positions).
Generally, if you have an NxN matrix, you want to choose the 2N elements which sum to the highest value, while discarding N^2-2N elements. The N=2 case is degenerate, because you will have chosen all 4 numbers. It also turns out that the parabola formed by N^2-2N hits its extrema at N=2, so all N greater than 2 will follow the same pattern of throw-aways increasing faster than keepers that is seen as you move from N=3 to N=4.
Obviously this is more "algorithm & programming" than math, but I found it interesting.
If you are talking "real time speed" of your computer's ability to process as the metric, I can almost guarantee you there is some nice way to do this with linear algebra that will finish super fast if you push it through a GPU; in fact some kind of convolution over the matrix would probably do the trick very quickly indeed. If you are talking algorithmic complexity, that is a bit more interesting.
This kind of problem reminds me of Sudoku. Have you looked into the algorithms to solve Sudoku at all?
I have not looked at any sort of Sudoku problems before. And I have pondered writing a CUDA program to solve a lot of these very quickly, but my home computer is using an ATI card so I would have to use whatever their GP_GPU system is which I'm not familiar with. That said, I would be a little interested to find a superior solution. I actually learned a few optimization tricks while experimenting with this (simple stuff, but at the time I hadn't had to use it).
The actual complexity of the original problem was to solve 16^16 of these, where each number was based on 5x 4-sided dice and get the exact average optimal result. I had my time down a lot (though it looks like I didn't actually write down the time to process 16 of them) on the computer I was testing, single-threaded. I simplified the problem to just the matrices, since the dice probabilities can be placed into an array so it's just a reference point. Then it's just iterating through 16^16 solutions, but that still takes impossibly long with my existing solution. And even a few orders of magnitude faster isn't quite enough.
It seems to me like there should be a simpler solution, but I've thrown this at a few mathmaticians (my D&D group at one time consisted of 3 people working on math doctorates) and a few other programmers, and still havn't been able to reduce the problem to something reasonable to calculate.
I've already found stastical answers with a few billion bits of data, so those are not my goal right now. Now I just want to see if there's a better solution, because if there is one, I know I will learn something I don't already know from it.
my home computer is using an ATI card so I would have to use whatever their GP_GPU system is which I'm not familiar with
Yeah I'm not sure about that either, actually
CUDA even has PyCUDA with Numpy hooks, so lazy programmers can be lazy.
The actual complexity of the original problem was to solve 16^16 of these, where each number was based on 5x 4-sided dice and get the exact average optimal result.
Wait, is the purpose to get an average, or are you saying that each cell was solved by using an average? This sentence confused me. In fact, I kind of lost how what you said relates to finding the maximum value in each row and column for a square matrix.
I have an approximation of the average. From setting up something like 16^6 random 4x4 matrices with numbers between 5 and 20. What I wanted to do was see if there were any interesting "things" about solving these matrices for the largest value. I also would be curious about other solutions, like if you value having a single 14 and an 8 over two 11s. Though I have trouble configuring an example where you would have to make that choice. The maximum value in each row and column is just one of the questions, but solving that one was the most obvious.
Edit: But if you know a way to get the exact average, rather than just using statistics to approximate that, that could be interesting too.
The brute force solution definitely seems like it could be improved upon. It looks like you could solve it by just finding the 8 largest values, and then if need be "tweaking" them slightly so that you've picked one value in each row and column.
I've made a start on a better solution for the nxn case that should be much faster than brute force.
First of all, you start off by marking the largest number in each row and column. If you end up with 2n distinct numbers, you're already finished, but most likely you will have some numbers that have been marked twice, because they were the largest number in their row and column respectively.
Now, in the case of these numbers that have been marked twice, you need to take one "mark" and move it to another number in either the same row or the same column. In general, we'd like to move it to the highest number out of those in the same row or column, but there is a slight issue - it may be that we end up wanting to move two marks to the same spot.
Out of curiosity, what would your algorithm do if you gave it a giant n x n matrix where every single value was 0. Would it select the value from column 1 in every row and the value from row 1 in every column, so have collision on every value, then collide on every value but 1, then 2, then 3, out to n-1? Basically I'm trying to figure out what the "worst case" problem is, and this is just an abstraction of it.
Well, the collision resolution is the tricky part. I'm not actually sure how it would be done yet - I'd prefer to mess around with code. Do you want to do up a text file with an example matrix and/or a random generator?
Out of curiosity, what would your algorithm do if you gave it a giant n x n matrix where every single value was 0. Would it select the value from column 1 in every row and the value from row 1 in every column, so have collision on every value, then collide on every value but 1, then 2, then 3, out to n-1? Basically I'm trying to figure out what the "worst case" problem is, and this is just an abstraction
Yeah, if you did it the most straightforward way, you'd probably start by marking the first value in every row and column. However, that doesn't mean collision in every row and column - in fact you only have collision in one place, the top left corner. The mark counts would look like this: array([[2, 1, 1, 1], [1, 0, 0, 0], [1, 0, 0, 0], [1, 0, 0, 0]]) I guess that mark in the top left corner needs to end up in position (1,1) - i.e. the final solution would most reasonably be this: array([[1, 1, 1, 1], [1, 1, 0, 0], [1, 0, 0, 0], [1, 0, 0, 0]]) As for how it ends up there, I'm not sure yet.
Alright, I think I know how to do it. Let's take a case where there are bound to be some clashes / difficulties: The matrix is as follows: array([[9, 8, 7, 6], [1, 9, 0, 0], [0, 0, 9, 0], [0, 0, 0, 9]])I'm using (R,C) to represent positions in the matrix, with zero-based indexing. The 9 in the top left corner is (0,0), while the 8 to its right is (0,1); etc.
Initial marking: array([[2, 0, 0, 0], [0, 2, 0, 0], [0, 0, 2, 0], [0, 0, 0, 2]])(i.e. we have a clash on every row and column)
We now resolve the clashes. First of all, consider the top left corner (0,0). The best value in the same row or column is the 8, so we move a mark to there: array([[1, 1, 0, 0], [0, 2, 0, 0], [0, 0, 2, 0], [0, 0, 0, 2]])
Now, consider what we can do with the mark in position (1,1). We can move it to any spot in the same row or column but position (0,1) is already occupied. However, if we were to move it to (0,1), then we would be free to move the row marker from (0,1) to any other position in that row. What this means is that when we're looking for where to move a mark, if we see a marked spot then we can also move the mark to any spot in the row or column of that mark. In other words, we can move the extra mark from (1,1) to any of the following spots: (0,2), (0,3), (1,0), (1,2), (1,3), (2,1), (3,1). Choosing the highest value, we pick (0,2), so now we have this: array([[1, 1, 1, 0], [0, 1, 0, 0], [0, 0, 2, 0], [0, 0, 0, 2]])
Applying the same idea, (2,2) is now in some sense "connected" to the rest of the unoccupied squares in the matrix, so we can move it anywhere we like - we choose (0,3): array([[1, 1, 1, 1], [0, 1, 0, 0], [0, 0, 1, 0], [0, 0, 0, 2]])
Similarly, we now move the marker from (3,3) to (1,0), and we are done: array([[1, 1, 1, 1], [1, 1, 0, 0], [0, 0, 1, 0], [0, 0, 0, 1]])
I'll prettify it now. The above post was pretty much a direct brain-dump; I was thinking about it as I was posting and that was the easiest way to do it.
EDIT: Is that better? It's formatted with numpy's standard array representation, and the indexing is now zero-based with that in mind.
Also, it's pretty clear that the core of what's going on here is this idea of "connectedness". Formalising it would likely lead to a further improvement in the algorithm; a proof that the algorithm arrives at the optimal solution is also required. For now, I guess I'll go ahead and implement what I described above.
Calculated total: 0 For an nxn matrix, the worst-case time complexity should be O(n^4). Granted, that's not particularly good, but it should be a heck of a lot better than brute forcing. That's assuming that this approach actually finds the optimal solution for arbitrary nxn matrices, of course.
As a rough estimate for brute forcing, there are n ways to pick an element in each row, and n to pick one in each column, so (ignoring collision issues) you have O(n^(2n)) different ways to pick an element in each row and column
A fast general solution to the nxn sized matrix would be even better.
Algorithm for nxn random matrix, selecting 2n values, minimum 1 per row, minimum 1 per column, such that sum(val) is maximized:
1) For every row, select highest value 2) For every column iff no value is selected yet, select highest value 3) For the n remaining selections just go from highest unselected value in the matrix until you have made 2n selections
This is O(n). After 2) you have satisfied all selection constraints, and of the top of my head I can not see any pathological configurations that will not result in sum(val) being maximized after 3). Feel free to contradict me though.
That's actually O(n^2), and only with a little work. Steps 1 and 2 are both O(n^2), and then in the worst case for step 3 you have to find the n largest elements out of n^2-n (i.e. O(n^2)) in step 3 - one approach would be to sort the elements, which is O(n^2 log(n^2)) = O(2n^2 log(n)) = O(n^2 log(n)). Apparently with a smart selection algorithm you could get this down to O(n^2), though, which is pretty cool.
I had thoughts along those lines, but I didn't quite convert the requirements in my head to 2n values with minimum one per row and one per column, which makes things a lot easier.
Comments
In the Kaiji anime they go on about psychological aspects of the game, and they use one specific rule to enforce this: you must look at the card you play in a turn before playing it, and players play their cards in sequence rather than simultaneously, with the player to play first swapping in each subsequent turn. The idea is that if they are playing first a player may give away a "tell" if they play a game-ending card (Emperor or Slave), and then the other player may make use of this. Of course, in the anime there is also cheating involved, since it is Kaiji after all, but we're setting that aside for the math problem.
In the purest sense, though, I do agree that the optimal strategy is random choice. That's why I said this:You haven't solved that one yet ^_~
Nonetheless, the human aspect does raise at least this question - how would one best implement the random choice, given human limitations?
I would question whether the further distance would be "worse" damage, and if so, should the negative infinite utility be modified from 30mm? If drilling from 30mm to 45mm really doesn't do any more damage functionally, then we can leave the standing assumption.
It seems to me that the best source of randomness you have available to you is simply shuffling the cards in your hand. For example, you could either shuffle the cards once and play them in order, or shuffle the cards every turn in order to randomly pick one from your hand. Technically speaking, in the anime it's said that 45mm could result in death, but for the sake of the problem it doesn't really matter, because you can 100% avoid ending up in a situation where you are at 29mm and must keep playing. For example, you could bet 2mm each round for all 12 rounds, and if you lost every round the drill would still only be at 24mm.
To start thinking about the expectations, I am going to use complex numbers to separate moneys from mm penetration. Real numbers will represent moneys; imaginary numbers will represent total mm penetration. I am also going to begin considering a minimum bet of 1mm is always chosen. Since Kaiji risks a maximum loss of 12mm in the worst possible case, he cannot possibly lose his eardrums (which I think terminates the game?) nor lose his life (which terminates the game).
E(payout | always minimum bet, starts as King holder, random strategy) = (4/5)*(100000) + (1/5)*(1i) + (4/5)*(100000) + (1/5)(1i) + (4/5)*(100000) + (1/5)*(1i) + (1/5)*(500000) + (4/5)*(1i) + ... = 6 * ( (4/5)*(100000) + (1/5)*(1i) ) + 6 * ( (1/5)*(500000) + (4/5)*(1i) ) = 1080000 + 6i.
Assuming I didn't screw up my decimal places, he can expect 1.08 million moneys and 6 mm penetration with minimum bet and starting as King holder. Note that the expectations are additive, which carry the property of being commutative.
If we swap all the order of the expectation calculation such that the King expectations are replaced with Slave expectations and vice versa, the result will be the same as if we had not swapped them. This holds so long as all 12 rounds are guaranteed to be played, so that both special cards are held for 6 rounds each:
E(payout | always minimum bet, starts as Slave holder, random strategy) = 1080000 + 6i.
Let's consider that Kaiji wants to get as close to 30mm without going over, and Kaiji wants to try to spread those mm evenly across the board! 30mm is fail, but 29mm is not. Kaiji will bet 2mm on all but 5 bets, and 5 bets will be placed at 3mm, for 29mm total bet. The higher bets will be placed as King holder only as an experiment. Since all 12 rounds will be played, it doesn't matter whether Kaiji begins as Slave holder or King holder (commutative property of addition).
E(payout | seven 2mm bets, five 3mm bets as King holder, random strategy) = 5 * ( (4/5)*(3*100000) + (1/5)(3*i) ) + 1 * ( (4/5)*(2*100000) + (1/5)*(2*i) ) + 6 * ( (1/5)*(2 * 500000) + (4/5)*(2 * i) ) = 2560000 + 13i
In this case, Kaiji can expect 2.56 million moneys and 13 mm penetration.
This is obviously becoming a pattern. We want one bid strategy as Slave holder and one bid strategy as King holder. Since expectations are commutative, it cannot matter what order the bids are placed so long as each classification of bid is played in the correct scenario (King bets as King holder, Slave bets as Slave holder).
Let us bid BS mm as Slave holder and BK mm as King holder. We must first guarantee all 12 rounds can be played for this simpler math, so 6*BS + 6*BK <= 29mm. This is constraint 1. The minimum bet for any round is 1mm, so constraints 2 and 3 are B<sub>S >= 1, BK >= 1.
Expectation = 6 * BK * ( (4/5)*100000 + (1/5)i ) + 6 * BS * ( (1/5)*500000 + (4/5)i ).
We want to maximize the real value of the expectation over BK and BS while adhering to all constraints; the real value of the expectation represents the objective function to be maximized. Constraint 1 guarantees that Im[Expectation] <= 29mm, and it also guarantees (even in the worst case), that Kaiji really loses nothing, thus we don't really care about the imaginary value of the objective function.
Re[Expectation] = B<sub>K * 480000 + BS * 600000
Clearly BS is worth more payout per mm, so maximizing BS while adhering to all constraints will maximize the objective function. To do this, BK must be minimized (due to constraint 1), so BK = 1 (the minimum possible due to constraint 3).
Solving constraint 1:
1 + BS <= 29/6
B<sub>S <= 29/6 - 1
B<sub>S <= 3.8333...
Assuming you find a way to divvy out that fractional part over Slave bets:
Re[Expectation] = 1*480000 + 3.8333...*600000 = 2.78 million
If I did all of this correctly, 2.78 million is the most Kaiji could earn without putting an eardrum at any actual risk.
Next chapter: putting the eardrum and/or life at risk. This one gets complicated because all 12 rounds might not be played; it also might make a difference whether King holder or Slave holder is chosen first. In that case, constraint 1 would be dropped, and be replaced with Im[Expectation] < 30mm.
Does the game end necessarily when the eardrum is pierced?
For example, consider this scenario: It's the second last round, and the drill is at 27mm. If you win, you will get to the last round at 27mm, and so you clearly will bet 2mm on the last round. If you lose, you're at 28mm, and so you will obviously bet 1mm on the last round. Consequently, this is also wrong. Also, even if your calculations were correct, that value wouldn't be the most he could earn, but rather the maximum expected value across all strategies.
If your example addresses an issue of rounding, where Kaiji might end on 28mm instead of 29mm because 29 does not divide evenly, I will assure you that the final expected calculation I presented does not account for rounding as was mentioned quite clearly (3.833 must be divided out in some clever way). However, you can only have a worse expectation if you round that wager, because you must round down; to round up breaks constraint 1 allowing more than 29mm to be wagered.
For example, if you bet 18mm every round and won every time, the drill would still finish at 0mm, but your total bets would be 18*12=216mm. Hence your constraint is completely wrong - the amount you can bet is in fact dependent on the outcomes of previous rounds.
Consequently, the optimal betting strategy could bet different amounts on the same round, depending on the outcome of previous rounds.
By your reasoning, the best strategy would be to bet 1mm on the first and second rounds.
However, consider the following strategy:
Bet 1mm on the first round. If you win the first round, bet 2mm on the second round, otherwise bet 1mm on the second round.
Like the previous strategy, this one can lose at most 2mm and hence is perfectly safe. However, it has a higher expected gain, and hence it is better!
However, you are proposing "changing the strategy" on a round by round basis. I am speaking of a single strategy, chosen at the start, and employed through the entirety of the game.
When I say that I guarantee no harm, I mean that, even if Kaiji loses every single round, the Strategy proposed still prevents harm.
What you describe is changing strategies as the game goes on, and is predicated on "but what if Kaiji doesn't lose every single round?" Such a strategy obviously does not account for the possibility of losing every round; it is in another class. So let me discuss this class of strategy:
When I offer to calculate a Strategy that maximizes Im[Expectation] < 30, what I am saying is that this Strategy would expect (just under) 30mm by game end. The changing strategy you talk about forces (just under) 30mm by game end. In effect, the strategy you are talking about is part of the strategy which maximizes Re[Expectation] moneys and maximizes Im[Expectation] < 30.
I got it covered, boss.
In your own words,Indeed, such an approach would put your eardrum/life at risk, and hence is clearly not optimal. There is a difference between forcing less than 30mm, and having an expectation of less than 30mm. The former is 100% safe, while the latter could possibly hit 30mm in the wrong circumstances; you yourself said "putting the eardrum and/or life at risk".
However, as I said before, by my calculations, with the correct approach you should expect a gain of ~8 million with no risk whatsoever.
So you have a 3x3 matrix. It contains random integers. Those integers can be duplicated, in case that matters. For example:
07|08|12
16|13|11
07|17|13
You want to pick one value from each row, and one value from each column. You cannot pick any specific number twice. Your goal is to pick the highest possible total set value.
The brute force method here would be to try every possible combination of valid picks and find the one with the highest total value. There is a significantly faster (in terms of how fast my computer gets an answer) solution to this problem.
The value is going to be equal to the sum of the total minus the three lowest values, unless those values are in a single row or column, in which case you subtract the two lowest values and the fourth lowest value. This works really well for me, and wasn't a pain to code once I realized it.
- - - - -
The larger problem involves solving the slightly more complex 4x4 matrix. The faster solution I used for the 3x3 doesn't work anymore, because you are discarding just as many values as you are including (8 or each). So-far, I havn't found a faster method than brute forcing. There are methods that seemed like they should be faster, like checking the sum of each valid template that can exist and comparing those (reduces the complexity by about 1/2) but the extra operations ended up being more computationally expensive by about 10% in the specific language and method I was using at the time. It could have just been my own execution that failed. Since you can rotate the matrix freely, you might be able to manipulate it down to only 1/16th the total problem size in theory... but I havn't quite solved that.
Obviously this is more "algorithm & programming" than math, but I found it interesting. It's no-longer something I need to solve for any reason, but I'm still curious. A fast general solution to the nxn sized matrix would be even better.
Generally, if you have an NxN matrix, you want to choose the 2N elements which sum to the highest value, while discarding N^2-2N elements. The N=2 case is degenerate, because you will have chosen all 4 numbers. It also turns out that the parabola formed by N^2-2N hits its extrema at N=2, so all N greater than 2 will follow the same pattern of throw-aways increasing faster than keepers that is seen as you move from N=3 to N=4. If you are talking "real time speed" of your computer's ability to process as the metric, I can almost guarantee you there is some nice way to do this with linear algebra that will finish super fast if you push it through a GPU; in fact some kind of convolution over the matrix would probably do the trick very quickly indeed. If you are talking algorithmic complexity, that is a bit more interesting.
This kind of problem reminds me of Sudoku. Have you looked into the algorithms to solve Sudoku at all?
The actual complexity of the original problem was to solve 16^16 of these, where each number was based on 5x 4-sided dice and get the exact average optimal result. I had my time down a lot (though it looks like I didn't actually write down the time to process 16 of them) on the computer I was testing, single-threaded. I simplified the problem to just the matrices, since the dice probabilities can be placed into an array so it's just a reference point. Then it's just iterating through 16^16 solutions, but that still takes impossibly long with my existing solution. And even a few orders of magnitude faster isn't quite enough.
It seems to me like there should be a simpler solution, but I've thrown this at a few mathmaticians (my D&D group at one time consisted of 3 people working on math doctorates) and a few other programmers, and still havn't been able to reduce the problem to something reasonable to calculate.
I've already found stastical answers with a few billion bits of data, so those are not my goal right now. Now I just want to see if there's a better solution, because if there is one, I know I will learn something I don't already know from it.
CUDA even has PyCUDA with Numpy hooks, so lazy programmers can be lazy. Wait, is the purpose to get an average, or are you saying that each cell was solved by using an average? This sentence confused me. In fact, I kind of lost how what you said relates to finding the maximum value in each row and column for a square matrix.
Edit: But if you know a way to get the exact average, rather than just using statistics to approximate that, that could be interesting too.
It looks like you could solve it by just finding the 8 largest values, and then if need be "tweaking" them slightly so that you've picked one value in each row and column.
First of all, you start off by marking the largest number in each row and column. If you end up with 2n distinct numbers, you're already finished, but most likely you will have some numbers that have been marked twice, because they were the largest number in their row and column respectively.
Now, in the case of these numbers that have been marked twice, you need to take one "mark" and move it to another number in either the same row or the same column. In general, we'd like to move it to the highest number out of those in the same row or column, but there is a slight issue - it may be that we end up wanting to move two marks to the same spot.
array([[2, 1, 1, 1],[1, 0, 0, 0],
[1, 0, 0, 0],
[1, 0, 0, 0]])
I guess that mark in the top left corner needs to end up in position (1,1) - i.e. the final solution would most reasonably be this:
array([[1, 1, 1, 1],[1, 1, 0, 0],
[1, 0, 0, 0],
[1, 0, 0, 0]])
As for how it ends up there, I'm not sure yet.
The matrix is as follows:
array([[9, 8, 7, 6],I'm using (R,C) to represent positions in the matrix, with zero-based indexing. The 9 in the top left corner is (0,0), while[1, 9, 0, 0],
[0, 0, 9, 0],
[0, 0, 0, 9]])
the 8 to its right is (0,1); etc.
Initial marking:
array([[2, 0, 0, 0],(i.e. we have a clash on every row and column)[0, 2, 0, 0],
[0, 0, 2, 0],
[0, 0, 0, 2]])
We now resolve the clashes. First of all, consider the top left corner (0,0). The best value in the same row or column is the 8, so we move a mark to there:
array([[1, 1, 0, 0],[0, 2, 0, 0],
[0, 0, 2, 0],
[0, 0, 0, 2]])
Now, consider what we can do with the mark in position (1,1). We can move it to any spot in the same row or column but position (0,1) is already occupied. However, if we were to move it to (0,1), then we would be free to move the row marker from (0,1) to any other position in that row. What this means is that when we're looking for where to move a mark, if we see a marked spot then we can also move the mark to any spot in the row or column of that mark. In other words, we can move the extra mark from (1,1) to any of the following spots: (0,2), (0,3), (1,0), (1,2), (1,3), (2,1), (3,1). Choosing the highest value, we pick (0,2), so now we have this:
array([[1, 1, 1, 0],[0, 1, 0, 0],
[0, 0, 2, 0],
[0, 0, 0, 2]])
Applying the same idea, (2,2) is now in some sense "connected" to the rest of the unoccupied squares in the matrix, so we can move it anywhere we like - we choose (0,3):
array([[1, 1, 1, 1],[0, 1, 0, 0],
[0, 0, 1, 0],
[0, 0, 0, 2]])
Similarly, we now move the marker from (3,3) to (1,0), and we are done:
array([[1, 1, 1, 1],[1, 1, 0, 0],
[0, 0, 1, 0],
[0, 0, 0, 1]])
EDIT: Is that better? It's formatted with numpy's standard array representation, and the indexing is now zero-based with that in mind.
Also, it's pretty clear that the core of what's going on here is this idea of "connectedness". Formalising it would likely lead to a further improvement in the algorithm; a proof that the algorithm arrives at the optimal solution is also required. For now, I guess I'll go ahead and implement what I described above.
Results for the cases mentioned above:
Input matrix:array([[9, 8, 7, 6],
[1, 9, 0, 0],
[0, 0, 9, 0],
[0, 0, 0, 9]])
--------------------------------------------
Choice of elements (1=chosen, 0=not chosen):
array([[1, 1, 1, 1],
[1, 1, 0, 0],
[0, 0, 1, 0],
[0, 0, 0, 1]])
--------------------------------------------
Calculated total: 58
Input matrix:
array([[0, 0, 0, 0],
[0, 0, 0, 0],
[0, 0, 0, 0],
[0, 0, 0, 0]])
--------------------------------------------
Choice of elements (1=chosen, 0=not chosen):
array([[1, 1, 1, 1],
[1, 1, 0, 0],
[1, 0, 0, 0],
[1, 0, 0, 0]])
--------------------------------------------
Calculated total: 0
For an nxn matrix, the worst-case time complexity should be O(n^4). Granted, that's not particularly good, but it should be a heck of a lot better than brute forcing. That's assuming that this approach actually finds the optimal solution for arbitrary nxn matrices, of course.
As a rough estimate for brute forcing, there are n ways to pick an element in each row, and n to pick one in each column, so (ignoring collision issues) you have O(n^(2n)) different ways to pick an element in each row and column
Syntax highlighting within < code> tags.
1) For every row, select highest value
2) For every column iff no value is selected yet, select highest value
3) For the n remaining selections just go from highest unselected value in the matrix until you have made 2n selections
This is O(n). After 2) you have satisfied all selection constraints, and of the top of my head I can not see any pathological configurations that will not result in sum(val) being maximized after 3). Feel free to contradict me though.
I had thoughts along those lines, but I didn't quite convert the requirements in my head to 2n values with minimum one per row and one per column, which makes things a lot easier.