Mafia Probabilities

[mith]

I think like 8 different people are working on this, and we've started discussing it in VG, so I figured I'd make a thread for it. What we're trying to do is make a program to calculate probabilities for each side winning with different starting conditions for a Mafia game. Here's my current program:

code:

---

#include <stdio.h>


#include <stdlib.h>





float f(int, int, int, int, int, int, int, int);





int main()


{


	float prob;


	


	int n, m, c;





	for (n=4;n<21;n=n+2)


	{


		for (m=1;m<4;m++)


		{


			for (c=0;c<2;c++)


			{


				prob=f(n, m, c, 0, 0, 0, 0, 0);


				printf("%d, %d, %d, %8.3f\n",n,m,c,prob);


			}


		}


	}


	return 1;


}








float f(int n, int m, int c, int dn, int im, int it, int rm, int rt)


{


	float x, y;


	


	if (it<0) return 0;


	if (im<0) return 0;


	if (m==0) return 1;


	if (m>=(n-m)) return 0;


	if (dn==0)


	{


		if (c==0)


		{


			if (rt==0) return f(n-1,m,0,1,0,0,rm,0);


			else return f(n-1,m,0,1,0,0,rm,rt-1);


		}


		else return ((n-m-it-1)*f(n-1,m,0,1,0,0,0,0) + 


		(m-im)*it*f(n-1,m,1,1,im+1,it-1,0,0) + 


		(m-im)*(n-m-it-1)*f(n-1,m,1,1,im+1,it,0,0) + 


		(n-m-it-1)*(it+1)*f(n-1,m,1,1,im,it,0,0) + 


		(n-m-it-1)*(n-m-it-2)*f(n-1,m,1,1,im,it+1,0,0))/(n-m)/(n-im-it-1);


	}


	else


	{


		if (c==1)


		{


			x=f(n,m,0,1,0,0,im,it);


			y=(f(n,m,0,1,0,0,im,it) + 


			im*f(n-1,m-1,1,0,im-1,it,0,0) + 


			(m-im)*f(n-1,m-1,1,0,im,it,0,0) + 


			it*f(n-1,m,1,0,im,it-1,0,0) + 


			(n-m-it-1)*f(n-1,m,1,0,im,it,0,0))/n;


			if (x>y) return x;


			else return y;


		}


		else


		{


			if (rm>0) return f(n-1,m-1,0,0,0,0,rm-1,rt);


			else return ((n-rt-m)*f(n-1,m,0,0,0,0,0,rt)/(n-rt) + 


			m*f(n-1,m-1,0,0,0,0,0,rt)/(n-rt));


		}


	}


}

---

It works fine without cops, and it works fine for small games with one Cop, but it's giving a weird output (-1.#IO) for bigger games with a Cop. Any ideas? And any thoughts on how to get it to do more than one Cop, multiple families, or other things like that?

[Da5id]

Is that C++? I don't recognize (some of) the syntax. I imagine that would be difficult to do using VB syntax?

[This message has been edited by Da5id (edited 05-05-2002 04:54 PM).]

[Bicho the Inhaler]

That's definitely C. I would help, but I know very little about mafia.

[jeep]

I just created a thread over on your site to discuss this too. Oh well, this will work.

[jeep]

Hmm, well, I'm changing some variables to make it more readable for me. I can't follow all this n, m, etc. mith, I'll send it to you, let me know if my changes look accurate.

-JEEP

[CrystyB]

Jeep, just save your version, then do a replace-all thing BACK and compare the result with the initial (posted) program. And could you please post your variant of the code here too? i'm lazy tonight...

[jeep]

C: I'm more concerned about if I interpreted things correctly, not if my replacements were correct.

I'll cut and paste, but it's gonna wrap and look terrible, I'm sure:

code:

---

#include <stdio.h>


#include <stdlib.h>





#define day 1


#define night 0





float f(int, int, int, int, int, int, int, int);





void main()


{	


	float prob;		


	int n, m, c;	


	





//	prob=f(10, 1, 1, 0, 0, 0, 0, 0);	


	for (n=4;n<21;n=n+2)	


	{		


		for (m=1;m<4;m++)		


		{			


			for (c=0;c<2;c++)			


			{				


				prob=f(n, m, c, 0, 0, 0, 0, 0);				


				printf("%d, %d, %d, %8.3f\n",n,m,c,prob);			


			}		


		}	


	}	





}








float f (int living, int mafia, int cops, 


		 int dn, 


		 int investigatedMafia, int investigatedTownie, 


		 int revealedMafia, int revealedTownie)


