Programming Mafia

[jeep]

Well, Antrax, mith, and I have been having some discussion in other, less appropriate forums, so I'm starting this topic to give us a place to discuss.Anyone else writing programs related to mafia?  I have two, one for determining the permutations possible in mini-2 (it's pretty slick) and one for determining the probability of town winning if random voting and night kills occur.  I'm expanding it to handle cops now.-JEEP

[Samadhi]

Wish I knew the syntax, I'd be able to help. ;I don't know any C, just Office stuff.

[jeep]

OK, so here is my adaptation of Mith's code, it now incorporates a cop,
but does not handle a doc. There are some basic assumptions that I
made. Mafia kills cop if they know who he is, etc.

Without a doc, it is always better for the cop to reveal absolutely
everything he knows, but I have the added check in there for
future expansion.

Sorry if this screws with the width of the page.

The hard coded numbers are simply because I used this to analyze the minvitaional game that is going on now.

-JEEP

Code: Select all

// p_<something> refers to the probability of town winning if <something> happens.
//                * the odds something happens

#include "stdafx.h"

#include <stdio.h>
#include <stdlib.h>

#define day 1
#define night 0

long double  f (int, int, int,  int,  int, int, int, int, int, int);
bool   isLegal (int living, int mafia, int cops,  int dn, int investigatedMafia, int investigatedTownie, int revealedMafia, int revealedTownie, int revealedCop, int round);
int findWinner (int living, int mafia, int cops,  int dn, int investigatedMafia, int investigatedTownie, int revealedMafia, int revealedTownie, int revealedCop, int round);

void main()
{	
	long double prob;	

	int n, m, c;	
	

	int round, dn;
	round =1;

	n=9; m=3; c=1; dn=day; 
	
	for (int im=0; im <3; im++)
	{
		for (int it=0; it <3; it++)
		{

			prob=f(n, m, c, dn, im, it, 0, 0, 0, round);				
			printf("%d, %d, %d, %d, %d, %8.3f\n",n,m,c,im, it,prob);	
		}
	}

}


