The "Good AI, Bad AI" Problem

[moonlord]

'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.

This clears up things.

For instance: p(1,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)

Are you sure about this? p(1,0) means you kill a good. p(1,0) = (n-m) / n by my derivations. p(2,0) by my derivations seems to be the same with your p(1,0). Maybe...

[PWrong]

Are you sure about this? p(1,0) means you kill a good. p(1,0) = (n-m) / n by my derivations. p(2,0) by my derivations seems to be the same with your p(1,0). Maybe...

You're right, I meant p(2,0). I'll go edit it.

[moonlord]

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.

Well, I see why Pascal's triangle shows up. In my derivation, I used combinations heavily, so it's no surprise. I don't see why the results should be EXACTLY the above. It's a pity Mathematica does not explain them. Maybe giving the results for K4 and K5 might help.

EDIT: I've figured out now. How stupid of me again. I should've seen earlier that g and e are probability functions. So it takes all the situations. Like, for p(3,2), killing (in order) EGG, GEG and GGE. Now guess how many possible situations are there? Yep, combinations and Pascal's triangle again. Joy!

So let me give K4:

p(4,0) = g(0,0) g(1,0) g(2,0) g(3,0) [2nd term is always 0 because we kill no evil]
p(4,1) = e(0,0) g(1,1) g(2,1) g(3,1) + g(0,0) e(1,0) g(2,1) g(3,1) + g(0,0) g(1,0) e(2,0) g(3,1) + g(0,0) g(1,0) g(2,0) e(3,0)
... this gets boring ...
p(4,4) = e(0,0) e(1,1) e(2,2) e(3,3)

Good. Now let's see how we write this as an algorithm.

[PWrong]

Ok, I think I can sketch a rough formula. First, let f(0, i, j) = g(i,j) and f(1,i,j) = e(i,j). The reason for this will become clear.

Now, let S(n,m) be the set of permutations (reorderings) of m 1's and n-m 0's.
i.e. S(5,3) is the set of permutations of (1,1,1,0,0)
Let A be one of these permutations. We have to sum over all A in S.
For instance, let A = (0,1,1,0,1). We use subscripts for the a'th element of A. So A₂ = 1

Now the thing that we're summing is the function f(A_a, the number of evil guys so far, the number of people so far).

The number of evil guys so far is just the sum of A_a from 1 to a-1. That's why we let evil be represented by 1, and good by 0.

That is, f(A_a, Sum (over b from 1 to a-1) of A_a, a)

Then our p function will look like this:
Sum over all A in S:
Product over a, from 1 to n:
f( A_a, Sum[b, 1 to a-1, A_a], a)

Does that all make sense?

[PWrong]

I just realised it's a lot simpler than that. You already noticed this.

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

For n=3, it's actually just:

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

[moonlord]

Well, that is a change in the wind. Now the coefficients are determined by combinations (aka, choose x from y) where x = e and y = k (the number of AI's you kill, and the number of evil AI's that die). And that brings Pascal's triangle again into play...

So k=4 becomes:

p(4,0) = g(0,0) g(1,0) g(2,0) g(3,0)
p(4,1) = 4 g(0,0) g(1,0) g(2,0) e(3,0)
p(4,2) = 6 g(0,0) g(1,0) e(2,0) e(3,1)
p(4,3) = 4 g(0,0) e(1,0) e(2,1) e(3,2)
p(4,4) = e(0,0) e(1,1) e(2,2) e(3,3)

I put the e's last because I believe that simplifies the formulas. It's just a feeling...

[PWrong]

I put the e's last because I believe that simplifies the formulas. It's just a feeling...

Well, I worked out a formula that puts the e's first. There's probably a similar formula with the e's last.

I was going to use p(k,e) for the probability, but that's potentially confusing, so I'll just use p(k,x). x is the number of evil guys killed.

p(k,x) = (k choose x) * product[ {i from 0 to (x-1)}, e[i,i] ] * product[ {i from p to (k-1)}, g[i,x] ]

I just realised this doesn't matter much. As Rob said before:

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.

But my earlier recurrance relation killed them seperately anyway.
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

Oh well, this might still be useful for when the evil AI's attack each other.

[moonlord]

I worked the formula for goods first while taking a test in physics

p(m,n,k,e) = C(k,e) * Product[0<=i<=k-e-1] of G(i,0) * Product[k-e<=i<=k-1] of E(i,i+e-k), where G and E have replaced the probability functions g and e.

There is a note of warning though. This only holds if we have k>=m and k>=n-m. Otherwise we might end with negative probabilities.

[PWrong]

I worked the formula for goods first while taking a test in physics

I'm glad you've got your priorities sorted . Did you finish the test first?

p(m,n,k,e) = C(k,e) * Product[0<=i<=k-e-1] of G(i,0) * Product[k-e<=i<=k-1] of E(i,i+e-k), where G and E have replaced the probability functions g and e.

It looks right .

There is a note of warning though. This only holds if we have k>=m and k>=n-m. Otherwise we might end with negative probabilities.