{	





	float x, y;	





	int concealedTownies,


			nonMafia,


			concealed ;	





	float	total_prob,


		    p_copkilled,


			p_foundMafia_investTownieKilled,


			p_foundTownie_investTownieKilled,


			p_foundMafia_ConcealedTownieKilled,


			p_foundTownie_ConcealedTownieKilled;


	





	if (investigatedTownie<0) return 0;	


	if (investigatedMafia<0) return 0;





	// No mafia left so town wins


	if (mafia==0) return 1;	





	// Mafia has majority so Mafia wins


	if (mafia>=(living-mafia)) return 0;	





	


	if (dn==night)	


	{		


		if (cops==0)		


		{		


			// kill a revealed townie, otherwise kill randomly


			if (revealedTownie==0) return f(living-1,mafia,cops,day,0,0,revealedMafia,0); // yes, cops is zero...





			else return f(living-1,mafia,cops,day,0,0,revealedMafia,revealedTownie-1);	// revealed townie gets killed


		}		


		else // there is a cop


		{


			concealedTownies = living-mafia-investigatedTownie-cops;


			nonMafia = (living - mafia);


			concealed = (living-investigatedMafia-investigatedTownie-1);





			p_copkilled = concealedTownies*f(living-1,mafia,cops-1,day,0,0,0,0) ;


			p_foundMafia_investTownieKilled = (mafia-investigatedMafia) * investigatedTownie * f(living-1,mafia,cops,day,investigatedMafia+1,investigatedTownie-1,0,0);


			p_foundMafia_ConcealedTownieKilled = (mafia-investigatedMafia) * concealedTownies * f(living-1,mafia,cops,day,investigatedMafia+1,investigatedTownie,0,0);


			p_foundTownie_investTownieKilled = concealedTownies * (investigatedTownie+1)*f(living-1,mafia,cops,day,investigatedMafia,investigatedTownie,0,0);


			p_foundTownie_ConcealedTownieKilled = concealedTownies * (concealedTownies-1)


						* f(living-1,mafia,cops,day, investigatedMafia,investigatedTownie+1,0,0);





			total_prob =( p_copkilled 		


						+ 	p_foundMafia_investTownieKilled + p_foundTownie_investTownieKilled 


						+  p_foundMafia_ConcealedTownieKilled + p_foundTownie_ConcealedTownieKilled


						)/nonMafia/concealed;





			return total_prob;	


		}


	}	


	else // must be day then...


	{		


		if (cops==1) 		


		{			


			// p[town win] if cop reveals


			x=f(living,mafia,cops-1,night,0,0,investigatedMafia,investigatedTownie);			





			// p[town win] if cop does not reveal


			y=(f(living,mafia,cops-1,night,0,0,investigatedMafia,investigatedTownie) + 


				investigatedMafia*f(living-1,mafia-1,cops,night,investigatedMafia-1,investigatedTownie,0,0) + 


				(mafia-investigatedMafia)*f(living-1,mafia-1,cops,night,investigatedMafia,investigatedTownie,0,0) + 


				investigatedTownie*f(living-1,mafia,cops,night,investigatedMafia,investigatedTownie-1,0,0) + 


				(living-mafia-investigatedTownie-1)*f(living-1,mafia,1,0,investigatedMafia,investigatedTownie,0,0))/living;			





			if (x>y) return x;			


			else return y;		


		}		


		else // only works with one cop, so for now, this means no cops


		{			


			// town lynches KNOWN mafia if possible


			if (revealedMafia>0) return f(living-1,mafia-1,cops,night,0,0,revealedMafia-1,revealedTownie);


			else 


				return ((living-revealedTownie-mafia)*f(living-1,mafia,0,0,0,0,0,revealedTownie)/(living-revealedTownie) + 			


				mafia*f(living-1,mafia-1,0,0,0,0,0,revealedTownie)/(living-revealedTownie));		


		}


	}


}

---

[edit - added code tags. Unfortunately, this will probably mess up the page width, so I've got some more editing ahead of me ]

[This message has been edited by mole (edited 05-06-2002 03:25 AM).]

[jeep]

Holy missing indentation Batman! Well, if you use a good editor, you should be able to tabify the code...

-JEEP

[Antrax]

Quite. BTW, should we use this thread or the one over on the mafiascum.net site?
Antrax

------------------
I'm cool, really

[Werebear]

?puzzled look? I saw you post this in the middle of the Bladerunner mafia game, went back the next day to get it, and it was gone! now it's here, and everyone's hacking at it. *chuckle* All for the best, my C++ install CD is apparently packed in a box somewhere. Ah, the joys of moving.

Werebear

[jeep]

Antrax, if mafiascum was more stable, I would suggest it, but given the problems lately, I think this is the best choice.

-JEEP

[jeep]

Thanks mole. I should have noticed that I got rid of the tags. I must have pasted over them and never noticed that was why the indentation was screwy.

-JEEP