// f returns the probability of town winning given the state of the game
long double f (int living, int mafia, int cops, 
		 int dn, 
		 int investigatedMafia, int investigatedTownie, 
		 int revealedMafia, int revealedTownie, int revealedCop, int round)
{	

	long double x, y, z;	
	int concealedTownies, nonMafia,	concealed, winner ;	
	long double	total_prob,
		    p_killCop,p_killConcealedTownie, p_killRevealedTownie,
			p_foundMafia_investTownieKilled, p_foundTownie_investTownieKilled,
			p_foundMafia_ConcealedTownieKilled,	p_foundTownie_ConcealedTownieKilled,
			p_lynchCop, p_lynchInvestMafia, p_lynchConcealedMafia, p_lynchRevealedMafia, p_lynchInvestTownie, p_lynchConcealedTownie;
	

	if (! isLegal ( living,  mafia,  cops, dn, 
					investigatedMafia,  investigatedTownie, 
				    revealedMafia,  revealedTownie, 
				    revealedCop,  round)) return 0;


	winner = findWinner( living,  mafia,  cops, dn, 
				    investigatedMafia,  investigatedTownie, 
				    revealedMafia,  revealedTownie, 
				    revealedCop,  round);
	if (winner != -1) return winner;


	if (dn==night)	
	{		
		if (cops==0)		
		{		
			// kill a revealed townie, otherwise kill randomly
			if (revealedTownie==0) 
			{
				// only townies left alive, 100% chance of killing one
				p_killConcealedTownie =f(living-1,mafia,cops,day,0,0,revealedMafia,revealedTownie,0, round+1);// yes, cops is zero...
				return  p_killConcealedTownie; // yes, cops is zero...
			}
			else 
			{
				// if there is a revealed Townie and no cop, then kill him
				p_killRevealedTownie = f(living-1,mafia,cops,day,0,0,revealedMafia,revealedTownie-1,0, round+1);
				return p_killRevealedTownie;
			}
		}		

		// there is a cop

		if (revealedCop > 0)
		{
			// if Cop is revealed, kill him.
			p_killCop = f(living-1, mafia, cops-1, day, 0, 0, revealedMafia, revealedTownie, revealedCop-1, round+1);
			return p_killCop;
		}

		concealedTownies = living-mafia-investigatedTownie-cops; 
		nonMafia = (living - mafia);
		concealed = (living-investigatedMafia-investigatedTownie);

		// cop is not revealed
		p_killCop = cops*f(living-1,mafia,cops-1,day,0,0,0,0,0, round+1)/nonMafia ;
		p_foundMafia_investTownieKilled = (long double)(mafia-investigatedMafia)/(concealed-1) * (long double) investigatedTownie/nonMafia * f(living-1,mafia,cops,day,investigatedMafia+1,investigatedTownie-1,0,0,revealedCop, round+1);
		p_foundMafia_ConcealedTownieKilled = (long double)(mafia-investigatedMafia) / (concealed-1) * (long double) concealedTownies/nonMafia  * f(living-1,mafia,cops,day,investigatedMafia+1,investigatedTownie,0,0, revealedCop, round+1);
		p_foundTownie_investTownieKilled = (long double) concealedTownies/(concealed-1) * (long double)(investigatedTownie+1)/nonMafia*f(living-1,mafia,cops,day,investigatedMafia,investigatedTownie+(1-1), 0,0, revealedCop, round+1);
		p_foundTownie_ConcealedTownieKilled = (long double) concealedTownies/(concealed-1) * (long double)(concealedTownies-1)/nonMafia* f(living-1,mafia,cops,day, investigatedMafia,investigatedTownie+1,0,0, revealedCop, round+1);

		total_prob =( p_killCop 		
					+ 	p_foundMafia_investTownieKilled + p_foundTownie_investTownieKilled 
					+  p_foundMafia_ConcealedTownieKilled + p_foundTownie_ConcealedTownieKilled
					);

		return total_prob;	
	}	
	else // must be day then...
	{		
		if (cops==1) 		
		{			
			// cop is revealed
			if (revealedCop > 0)
			{
				if (revealedMafia+investigatedMafia>0)
				{
					// revealed mafia gets lynched if possible
					p_lynchRevealedMafia = f(living-1,mafia-1,cops,night,0,investigatedTownie,revealedMafia-1+investigatedMafia,revealedTownie, revealedCop, round+1);
					return p_lynchRevealedMafia;
				}

				// randomly lynch someone
				// cop doesn't allow revealed townie to be lynched... (don't handle revealing townie explicitly, yet)
				p_lynchConcealedTownie = (long double) (living-revealedTownie-mafia-revealedCop)/(living-revealedTownie)*f(living-1,mafia,cops,night,investigatedMafia,investigatedTownie,revealedMafia,revealedTownie, revealedCop, round+1);
				p_lynchConcealedMafia = (long double) mafia/(living-revealedTownie)*f(living-1,mafia-1,cops,night,investigatedMafia,investigatedTownie,revealedMafia,revealedTownie, revealedCop, round +1);
				return ( p_lynchConcealedTownie+ p_lynchConcealedMafia);
			}

			// cop is hidden

			// p[town win] if cop does not reveal
			p_lynchCop = (long double) cops/living*f(living-1,mafia,cops-1,night,0,0,0,0, revealedCop, round+1);
			p_lynchInvestMafia = (long double) investigatedMafia/living *f(living-1,mafia-1,cops,night,investigatedMafia-1,investigatedTownie,0,0, revealedCop, round+1);
			p_lynchConcealedMafia = (mafia-investigatedMafia)*f(living-1,mafia-1,cops,night,investigatedMafia,investigatedTownie,0,0, revealedCop, round+1)/living;
			p_lynchInvestTownie = investigatedTownie*f(living-1,mafia,cops,night,investigatedMafia,investigatedTownie-1,0,0, revealedCop, round+1)/living;
			p_lynchConcealedTownie = (living-mafia-investigatedTownie-cops)*f(living-1,mafia,cops,night,investigatedMafia,investigatedTownie,0,0, revealedCop, round+1)/living;

			y=( p_lynchCop + p_lynchInvestMafia + p_lynchConcealedMafia + p_lynchInvestTownie + p_lynchConcealedTownie);	


			// p[town win] if cop reveals everything-- same round, so call it the same
			x=f(living,mafia,cops,day,0,0,investigatedMafia,investigatedTownie, revealedCop+1, round);		
			
			// p[town win] if cop reveals only mafia
			z=f(living,mafia,cops,day,0,investigatedTownie,investigatedMafia,0, revealedCop+1, round);		


			// assume cop makes the right decision
			if ((x>=y) && (x>=z))
			{
				if (round < 2)
				{
					printf ("REVEAL: %8.3f:%8.3f:%8.3f\n", x,y,z);
				}
				return x;
			}
			
			if ((y>=x) && (y>=z))
			{
				if (round < 2)
				{
					printf ("DON'T REVEAL: %8.3f:%8.3f:%8.3f\n", x, y, z);
				}
				return y;		
			}
			
			if ((z>=x) && (z>=y))
			{
				if (round < 2)
				{
					printf ("REVEAL Mafia: %8.3f:%8.3f:%8.3f\n", x, y, z);
				}
				return z;		
			}
		}		
		
		// 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, revealedCop, round+1);
		else 
		{
			// yes cops should == 0
			p_lynchConcealedTownie=(living-revealedTownie-mafia)*f(living-1,mafia,cops,night,0,0,revealedMafia,revealedTownie, revealedCop, round + 1)/(living-revealedTownie);
			p_lynchConcealedMafia=mafia*f(living-1,mafia-1,cops,night,0,0,revealedMafia,revealedTownie, revealedCop, round +1)/(living-revealedTownie);
			return ( p_lynchConcealedTownie+ p_lynchConcealedMafia);		
		}
	}
}



