My Math Forum  

Go Back   My Math Forum > Science Forums > Computer Science

Computer Science Computer Science Forum


Reply
 
LinkBack Thread Tools Display Modes
October 29th, 2007, 12:15 PM   #1
Senior Member
 
Joined: Dec 2006

Posts: 1,111
Thanks: 0

Riddle of the shooting Cyborgs

I got this riddle fromHere, and it was listed as hard.

Quote:
you're a cyborg in a pistol duel with two other cyborgs. you have been programmed to fire pistols with an accuracy of 33%. the other two cyborgs shoot with accuracies of 100% and 50%, respectively. the rules of the duel are one shot per-cyborg per-round. the shooting order is from worst shooter to best shooter. thus, you go first, the 50% guy goes second, and the 100% guy goes third; repeat. if a cyborg dies, we just skip his or her turn, obviously. what should you shoot at in round 1 to maximize your chances of survival over time?
This seems obvious, shoot at the cyborg who has the 100% chance of hitting whatever he shoots at. Otherwise, if you don't get him, he will either shoot you for sure when his turn comes around, or he will shoot the other guy for sure and then you next if you miss him. So, to test the hypothesis, I wrote a program to have the Cyborgs alternately blast each other according to the rules:


After 100 million rounds of totally random firing for all Cyborgs, these were the scores:

Cyborg 100 Score: 52767596
Cyborg 50 Score: 29173399
Cyborg 33 Score: 18059005

As you can see, Cyborg 33 survives about 1/6 of the time, while Cyborg 50 survives about 1/3 of the time. Cyborg 100 has about twice the chance of surviving as the other two combined, so Cyborg 100 wins about 50% of the time.


Now, I tried another two rounds of firing, each with 100 million rounds, but this time with Cyborg 33 firing all the time at either Cyborg 50 or Cyborg 100 in the first round.

Cyborg 33 always shoots at Cyborg 50 on first round:

Cyborg 100 Score: 69443112
Cyborg 50 Score: 16671731
Cyborg 33 Score: 1388515

