The "Good AI, Bad AI" Problem

[PWrong]

I had an idea last night about a simple game where you play as a utilitarian. You have a bunch of AIs, and some of them are good and some are evil. You know exactly how many are bad, but you don't know which ones. Each turn, each bad AI randomly selects another AI and kills it. We assume it's possible for two AIs to kill each other simultaneously. Your job is to maximise the total lifespan by trying to kill the bad guys. There could be another version, where the life of a good guy is more valuable than the life of a bad guy. It gets complicated very quickly.

Let's look at the game with only 2 guys.
If they're both good, you obviously don't kill anyone.
If they're both evil, then it's better to kill one of them. If you do nothing, they'll both kill each other.

If only one is good, then it depends which version you're playing. If everyone's life is equal, then it doesn't matter whether you kill one person or do nothing. But if the life of a good guy is more valuable, it gets controversial.
If you do nothing, the bad guy will kill the good guy, so you end up with one bad guy. But if you randomly select one to kill, you have a 50% chance of having a good guy left. Wow, I already feel guilty about playing with the lives of these poor things. It's odd that I can play a video game and kill hundreds of little things for no reason, but when I save the lives of two abstract, hypothetical entities by killing one, I feel bad.

I'm going away for two weeks, but I hope people keep discussing this. I'll think about the case with three AI's while I'm away.

Split from "utilitarianism" by jinydu.

[moonlord]

This sounds a lot like game theory to me. I'll have to do some research.

[Keiji]

I'll think about the case with three AI's while I'm away.

Three good AIs: Don't kill anyone.
Three evil AIs: Kill two of them.
Two good, one evil: Killing one gives a 1/3 chance of two good AIs, a 2/3 chance of one evil AI. Killing two gives a 2/3 chance of one good AI, a 1/3 chance of one evil AI.
One good, two evil: Kill two of them, for a 1/3 chance of one good AI, and a 2/3 chance of one evil AI. Killing only one gives a 100% chance of one evil AI.

Hm...

[PWrong]

Hey guys, I'm back.

This sounds a lot like game theory to me. I'll have to do some research.

