Weighted random selection from sorted array (a little math help)

[Carey Brown]

I'm working on a Battleship game and I have the code in place to compute the probability that a ship is at a given coordinate. This is what it looks like before any moves are made:

    0   1   2   3   4   5   6   7   8   9  
   --  --  --  --  --  --  --  --  --  --  
0| 10  15  18  20  21  21  20  18  15  10  
1| 15  20  23  25  26  26  25  23  20  15  
2| 18  23  26  28  29  29  28  26  23  18  
3| 20  25  28  30  31  31  30  28  25  20  
4| 21  26  29  31  32  32  31  29  26  21  
5| 21  26  29  31  32  32  31  29  26  21  
6| 20  25  28  30  31  31  30  28  25  20  
7| 18  23  26  28  29  29  28  26  23  18  
8| 15  20  23  25  26  26  25  23  20  15  
9| 10  15  18  20  21  21  20  18  15  10 

I turn this in to a List of coordinates sorted in descending order by probability. Now I want to choose a random entry in the list such that any entry *could* be chosen but with a weighted leaning towards the beginning of the list with the higher probabilities.

This is one attempt I made where the coordinates are added to the list multiple times depending on the probability. Slightly works but not weighted enough.

	public void shoot()
	{
		List<RC>	list = new ArrayList<RC>();
		for( int r=0 ; r < 10 ; r++ )
			for( int c=0 ; c < 10 ; c++ )
				for( int j=0 ; j < probability[r][c] ; j++ )
					list.add( new RC( r, c, probability[r][c] ) ); // add multiple times
		
		Collections.shuffle( list );
		Collections.sort( list );
		
		int			i = RAND.nextInt(list.size());
		RC			rc = list.get(i);
		shots[rc.r][rc.c] = true;
	}

I also tried using probability-squared but this was way to heavily weighted to the higher probabilities.

Any suggestions for a compromise approach?

Here's another set of probabilities after a few shots (no ships yet).

    0   1   2   3   4   5   6   7   8   9  
   --  --  --  --  --  --  --  --  --  --  
0| 10  15  18  20  21  19  15  18  14  10  
1| 15  20  22  22  20  10   *  13  12  13  
2| 18  23  26  28  29  19  20  26  17  18  
3| 20  24  25  24  20   *  14  22  11  19  
4| 21  26  29  31  30  18  23  21   *  16  
5| 21  26  29  31  29  26  30  29  15  21  
6| 20  25  28  30  26  28  30  28  19  20  
7| 18  23  26  28  21  28  28  26  20  18  
8| 14  17  17  14   *  15  19  20  18  15  
9| 10  15  18  20  16  21  20  18  15  10 

[Les Morgan]

Carey,

I am afraid my thinking goes along this line: since you have probabilities and there are ships of finite sizes, then I would overlay a grid and pick the highest probabilities from that grid. So in the classic Battle Ship, you have 2, 3, 4, and 5 hole boats.  I would start with the 2 grid and choose the coordinates with the highest probability.

Les

[Carey Brown]

That's about how I arrived at these probabilities. I have ships of sizes: 5, 4, 3, 2, and 2. At each coordinate is the sum of all possible ship positions that could encompass that coordinate. So a probability of 32 would be a likely first place to shoot. However, if you follow that logic all the time then the opponent will see the pattern and place their ships on the perimeter. Hence my reasoning for a weighted selection, leaning toward the higher probabilities, but not ruling out the perimeter.

[Les Morgan]

I see, and a very good point indeed. I think then that I would randomly generate a point, and do an area search for the highest probability in that area, probably using the grid overlay idea on too of the area.

So lay the grid out, I like the 2X2, and take a random shot, then search say 2 or 3, or even a random number, grids in each direction from the random shot, and choose the highest probability in the area.

[Stephan van Hulst]

Why not use a Guassian distribution (bell curve) instead of a uniform one? Order your list so your preferred choices are at the start. You can then generate an index with a Gaussian distribution using:

(int) Math.abs(generator.nextGaussian() * choices.size());

[Stephan van Hulst]

Woops, I misread the contact for nextGaussian(). The standard deviation is one, so it generates numbers greater than one.

You need to tweak my code snippet so the bell curve has a cutoff point after the last index of your list. You can do this by simply re-rolling when the index is greater or equal to the size of the list, but I'm not sure how that influences the distribution.