That can't be good. So either there's a mistake somewhere, we need another formula, or it's always the case that k>=m and k>=n-m.

Maybe we should go back to the old recurrence relation (since we know it works now), and try to figure out the next step (evil guys killing each other).

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

All we need is a new formula for U(n,m,0).
Since an evil guy can't kill himself, we reduce n and m by one, then we kill one of the remainder at random. So is it possible that U(n,m,0) = U(n-1, m-1, 1) for m>1? It's not, because we have to somehow add the evil guy back in afterwards, and include the fact that he's already made his kill. It seems that murder is an entirely different operation to execution, and they can't be converted. Maybe we need a new variable to keep track of how many murders we've had. This terminology makes them seem more human in every post.

[moonlord]

I worked the formula for goods first while taking a test in physics

I'm glad you've got your priorities sorted . Did you finish the test first?

I... well... kinda mixed them up...

There is a note of warning though. This only holds if we have k>=m and k>=n-m. Otherwise we might end with negative probabilities.

No, I don't think we need another formula. We just have to make some extra tests.

if (k>n-m) for (i=0; i<n-m-k; i++) p(n,m,k,i) = 0;

I believe this suffices.

[PWrong]

if (k>n-m) for (i=0; i<n-m-k; i++) p(n,m,k,i) = 0

Why does it equal 0? Do the probabilities still sum to 1? :?

[moonlord]

If you have three good and three bad and you kill five, the chance of killing only one or no evil is zero, because you run out of goods. I don't know if it still sums to 1. Will code something today and test it...

[PWrong]

Any luck?

[moonlord]

No, unfortunately. When I actually managed to get a program working, it gave ridiculous answers. Now, I'm in a physics summer school right now and doing a project for it too, so this isn't my first priority. The school will end on the 18th, but it will be the end of my summer holiday. I want to get a firm grasp on mechanics 'till the "regular" school starts. I also need to play with thermodynamics and optics quite a lot. They're not in the school plan for the ninth grade, but I wish to get to the IPhO :p. Slim chances, though.

My problem right now is this: to prove the laws of reflexion and refraction, using Fermat's Principle (between two given points, the light will travel on the trajectory that will require the least time). Relativity is not considered.

Anyway, this is becoming off-topic. I just say I won't have that much time from now on...

EDIT: I have the feeling that they will not add to 1, but we must multiply all of them with a ratio, so that they will sum up to 1. It's just a ... wild guess.

[moonlord]

I've just realised that all the probability calculations that should return zero, but we thought would return something negative, actually return zero. If you kill four people, given there are 3 goods and 3 bads, when you apply one of the equivalent formulas to compute the probability, in one of the products, one term will be zero - either because m=j or n-i=m-j.

So actually it was correct in all situations.

We should anyway test in some way if our formulas actually sum to 1 in the general case. Any ideas?

[PWrong]

It's been a while since I looked at this, and I've forgotten what's going on.

Whenever k>0, we have the formula:
U(n,m,k) = m/n * U(n-1,m-1, k-1) + (n-m)/n U(n-1, m, k-1)

This lets us kill them separately, so the probability formulas are irrelevent.

All we need is a formula for U(n, m, 0). So we have n AI, m of which are evil, and each evil guy kills one other guy at random. The process is as follows:

Reduce n and m by 1.
Kill one guy at random.
Add 1 to n and m.
Repeat for every evil guy.

Maybe we need a new variable to keep track of how many murders we've had.

Let's try this. We'll define a new function P(n,m,d) where d is the number of deaths we've had. This starts at 0, and increases to m. Once we get to m, we start the next turn.

note that U(n,m,0) = P(n,m,m)

If d < m
P(n,m,d) = (m-1)/(n-1) * P(n-1,m-1,d+1) + (n-m)/(n-1) * P(n-1,m,d+1)

If d = m, then we end the turn, so P(n,m,m) = V(n,m).

Here's our final set of rules. We need a lot of initial conditions.

V[n, m] = Max[Table[U[n, m, k], {k, 0, n}]]
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] = If[n > 0 && m > 0 && k > 0,
(m/n) U[n - 1, m - 1, k - 1] + (n - m)/n U[n - 1, m, k - 1]])

U[n, m, 0] = P[n, m, m]

P[n, 0, d] = n
P[1, m, 0] = 1
P[1, m, d] = 0
P[n, m, 0] = V[n, m]
P[n, m, d] = (m-1)/(n-1) P[n-1, m-1, d-1] + (n-m)/(n-1) P[n-1, m, d-1]

When I plugged this into mathematica, I got a different answer for GGEE k0. The new formula gives 1 instead of 10/9. We should look at this one more carefully.

[PWrong]

I've just checked it manually, and 10/9 is correct. So something is wrong with the new formula .

I think we need a separate rule for P when m=0, m=1, and m>1

[papernuke]

Whats an AI? Artificial Inteligence?

[moonlord]

Icon: That's right. We consider small AI's, "lemmings", that do only what we tell them to.