I studied a bit of game theory in ops research this year (ok, maybe I didn't study, but I did pass the exam ). What I learned only works for games with two human players, where one player is maximising something, and the other is minimising it.

Let's formalise this a bit. "gge" represents two good, one evil e.t.c. Alternatively, {x,y} means we have x good and y evil. If on the first turn we kill n AI's, then we call this action "kn". The utility of this action is U(kn).

There's another variation we could consider. Once an AI kills, you know it's evil, so you can kill it on your next turn. I think this is more interesting, because the concept of "punishment" arises. For a large population with only a few bad guys i.e. x>>y (like most human societies), it's best to wait one turn, and kill everyone who kills on the first turn. The problem with this version is that we now have four different possible AI's. I'll consider this version later.

Suppose an action can have two possible consequences: A & B. The probability of A is p₁, and the probability of B is p₂. The utility (in this case, the number of lives) of A is a, and the utility of b is b. Then the utility of the action is the "expected utility": p₁*a + p₂*b. Anyone who's learned any probability should understand this. If not I'll explain it.

Here's my analysis of three AI's.
ggg = {3,0}: kill noone. U(k0) = 3
eee = {0,3}: kill 2. U(k2) = 1

For the others, we'll first assume that good and evil AI's are equally valuable.

gge = {2,1}:
k0: gge -> ge -> U(k0) = 1
k3: U(k3) = 0

k1: gg -> 2, p₁ = 1/3
ge -> 1, p₂ = 2/3
expected utility for k1 = 2*(1/3) + 1*(2/3)
U(k1) = 4/3

k2: g or e, 1 point
U(k2) = 1

So the best option for gge is k1, that is, kill 1 AI, giving a utility of 4/3.

gee = {1,2}:
k0: gee -> e -> U(k0) = 1
k1: gee -> ge -> 1, p₁ = 2/3
gee -> ee ->0, p₂ = 1/3
U(k1) = 1*(2/3) + 0*(1/3) = 2/3
k2: gee -> 1
U(k2) = 1
k3: U(k3) = 0

The best option for "gee" is to kill noone, or to kill two.

This is all too complicated, so I'll put the utility values for each action in a table. The first column is the number of evil AI's, and the first row is the number to kill in the first turn. The other numbers represent the expected utility for that action. The best action to take is the maximum in the given row.

Code: Select all

Two AI's
|0  1  2
-----------
0|2  1  0
1|1  1  0
2|0  1  0

Three AI's
|0   1   2  3
--------------
0|3   2   1  0
1|1  4/3  1  0
2|1  2/3  1  0
3|0   0   1  0

I hope all this is still understandable. I might have formalised it a bit too much.

[moonlord]

THE BLACK AND WHITE PROBLEM

OK. I've done the table for 4 AI's by trial but there is an empty place, the EEEE one (kill zero). EDIT: I've removed the 47/108 value for GEEE, kill zero, because it's incorrect.

GGGG: 4 3 2 1 0
GGGE: 1 3/2 3/2 1 0
GGEE: 5/6 7/8 1 1 0
GEEE: ? 3/4 1/2 1 0
EEEE: ? 3/4 0 1 0

[too lazy to format a code tag]

U(n,m,k) is the function, U:Z^3->Q. n AI's, m evil AI's, k killed at round 0.

A. Rules:

R1. if n = k then U = 0. Duh. If you kill all...
R2. if n = k + 1 then U = 1. You kill all except one.
R3. if m = 0 then U = n - k. No evil, noone kill anybody. You get what you left alive.

B. Conjectures (valid with 0->5 AI's, untested for higher values):

C1. if n = k + 2 then U = 2 * (1 - m/n). That is, the corresponding column is linear from 2 to 0.
C2. Except for the trailing zero value, the second row is symmetric. The values for five AI's for the second row are: 1, 8/5, 9/5, 8/5, 1, 0.

I calculate the values using common sense, for the simpler situations, and a recursive method for the more complex. If it were a good method, I'd have filled the table...

I'm currently trying to make a program that calculates these tables and maybe more. However, the current version is using 65535 (2^16-1) random generations for probability "calculations" (at round 0) and backtracking for all the evil-kill-good possibilities at later rounds. So this is how it works - example: GEEE, kill one. U(4,3,1).

Random generation will tell that there are only two possible results for the K1 operation: GEE and EEE. It will also tell that there are aproximatively 75% chances for GEE and 25% for EEE.

Now testing GEE evolution (start at round 1). Every evil has two choices, and there are two evils, so there are 2^2 = 4 possibilities. Backtracking:

1. E1 -> G and E2 -> G. Result: EE. Start round 2: Backtracking: one possibility, E1 -> E2 and E2 -> E1. Result: null (stable). Therefore this option has utility 0.

2. E1 -> G and E2 -> E1. Result: GE. Start round 2: Backtracking: one possibility, E -> G. Result: E (stable). Therefore this option has utility 1.

3. E2 -> G and E1 -> E2. Result: GE. Start round 2: Backtracking: one possibility, E -> G. Result: E (stable). Therefore this option has utility 1.

4. E1 -> E2 and E2 -> E1. Result: G (stable). Therefore this option has utility 1.

Exiting GEE evolution test. U(3,2,0) = (0+1+1+1) / 4 = 3/4.
Entering EEE evolution test.

[There are 2^3 = 8 possilibilities.]

Exiting EEE evolution test. U(3,3,0) = 3/4.

Now calculating average utility for GEEE: U(4,3,1) = 75% * U(3,2,0) + 25% * U(3,3,0) = 75% * 3/4 + 25% * 3/4 = 3/4. Done.

As you can see, this is a very inefficient method.

[Got to go to beach now, will finish the post when I return - ETA 21:00 GMT+2]

[Nick]

Could you guys make titles for your tables? In other words, what does the first column represent, the first row, etc?

[PWrong]

OK. I've done the table for 4 AI's by trial but there is an empty place, the EEEE one (kill zero). EDIT: I've removed the 47/108 value for GEEE, kill zero, because it's incorrect.

Thanks for the help moonlord. The empty ones don't look difficult. If you have four evil guys and kill none, they'll all kill each other, so U=0. For GEEE, k0, you have four guys and three die. So you get U = 1.

Code: Select all

      0   1   2  3 4
GGGG: 4   3   2  1 0
GGGE: 1  3/2 3/2 1 0
GGEE:5/6 7/8  1  1 0
GEEE: 1  3/4 1/2 1 0
EEEE: 0  3/4  0  1 0


I haven't checked your other values yet.

U(n,m,k) is the function, U:Z^3->Q. n AI's, m evil AI's, k killed at round 0.

We can define another function V(n,m) that gives the maximum utility, i.e. it assumes you make the best choice. That would come in handy for the recursion.

R1. if n = k then U = 0. Duh. If you kill all...
R2. if n = k + 1 then U = 1. You kill all except one.
R3. if m = 0 then U = n - k. No evil, noone kill anybody. You get what you left alive.

R4. If n = m and k = n-1, then U=1. If k is anything else, U=0. If they're all evil, kill all except one.
That is,
U(n, n , n-1) = 1
U(n, n, k) = 0, (k != n-1)

Let's look at arbitrary values of n.

If you have one evil one, and you don't kill anyone, you get one less good guy.
U(n, 1, 0) = V(n-1, 1)

One evil one, kill one. You have a 1/n chance of getting the bad guy. If you don't get him, two good guys die.
U(n, 1, 1) = 1/n * V(n-1,0) + (n-1)/n * V(n-2, 1)

For arbitrary k, we have a k/n chance of getting the bad guy.
U(n, 1, k) = k/n * V(n-k, 0) + (n-k)/n * V(n-k, 1)

Let's try two evil guys.

k0: two people die. Each evil guy has n-1 potential victims, one of which is evil.
The chance of the two evil guys killing each other simultaneously is 1/(n-1)*1/(n-1)
The chance of the 1st evil guy killing the 2nd bad guy, and the 2nd bad guy killing someone else is 1/(n-1) * (n-2)/(n-1)
The chance of this happening the other way around is (n-2)/(n-1) * 1/(n-1)
The chance of both bad guys killing good guys is (n-2)/(n-1) * (n-2)/(n-1)

So, adding all this up, we have:
U(n, 2, 0) = V(n-2,0) / (n-1)^2 + V(n-2,1) * 2 (n-2)/(n-1)^2 + V(n-2,0) *(n-2)^2/(n-1)^2

k1: Now, we still have two evil guys, but this time we kill one.
We have a 2/n chance of getting a bad guy. If we do, the remaining bad guy will kill a good guy, so we end up with V(n-2, 1).
If we don't get a bad guy, we get the situation where we have one less guy, and two guys are going to die. So the result is the same as U(n-1,2,0)
U(n,2,1) = V(n-2, 1) * 2/n + U(n-1, 2, 0) * (n-2)/n

Note that this is the same as:
U(n,2,1) = U(n-1, 1,0) * 2/n + U(n-1, 2, 0) * (n-2)/n

Now I think I know the general formula that applies when n, m and k are sufficiently large. We have to kill 'k' guys, but we do each one in turn. For the first kill, we have an m/n chance of killing a bad guy, which gives us U(n-1, m-1, k-1).
We have an (n-m)/n chance of killing a good guy, which gives U(n-1, m, k-1). So we have:

U(n,m,k) = m/n * U(n-1,m-1, k-1) + (n-m)/n U(n-1, m, k-1)
And I think this applies whenever n>0, m>0 and k>0

Now we need a general formula for U(n,m,0). This will be more difficult.

I plugged the above rules into mathematica, and got a different matrix to yours for n=4. It's not complete, because we haven't found all the rules. But you might want to check your working out.

[PWrong]

Ok, I'll make a summary of what we have so far. Some of these rules may be redundant, but this is what I've plugged into mathematica.

V(0, m) = 0
U(0, m, k) = 0
U(1, m, 0) = 1
U(1, m, 1) = 0
U(n, 0, k) = n - k

U(n,m,k) = m/n * U(n-1,m-1, k-1) + (n-m)/n U(n-1, m, k-1)
whenever n>0, m>0 and k>0

We can also work out that
U(3,3,0) = 0
U(4,3,0) = 1
U(4,4,0) = 0

I plugged these into mathematica and found the three matrices for n=2,3,4

Code: Select all

Two AI's
|0  1  2
-----------
0|2  1  0
1|1  1  0
2|0  1  0

Three AI's
|0   1   2  3
--------------
0|3   2   1  0
1|1  4/3  1  0
2|1  2/3  1  0
3|0   0   1  0

Four AI's
| 0    1   2   3  4
--------------------
0| 4    3   2   1  0
1|4/3  3/2 3/2  1  0
2|10/9  1   1   1  0
3| 1   3/4 1/2  1  0
4| 0    0   0   1  0


The n=4 matrix is quite a lot different from yours, so one of us is wrong.

I'll try to work out U(n,3,0). Remember that evil guys can kill each other simultaneously. However, two bad guys can't kill the same guy simultaneously. Basically, if there are three evil guys, we simply pick three guys at random to die.

Let's look at U(5,3,0). Call them a,b,c,d,e. a & b are good, and c,d,e are evil. We have to pick two of them to survive. I list the possible combinations, along with the number of surviving evil guys.

Code: Select all

ab, ac, ad, ae, bc, bd, be, cd, ce, de
0 , 1 , 1 , 1 , 1 , 1 , 1 , 2 , 2 , 2

There are (5 choose 3 = 10) possible combinations.
U(5,3,0) = 1/10 V(2,0) + 6/10 V(2,1) + 3/10 V(2,2)

Now I'll try U(6,3,0). Call them a,b,c,d,e,f and let a,b,c be the good ones. Again, we have to pick three to survive.

abc, abd, abe, abf, acd, ace, acf, ade, adf, aef,
bcd, bce, bcf, bde, bdf, bef,
cde, cdf, cef,
def

3, 2, 2, 2, 2, 2, 2, 1, 1, 1,
2, 2, 2, 1, 1, 1,
1, 1, 1,
0

p(m=3) = 1/20
p(m=2) = 9/20
p(m=1) = 9/20
p(m=0) = 1/20

I would have been able to figure this out two years ago, but I've forgotten everything from applicable maths.

[moonlord]

None of us is wrong because we're playing by different rules. I allow more than one evil guy to kill the same guy at the same round. That is, one possible evolution of GGEEE: GGEEE -(all evil kill one good)> GEEE -(one evil kill the good, the other evils kill the first evil)> EE -(kill each other)> 0.

So should we allow victim sharing?

If we don't, then the problem comes a lot simpler, as you pointed out. If we do, then...

GEEE/K0 possibilities: 3^3 = 27.

possible outcomes after a round:
G (all three guys kill each other) - two possibilities, clockwise and anticlockwise
GE (two guys kill each other, and the third kills one of them - one victim is shared) - 6 possibilities (three for the first two, two for the third's choice)
GE (one kills another, which kills another, which kills the good guy) - 6 possibilities
GEE is not obtainable. The dude to be killed must kill one of the others.
GEEE is not obtainable. We want blood, so we force them to kill.
E (two guys kill each other, and the third kills the good guy) - three possibilities (three for the first two, the third's choise is restricted)
EE seems difficult so I'll consider it later.
EEE (all three kill the good) - one possibility

Therefore EE has 27-(2+12+3+1)=10 possibilities.
U(4,3,0) = 2/27 * 1 (G) + 12/27 * 1 (GE becomes E after another round) + 3/27 * 1 (E) + 10/27 * 0 (EE) + 1/27 * 3/4 (U(3,3,0) = 3/4) = 17.75 / 27 = 71/108. This value is not much different from 47/108 so I suspect this is also wrong. I overlooked 6/12 possibilities for getting GE before, so I wouldn't be surprised if I've overlooked some more. Maybe you can count the possibilities that EE is the result and see if it matches with mine.

[Keiji]

Without victim sharing (that sounds very evil, lol):

GGEEE -> (2 Es kill 2 Gs, other E kills an E) -> EE -> (kill each other) -> 0

So it doesn't make a difference in that situation...

[moonlord]

Yes but E's choose their victim randomly. That is, three of them can kill themselves in the first round and the two good AI's survive. The question is, what are the chances of this happening?

I've computed something for round zero (with victim sharing) - this is when the God kills people randomly.

If k<=m and k<=n-m then the chance that i E's survive p(i) = C[n-m,i] * C[m,k-i] / C[n,k-i]. If one wills, I can prove this. m, n and k have their usual meaning.

EDIT: My table for three AI's says U(3,2,0) = 3/4 and U(3,3,0) = 3/4, and I suspect these differences arise from victim sharing.

[Nick]

@PWRONG: What do the rows and columns of your tables mean? I am confused by this.

[Keiji]

The number on the left is how many evil AIs there are.

The number on the top is how many you kill.

[PWrong]

I'll try to work out U(n,3,0). Remember that evil guys can kill each other simultaneously. However, two bad guys can't kill the same guy simultaneously. Basically, if there are three evil guys, we simply pick three guys at random to die.

I just realised this is wrong. An evil guy can't kill himself.

Ok, we're looking at n guys, 3 of which are evil, without victim sharing. Each evil guy has n-1 potential victims, 2 of which are evil. So the chance of him killing an evil guy is 2/(n-1), and the chance of him killing a good guy is (n-3)/(n-1)

The chance of the three evil guys killing each other simultaneously is 2/(n-1)*2/(n-1)*2/(n-1)

The chance of the first two evil guys killing an evil, but the third one killing a good guy is 2/(n-1)*2/(n-1)*(n-3)/(n-1)
This can happen in a different order, so the chance of two evil guys dying is 3*2*2*(n-3)/(n-1)^3

The chance of the first evil guy killing an evil, but the other two killing good guys is 2/(n-1)*(n-3)/(n-1)*(n-3)/(n-1).
Again, this can happen in three different orders, so the chance of one evil guy dying is:
3*2*(n-3)^2 / (n-1)^3

Finally the chance of all three killing good guys is (n-3)^3 / (n-1)^3.

Now I can see the pattern. There's always a Pascal's triangle hidden somewhere in these problems. Let x = 2/(n-1), y = (n-3)/(n-1)
Then U(n,3,0) = x^3 V(n-3, 0) + 3 x^2 y V(n-3,1) + 3 x y^2 V(n-3,2) + y^3 V(n-3,3)

Now I'm not sure if this always applies, or if it only works for n>5. For n=5, we get V(2,3) in the answer, which doesn't make sense. We have a similar problem with U(n,2,0). We'll have to look more closely at U(n,3,0) and U(n,2,0) for small n.

[moonlord]

How about we first choose whether victim sharing is allowed or not. That way, we'll both talk about the same thing.

[PWrong]

Ok. I'd prefer to disallow victim sharing, simply because victim sharing is more complicated. We'll assume that bad guys are smart enough not to kill someone who's already being killed.

[Keiji]

The chance of the three evil guys killing each other simultaneously is 2/(n-1)*2/(n-1)*2/(n-1)

= 8(n-1)^-3

The chance of the first two evil guys killing an evil, but the third one killing a good guy is 2/(n-1)*2/(n-1)*(n-3)/(n-1)
This can happen in a different order, so the chance of two evil guys dying is 3*2*2*(n-3)/(n-1)^3

= 12(n-3)(n-1)^-3

The chance of the first evil guy killing an evil, but the other two killing good guys is 2/(n-1)*(n-3)/(n-1)*(n-3)/(n-1).
Again, this can happen in three different orders, so the chance of one evil guy dying is: 3*2*(n-3)^2 / (n-1)^3

= 6(n-3)²(n-1)^-3

Finally the chance of all three killing good guys is (n-3)^3 / (n-1)^3.

= (n-3)³(n-1)^-3

[jinydu]

This discussion about the AI problem is distinct from the original discussion about utility functions; so I've split it into a separate thread.

[Keiji]

Which usually deserves a tag at the bottom of the first post, not an extra post

[Nick]

I started doing 5, but quickly I came to an impass:

Let's say we have GGGGE: if I kill two of them, what are the odds of killing the E? Is it 2/5, or is it 1/5 + 1/4? Do I kill two random people simultaneously or not?

[Keiji]

I started doing 5, but quickly I came to an impass:

Let's say we have GGGGE: if I kill two of them, what are the odds of killing the E? Is it 2/5, or is it 1/5 + 1/4? Do I kill two random people simultaneously or not?

It's 1/5 + 1/4. If you were to kill two people simultaneously, you wouldn't kill one person twice, so it would be the same as if you killed them seperately.

[Nick]

I started doing 5, but quickly I came to an impass:

Let's say we have GGGGE: if I kill two of them, what are the odds of killing the E? Is it 2/5, or is it 1/5 + 1/4? Do I kill two random people simultaneously or not?

It's 1/5 + 1/4. If you were to kill two people simultaneously, you wouldn't kill one person twice, so it would be the same as if you killed them seperately.

Damn. That makes it so much more complicated

edit: OK, let me just see if I'm doing this right:
For GGGGE:
U(K2)=[(1/5 + 1/4)*4] + [(4/5 + 3/4)] * 1) = (9/20 * 4) + (31/20) = 33/10

Something tells me that's not right... :?

[moonlord]

U(K2)=[(1/5 + 1/4)*4] + [(4/5 + 3/4) * 1] = (9/20 * 4) + (31/20) = 33/10

Bold: It's not correct this way. You can either remain with GGG or with GGE (two possible results). The chances for GGG are 1/5 + 1/4 as you pointed out, therefore the chances for anything else (in this case, GGE) are 1 - 9/20 = 11/20.

Thus, U(5,1,2) = 9/20 * 3 + 11/20 * 1 = 38/20 = 1.9

U(3,0,0) = 3, not 4.

However your post was indeed constructive. I've realised I don't have to mess with those combinations to compute the probability for every possible result of round 0.

U(n,m,k), p(i) is the probability that i evil AI's are killed.

k=1:
p(0) = (n-m)/n
p(1) = m/n
Sum = 1

k=2:
p(0) = (n-m)/n * (n-m-1)/(n-1)
p(1) = (n-m)/n * m/(n-1)
p(2) = m/n * (m-1)/(n-1)
Sum = [ (n-m)(n-m-1) + m(n-m) + m(m-1) ] / n(n-1) = [ (n-2)(n-1) + m(m-1) ] / n(n-1) = ( n² - 3n + 2 + m² - m ) / n(n-1). Now why isn't Sum = 1?

[PWrong]

It's 1/5 + 1/4. If you were to kill two people simultaneously, you wouldn't kill one person twice, so it would be the same as if you killed them seperately.

Uh oh. That means we'll have to go through the whole matrix again.

p(1) = (n-m)/n * m/(n-1)

Here's your problem. This is the probability that the second AI is evil, but not the first. The probability that the 1st is evil, but not the 2nd is m/n * ((n-1) - (m-1))/(n-1) = m/n*(n-m)/(n-1). Now the probability of exactly one being evil is the sum of these.

p(1) = (n-m)/n*m/(n-1) + m/n*(n-m)/(n-1)

When you add these up they do sum to one.

[Nick]

I'll let you guys do this stuff... its way too confusing.

[Keiji]

I could make a program in Python to figure this out...

[moonlord]

Hey I'm stupid. I realised the situations should give the same formula, but didn't add them.

So you say if p(0) = 2 * m(n-m) / n(n-1) then Sum = 1...

k=2:
p(0) = (n-m)(n-m-1) / n(n-1)
p(1) = 2 * m(n-m) / n(n-1)
p(2) = m(m-1) / n(n-1)

Sum = [ (n-m)(n-m-1) + 2m(n-m) + m(m-1) ] / n(n-1) = ...paper work... = 1 yeeey.

[PWrong]

Hey I'm stupid. I realised the situations should give the same formula, but didn't add them.

You're not stupid. My mistake was a lot worse (the one irockyou pointed out).

So we need to define this new function, p(n, m, k, e), where e is the number of evil guys killed. I'll often abbreviate this as p(k,e). I'll try doing it with mathematica. It looks like we need a sum of products.

Watch this trick. First we notice that two forms keep popping up:
((n-i) - (m-j)) / (n-i) whenever a good guy is killed, and
(m-j)/(n-i) whenever an evil guy is killed.

Define g(i, j) = ((n-i) - (m-j))/(n-i)
and e(i,j) = (m-j) / (n-i)

Now here's our definitions up to k=3. I copied this from my mathematica notebook, hence the square brackets.

p[1, 0] = g[0, 0]
p[1, 1] = e[0, 0]

p[2, 0] = g[0, 0]g[1, 0]
p[2, 1] = g[0, 0]e[1, 0] + e[0, 0] g[1, 1]
p[2, 2] = e[0, 0] e[1, 1]

p[3, 0] = g[0, 0] g[1, 0] g[2, 0]
p[3, 1] = e[0, 0] g[1, 1] g[2, 1] + g[0, 0] e[1, 0] g[2, 1] + g[0,0] g[1, 0] e[2, 0]
p[3, 2] = e[0, 0] e[1, 1] g[2, 2] + e[0, 0] g[1, 1] e[2, 1] + g[0, 0] e[1, 0] e[2, 1]
p[3, 3] = e[0, 0] e[1, 1] e[2, 2]

Now we can see the pattern, including old pascal hiding away in the number of summands. Working out a formula or an algorithm will be difficult though.

[moonlord]

I'm afraid I can't follow. What are i and j? I mean, I see what they are, but how do they pop in?

[PWrong]

'i' is the number of people you've killed so far. It's also the number you subtract from n.
'j' is the number of evil people you've killed so far. It's the number you subtract from m.

For instance: p(2,0) = g[0,0] g[1,0] = ((n-0)-(m-0))/(n-0) * ((n-1)-(m-0))/(n-1) = (n-m)/n * (n-m-1) / (n-1)

Here, in the first term of the product, i=0 and j=0
In the second term, i=1 and j=0.

Does that help?