As you can see, just as I thought, shooting at Cyborg 50 first makes our (Cyborg 33's) chances of survival dismal.

Cyborg 33 always shoots at Cyborg 100 on first round:

Cyborg 100 Score: 36106605
Cyborg 50 Score: 41667971
Cyborg 33 Score: 22225424

Now, Cyborg 100 only wins about 1/3 of the time, and Cyborg 50 wins 40% of the time. Most importantly, Cyborg 1, us, survives a good 22% of the time, the highest of any of the possibilities.

This is my question:
Now, however, what if Cyborg 50 and 100 were not just mindless idiots firing randomly? Suppose the tried to guess who was the best to shoot at given what they thought the other two Cyborgs would fire at? What would the tree look like that described the optimal way for all Cyborgs to survive based on what the previous Cyborg did? Also, what if we assumed that one or more of the Cyborgs were willing to be sort of temporarily altruistic toward another if they thought it might help themselves? Does this bring up that old paradox of the "informing prisoners" where the prisoners are all better off if they all remain silent, but informing on the other prisoners can bring you lesser benefits, but possibly worse punishments?

This is the code I used for the calculations:

The class for the Cyborgs:

Code:
public class Cyborg
{
 public String name;
 public double accuracy;
 public boolean dead;  
	
 public Cyborg(String new_name, double new_accuracy)
 {
  name = new_name;
  accuracy=new_accuracy;
  dead=false;
 }
	
 public void shoot_up(Cyborg C)
 {
  if(Math.random() < this.accuracy)
  {
	C.dead = true;
   // System.out.println(name + " kills " + C.name);
  }
  else
  {
   // System.out.println(name + " misses " + C.name); 
  }	
 }
}
The driver:

Code:
import java.math.*;
public class Cyborg_shooting_match
{
 public static void main(String[] args)
 {
  Cyborg P100 = new Cyborg("100",1.0);
  Cyborg P50 = new Cyborg("50",0.5);
  Cyborg P33 = new Cyborg("33", 0.33333333333333);
    
  int i = 0;
  int k = 0;
  int P100_score=0;
  int P50_score=0;
  int P33_score=0;
  
  for(long j=0; j<100000000; j++) 
  { 
   k = 0;
   do
   {
    if(!P33.dead)
 	{
	  double d = Math.random();
	 
	  // Used for causing Cyborg 33 to always pick one or other of the other 
	  // Cyborgs on the first round of firing:
	
	  /*
	  if(k==0)
	  {
	   P33.shoot_up(P50);
	  }
	  */
	 
	  /* 
	  if(k==0)
	  {
	   P33.shoot_up(P100);
	  } 
	  */
	 	 
	  if(d>0.5) // Change to "else if" if either of the above two sections are being used.
	  {
	   if(!P100.dead)
	    P33.shoot_up(P100);
	   else
	    P33.shoot_up(P50);
     } 
	  else if(d<0.5)
	  {
	   if(!P50.dead)
	    P33.shoot_up(P50);
	   else
	    P33.shoot_up(P100);
	  }
 	} 
   
	 if(!P50.dead)
 	{
	  double d = Math.random();
	  if(d>0.5)
	  {
	   if(!P100.dead)
	    P50.shoot_up(P100);
	   else
	    P50.shoot_up(P33);
     } 
	  if(d<0.5)
	  {
	   if(!P33.dead)
	    P50.shoot_up(P33);
	   else
	    P50.shoot_up(P100);
	  }
    } 

    if(!P100.dead)
 	{
	  double d = Math.random();
	  if(d>0.5)
	  {
	   if(!P33.dead)
	    P100.shoot_up(P33);
	   else
	    P100.shoot_up(P50);
     } 
	  if(d<0.5)
	  {
	   if(!P50.dead)
	    P100.shoot_up(P50);
	   else
	    P100.shoot_up(P33);
	  }
    }
	
	 i=0; 
    if(!P100.dead)
     i++;
    if(!P50.dead)
     i++;
    if(!P33.dead)
     i++;
	 
    k++;
   }while(i>=2);
  
   if(!P100.dead)
    P100_score++;
    // System.out.println("P100 is the winner!");
   if(!P50.dead)
    P50_score++;
    // System.out.println("P50 is the winner!");
   if(!P33.dead)
    P33_score++;
    // System.out.println("P33 is the winner!");	
  
   P100.dead=false;
   P50.dead=false;
   P33.dead=false;
  }
  System.out.println("P100 Score: " + P100_score);
  System.out.println("P50 Score: " + P50_score);
  System.out.println("P33 Score: " + P33_score);
 } 
}
Infinity is offline  
 
October 29th, 2007, 12:39 PM   #2
Global Moderator
 
CRGreathouse's Avatar
 
Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 938

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
Let's say only two remain. In that case they both fire at the other; let's see the probabilities.

100 - 50: 100 wins.
100 - 33: 100 wins.
50, 100: 50 wins half the time.
50, 33: 50 wins 100/133 = 75.18...% of the time.
33, 100: 33 wins 33% of the time.
33, 50: 33 wins 66/133 = 49.62...% of the time.

So if all three remain, and it's 100's turn, 100 shoots at 50 to maximize its chance of winning. If all three remain and it's 50's turn, 50 shoots at 100 because otherwise it dies on the spot.
CRGreathouse is offline  
October 29th, 2007, 12:50 PM   #3
Global Moderator
 
CRGreathouse's Avatar
 
Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 938

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
You may consider adding a shooting dummy as well. It doesn't shoot, but but can get hit. It wouldn't surprise me if shooting at the dummy gave 33 a better chance in the opening salvo.
CRGreathouse is offline  
October 29th, 2007, 01:02 PM   #4
Senior Member
 
Joined: Dec 2006

Posts: 1,111
Thanks: 0

Thanks for the quick reply! What you say makes sense to me, and explains it all very well. 50 always fires at 100 to avoid dying on the spot (Unless 100 is dead), and 100 always fires at 50 to maximize its chances of surviving the next round (unless 50 is already dead). If that be the case, then, what pattern of firing should Cyborg 33 pursue? Here's my reasoning: Assuming 33 knows that 50 and 100 are going to blast each other until one or the other is dead, I would say that it ought to aim for 100, since that is the most dangerous enemy of the two. If 33 takes out 100, it then has a chance to blast away at 50 and possibly win. If it takes out 50, however, it dies instantly from 100's next shot.

Here are the results of the fighting after 100 million rounds assuming the Cyborgs are clever and shoot according to the best possible survival algorithm:

Cyborg 100 Score: 22,217,709
Cyborg 50 Score: 41,662,663
Cyborg 33 Score: 36,119,628

In this case, Cyborg 50 comes out on top 40% of the time, while Cyborg 33 comes out on top 36% of the time. Cyborg 100, despite being the most powerful, comes out lowest because everybody is firing at it to maximize their own chances of survival.
Infinity is offline  
October 29th, 2007, 01:16 PM   #5
Global Moderator
 
CRGreathouse's Avatar
 
Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 938

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
Quote:
Originally Posted by Infinity
Here are the results of the fighting after 100 million rounds assuming the Cyborgs are clever and shoot according to the best possible survival algorithm:

Cyborg 100 Score: 22,217,709
Cyborg 50 Score: 41,662,663
Cyborg 33 Score: 36,119,628

In this case, Cyborg 50 comes out on top 40% of the time, while Cyborg 33 comes out on top 36% of the time. Cyborg 100, despite being the most powerful, comes out lowest because everybody is firing at it to maximize their own chances of survival.
This strategy should have 33 win 35.86% of the time (closely matching your experimental probability), but if 33 intentionally misses in the first round its chance of winning rises to 41.31%.
CRGreathouse is offline  
Reply

  My Math Forum > Science Forums > Computer Science

Tags
cyborgs, riddle, shooting



Search tags for this page
Click on a term to search for related topics.
Thread Tools
Display Modes


Similar Threads
Thread Thread Starter Forum Replies Last Post
Yet another riddle hermes2014 Applied Math 10 March 15th, 2015 03:34 AM
In a shooting test, probability of hitting the target r-soy Probability and Statistics 2 October 12th, 2013 01:14 AM
new riddle Hoempa New Users 189 June 23rd, 2013 03:31 PM
Riddle rebecca Applied Math 2 November 6th, 2011 04:12 PM
help with a riddle adenthet Computer Science 1 August 29th, 2009 07:43 PM





Copyright © 2018 My Math Forum. All rights reserved.