PWrong: I can't follow your post from the "Reduce n and m by 1. Kill one guy at random. Add 1 to n and m. Repeat for every evil guy." I don't understand your algorithm. Do you use victim sharing or not?

It seems afterall that all we need to finish the problem is a formula for U(n,m,0). The general U(n,m,k!=0) recursive formula must give the same results as our non-recursive probability formulas. The latter seem more Turing-machine friendly because recursion takes a hell of a time when used on high values. Maybe we should consider all three.

Am I right till here?

[papernuke]

Whats an AI?

[moonlord]

Icon: Generally, AI comes from "Artificial Intelligence". For the current specific purpose, an AI is an entity, like the lemmings from the games with the same name. They only do whatever we tell them to. In this case, the good AI's do nothing and every evil AI kills a random other AI.

PWrong: I see a problem with the non-victim sharing version. The game must be played on multiple rounds, because if the evil AI's do choose their victims randomly, the other evils cannot know who has been alredy targeted. Each round there is a sole random kill. The problem is when you're left to EE. One would kill the other, but the victim cannot kill the attacker, because we only have a kill per round. So U(EE) = 1 and not zero, as we used until now. So I again suggest we allow victim sharing.

[PWrong]

So I again suggest we allow victim sharing

If we disallow victim sharing, but allow two AI's to kill each other, then we always have exactly one death for every evil guy. There's no other way to do this (unless we allow suicide).

Maybe we should try both ways. I can't seem to work out the correct formula for the non-victim sharing case. The problem is that with the current formula, P(3,1,1) can mean two things. It could mean we have GGE and the evil guy is about to kill someone, or it could mean the evil guy just killed another evil guy, who is about to simultaneously kill someone else.

[moonlord]

If we disallow victim sharing, but allow two AI's to kill each other, then we always have exactly one death for every evil guy.

Then victim choosing wouldn't be completely random. "I want to kill X." "Sorry, X is already taken. Please choose again.". I see two possible ways: turn based and realtime. Turn based can disallow victim sharing, but also it will not let two or more evils kill each other - in a circular fashion. Realtime always allows victim sharing, and two or more evils to kill each other.

Maybe we should try both ways. I can't seem to work out the correct formula for the non-victim sharing case. The problem is that with the current formula, P(3,1,1) can mean two things. It could mean we have GGE and the evil guy is about to kill someone, or it could mean the evil guy just killed another evil guy, who is about to simultaneously kill someone else.

I agree. However, I also can't give the formula for the victim sharing case. I don't understand the P function yet.

[papernuke]

Whoops sorry about the doubble post, I didn't know there was another page so I thought something happened to it and posted again.

[moonlord]

...happens to all of us.

[PWrong]

Then victim choosing wouldn't be completely random. "I want to kill X." "Sorry, X is already taken. Please choose again.". I see two possible ways: turn based and realtime. Turn based can disallow victim sharing, but also it will not let two or more evils kill each other - in a circular fashion. Realtime always allows victim sharing, and two or more evils to kill each other.

You could do it this way. First everyone takes it in turns to choose their victim, with the restriction that two people can't choose the same victim (and you can't kill yourself). Then, everyone fires their gun simultaneously. So choosing is turn-based, but killing is in real-time.

[moonlord]

Yes but it wouldn't be completely random. See the "dialogue" above. "I want to kill X." "Sorry, X is already taken. Please choose again.". But I believe we can live with that. I don't know why, but I have a strong feeling that the computations for the full-realtime version are simpler. I think we should try all the situations.

I still can't understand either your "remove a evil, randomly kill, add a evil" algorithm or the P function. Care to explain or are they obsolete?

[PWrong]

I still can't understand either your "remove a evil, randomly kill, add a evil" algorithm

The algorithm is supposed to prevent suicide. This guy's about to kill someone, so we take him out of the group, let him kill (or just choose) someone else, and then put him back in.

or the P function

The P function should make sure that you can still kill someone even if someone kills you first. But it doesn't seem to be working.

Let's try and update the algorithm. We can write G' or E' to point out that that person is a chosen victim.
Say we start with GGGEEEEE (or {8,5})

1. Revome the first evil guy, so he can choose a victim. GGGEEEE
2. Put a dash next to his chosen victim. GGGE'EEE
3. Put the evil guy back in the group. GGGE'EEEE
4. Repeat for each evil guy. G'G'GE'EE'E
5. Kill everyone with a dash. GEE

Now we have 4 numbers describing the group: the number of G, E, G', and E', respectively.

[moonlord]

Okay, now I understand the algorithm but how can it be used to compute the global utility?

[PWrong]

Ok, let's try a new P function, P(n, m, n', m', d). n' is the number of people with a dash, m' is the number of evil guys with a dash, and d is the number of evil guys who haven't chosen anyone yet.

For a given attacker, the probability that an evil guy is chosen is the number of undashed evil guys (not including the attacker) divided by the number of undashed guys.

Now we have a problem already. If the attacker is undashed, we have to subtract 1 from the number of undashed guys. If he's dashed, we don't. We currently have no way to tell.