// isLegal: takes same input as f and returns true if inputs are legal
//          returns false if we should never be able to have this.

bool isLegal (int living, int mafia, int cops, 
		 int dn, 
		 int investigatedMafia, int investigatedTownie, 
		 int revealedMafia, int revealedTownie, int revealedCop, int round)
{
	bool rv;

	rv=true;

	// NONE of these situations are legal
	if (living < 0) 
	{
//		printf ("No one is alive!\n");
		rv=false;
	}
	if (mafia < 0 || mafia>living) 
	{
//		printf ("mafia: %d\tliving: %d\n", mafia, living);
		rv=false;
	}
	if (cops < 0 || cops >1) 
	{
//		printf ("Cops: %d\n", cops);
		rv=false;
	}
	if (dn != night && dn != day) 
	{
//		printf ("Uh... what the hell time of day is %d\n", dn);
		rv=false;
	}
	if (investigatedMafia>mafia || investigatedMafia< 0) 
	{
//		printf ("mafia: %d\tinvestigatedMafia: %d\n", mafia, investigatedMafia);
		rv=false;
	}
	if (investigatedTownie<0 || investigatedTownie> (living-mafia-cops)) 
	{
//		printf ("investigated Townies: %d\tTownies: %d\n", investigatedTownie, (living-mafia-cops));
		rv=false;	
	}
	if (revealedMafia<0 || revealedMafia > mafia) 
	{
//		printf ("mafia: %d\trevealedMafia: %d\n", mafia, revealedMafia);
		rv=false;
	}
	if (revealedTownie<0 || revealedTownie > (living-mafia-cops)) 
	{
//		printf ("revealedTownie Townies: %d\tTownies: %d\n", revealedTownie, (living-mafia-cops));
		rv=false;
	}
	if (revealedCop>1 || revealedCop<0) 
	{
//		printf ("revealedCop: %dn", revealedCop);
		rv=false;
	}

	if (rv == false)
	{
//		printf ("Found illegal situation\n");
//		printf("%d %d %d %d %d %d %d %d %d %d\n", living, mafia, cops, dn, investigatedMafia,investigatedTownie, revealedMafia, revealedTownie, revealedCop, round);
	}
	return rv;
}


int findWinner(int living, int mafia, int cops, 
		 int dn, 
		 int investigatedMafia, int investigatedTownie, 
		 int revealedMafia, int revealedTownie, int revealedCop, int round)
{
	// No mafia left so town wins
	if (mafia==0) 
	{
//		printf("Town wins by killing all\n");
		return 1;	
	}
	// Mafia has majority so Mafia wins
	if (mafia>=(living-mafia)) 
	{
//		printf("Mafia wins by majority\n");
		return 0;	
	}
	
	// Cop found majority, so town wins, no need to finish this
	if (dn==day && ((revealedTownie + revealedCop) >= (living/2)))
	{
//		printf("Town wins by majority\n");
		return 1;
	}

	// Cop knows everything
	if (dn==day && (investigatedMafia + investigatedTownie + cops) >= (living -1))
	{
		return 1;
	}

	// Cop found all mafia, so town wins, no need to finish
	// this must be after mafia has half majority
	if (dn==day && (investigatedMafia == mafia))
	{
		return 1;
	}

	return -1; // no winner yet.
}

[Antrax]

Jeep, could you email me this source? I've looked over it briefly and I think some optimizations could be made. Plus my stupid program won't be useful for much longer, as more and more complex problems surface.
Antrax

[jeep]

sent. As I said in the e-mail, this can surely be optimized. Mostly, I took Miths code, changed variables so I could understand it, and then fixed the bugs I saw.

-JEEP

[Cadmium]

Hey, that's a coincidence .

I just started on programming something for the mafia games. I tried to look up the source code posted on the GL yesterday, but couldn't find them. Then I remembered this thread and looked here, but no code. And now Jeep posts his new code. Great .

Let me know if there's anything I can do to help out. I must warn you, though. I'm only programming in C++ lately. So I might be a bit rusty in programming C .

[jeep]

No problem, I'm using C++... ok, so I haven't used any constructs that aren't availble in C...

Anyway, I was thinking about moving to some OOP data structures... something like this (this is just off the top of my head, so forgive any syntax errors and incompleteness). This would make the tree bigger, but more flexible:

class living {
char * investigatedBy[MAXCOPS];
bool revealed

}

class townie : living {
// stuff
}

class cop : townie {
// stuff
}

class doc : townie {
// stuff
}

class mafia : living {
// stuff
}

[ralphmerridew]

Hey jeep, could you add some linebreaks to your code? Some long lines make the screen scroll horizontally.

[jeep]

If someone wants to take the time, they can add the breaks and send me the revised code to post. For now, however, I'm satisfied with my apology about it screwing with the width...

If it bugs enough people I'll delete the program and have people request it via e-mail.

-JEEP