Anyway, try it out, generate a bunch of indices and let us know if the distribution is fair enough.

[Stephan van Hulst]

You can tweak the shape of the bell curve by applying a multiplier to the list size, before you apply the cut-off.

[Stephan van Hulst]

As a final remark, and then I'll shut up, you might actually find a Laplace distribution easier to use.

Check out this class from the Apache commons lib: http://commons.apache.org/proper/commons-math/javadocs/api-3.6.1/org/apache/commons/math3/distribution/LaplaceDistribution.html

[Carey Brown]

This  Gaussian distribution seems to get me close to what I need. I would have liked to have it weighted slightly heavier towards the high probability end. I'll look further into Laplace, it wasn't immediately obvious on how to work it into my program.

	//----------------------------------------------------------------------
	public static int nextGaussian( int size )
	{
		double			d;
		while( ( d = Math.abs( RAND.nextGaussian() ) ) > 3.0 )
			;
		return (int)( d / 3.0 * size );
	}
	
	//----------------------------------------------------------------------
	public void shoot()
	{
		List<RC>	list = new ArrayList<RC>();
		for( int r=0 ; r < 10 ; r++ )
			for( int c=0 ; c < 10 ; c++ )
				if( probability[r][c] > 0 )
					list.add( new RC( r, c, probability[r][c] ) );
		
		Collections.shuffle( list );
		Collections.sort( list );
		
		int			i = nextGaussian(list.size());
		RC			rc = list.get(i);
		shots[rc.r][rc.c] = true;
	}

[Piet Souris]

And one for me, then I'll shut up as well.

First: the distribution structure that I have in mind is this one (sort of inverse cumulative  density function):
say wel have the cells A, B and C each with probability 20%, D and E with each 15% and F with 10%, then I use a TreeMap(Double, List<Cells>) with reversed natural ordering:
<0, List(A, B, C)>
<.6, List(D, E)>
<.9, List(F)>

Now, drawing from the uniform distribution with draw = random.nextDouble(), and using TreeSet.floorEntry(draw) will give us the relevant list, to pick a cell from.
If this 'natural' distritbution is not good enough, then the easiest way to do something about it is to tweek or change the uniform distribution somewhat.

Stephan already gave some examples, where he corrected the standard normal distribution, because that distribution gives a change of about 32% of getting a value outside of (-1, 1).
But that and the Laplace are pretty complicated to apply, needing to be truncated.

There are easier ways. Think of the graph of the CDF of a Uniform(0,1) distribution. That is simply the graph of y = x, for x in the segment [0, 1].
It follows that any function that starts in (0,0), ends in (1,1) and is non-decreasing, is a candidate to get some random value between 0 and 1.

For instance, take this function: f(x) = 2x for x in (0, 1/4), 2/3 * x + 1/3 for x in (1/4, 1), and let the random variable X have this CDF. Then P[X < 1/4] = .5, P[X < .5] = 2/3, so that P[ 1/4 < X < .5] = 1/6.
As you see, the chances are a little shifted towards the lower values. The rule is in this case: draw from the U(0,1), and if x < 1.4 then take 2 * x as outcome, otherwise 2/3x + 1/3. Within constraints, you can vary a and b until you get the desired shift.

Other simple candidates are: y = x^2 (already tried by Carey), y = sqr(x) shifting the chances to the end, y = sin(x * pi / 2) et cetera. Just make a drawing of y = x, and take any non-decreasing function starting in (0,0) and ending in (1,1). Should be a lot of fun.

[Stephan van Hulst]

Sweet insights Piet, have a cow.

[Piet Souris]

Thank you, Stephan!

But I must correct a blunder of mine.
If you have a random variable X with CDF: F(x) = 2x for x in (0, 1/4) and F(x) = (2/3)x + 1/3 for x in (1/4, 0), then the rule for drawing a value x with x = random.nextDouble() is:
if x <= .5 then outcome = .5x, else outcome = 1.5x - .5.

I forgot to express X in terms of U(0,1).
I don't want to talk about maths anymore, so I leave it to the interested reader to explain this.

For the very enthousiast reader: if we take as CDF: sin(x * pi/2), how must we transform our outcome of random.nextDouble()?

And now, shut up, Souris! Ay ay sir...