[Cs4800] Reg: HSR Counting Tournament

[Dennis Zografos]

Despite having only 18.0 points, I won every game I played in this

(I only played 6 games; the winners played 10; something went wrong, 
 somewhere)

(Note: My avatar makes particularly challenging proposals)


----- "Nimrod E. Drizlikh" <nimdriz at ccs.neu.edu> wrote:

> Here are the tournament results for the 100,000 rung tournament: 
> 
> usb	30.0 / ??
> team2	30.0 / Nimrod and Ryan
> wkn32	27.0 / Matthew Pelland
> iGalaxy	27.0 /  James Antonius
> TheGreatGonzo	18.0 / Dennis
> baby	6.0 / The Baby Avatar 
> 
> The other two avatars that participated didn't actually send any
> responses. 
> 
> I also ran into the same issue as David. I am guessing that the only
> thing that is slowing down the server is the implementation of the
> valid function. There seems to be no issues for avatars to run a high
> amount of rungs.
> 
> Nimrod Drizlikh
> 
> ----- Original Message -----
> From: "David Richards" <dirich at ccs.neu.edu>
> To: "Karl Lieberherr" <lieber at ccs.neu.edu>
> Cc: "Ravishankar Rajagopal" <rajagopal.r at husky.neu.edu>, "CS4800
> Mailing List" <cs4800 at lists.ccs.neu.edu>
> Sent: Thursday, December 1, 2011 10:56:09 PM GMT -05:00 US/Canada
> Eastern
> Subject: Re: [Cs4800] Reg: HSR Counting Tournament
> 
> One quick problem I noticed with running a 100,000 rung tournament is
> that the valid function for the HSR playground
> slows down pretty drastically.  While it was taking me a fraction of a
> second to produce a 100,000 rung solution, it was
> taking multiple seconds to compute its validity.  When I ran a
> 1,000,000 rung solution, it took about 5 minutes after which
> I gave up and terminated the program.
> 
> The problem behind this seems to be in the use of ArrayLists.  One of
> the things valid does is produce an ArrayList of
> Integers from 0 to n-1.  It then iterates through the solution tree
> and removes the question of each node from the ArrayList.
> At the end, it checks to make sure that the list is empty.  The
> problem with this approach is that removing an item from an
> ArrayList is actually a potentially long running operation since it
> needs to shift every element in the list after the element
> that was removed.  I did some refactoring and implemented essentially
> the same solution using a stack, which is possible
> as long as we're careful to traverse the solution in the correct order
> (left, current node, right).  Since stacks are designed
> to quickly pop the top element, the runtime was reduced to essentially
> linear in respect to the size of the solution.
> 
> -David
> 
> 
> On Dec 1, 2011, at 10:18 PM, Karl Lieberherr wrote:
> 
> > Hi Nimrod:
> > 
> > thank you for running the tournament. I have not been told yet what
> went wrong with the 100 000 tournament.
> > There is a danger of a stack overflow happening. A larger stack size
> for the admin and avatars might do the trick.
> > 
> > I am at a loss why this was not done before. I double checked this
> morning with the graduate class and a testing team was working on it.
> > 
> > -- Karl
> > 
> > On Thu, Dec 1, 2011 at 10:10 PM, Nimrod E. Drizlikh
> <nimdriz at ccs.neu.edu> wrote:
> > I spent a decent chunk of time testing for 100,000 and making sure
> it would work. If anyone else is in the same boat and wants to test
> their avatar in a 100,000 rung competition I am running one on
> tank.ccs.neu.edu. It starts at 10:37pm. The tournament id is 34. I
> can't promise this but I should also have the babyavatar running in
> the tournament for comparison.
> > 
> > Thanks,
> > Nimrod Drizlikh
> > ----- Original Message -----
> > From: "Ravishankar Rajagopal" <rajagopal.r at husky.neu.edu>
> > To: "Dennis Zografos" <dzog at ccs.neu.edu>
> > Cc: cs4800 at lists.ccs.neu.edu
> > Sent: Thursday, December 1, 2011 9:59:44 PM GMT -05:00 US/Canada
> Eastern
> > Subject: Re: [Cs4800] Reg: HSR Counting Tournament
> > 
> > 
> > No unfortunately at this point, n = 100000 setting has not been
> tested enough and therefore this will be a maxN: 1000 tournament.
> > 
> > Also i request all of you to signup again at tvtennis for the MMG.
> Thanks.
> > 
> > Regards,
> > Ravi Rajagopal
> > 
> > 
> > On Thu, Dec 1, 2011 at 9:46 PM, Dennis Zografos < dzog at ccs.neu.edu >
> wrote:
> > 
> > 
> > the config file for that tournament has
> > 
> > hsr_config[maxN: 1000 ]
> > 
> > isn't this supposed to be an n=100000 tournament?
> > 
> > 
> > ----- "Ravishankar Rajagopal" < rajagopal.r at husky.neu.edu > wrote:
> > 
> > > Hi All,
> > >
> > > The HSR Counting tournament has been scheduled at 10.30 PM tonight
> at
> > > seawolf.ccs.neu.edu . I will approve signups every 5 minutes. You
> can
> > 
> > > use the same version of the code - 76 - as you have used for MMG.
> > >
> > > Regards,
> > > Ravi Rajagopal
> > >
> > 
> > 
> > 
> > > _______________________________________________
> > > Cs4800 mailing list
> > > Cs4800 at lists.ccs.neu.edu
> > > https://lists.ccs.neu.edu/bin/listinfo/cs4800
> > 
> > 
> > _______________________________________________
> > Cs4800 mailing list
> > Cs4800 at lists.ccs.neu.edu
> > https://lists.ccs.neu.edu/bin/listinfo/cs4800
> > 
> > _______________________________________________
> > Cs4800 mailing list
> > Cs4800 at lists.ccs.neu.edu
> > https://lists.ccs.neu.edu/bin/listinfo/cs4800
> > 
> > _______________________________________________
> > Cs4800 mailing list
> > Cs4800 at lists.ccs.neu.edu
> > https://lists.ccs.neu.edu/bin/listinfo/cs4800
> 
> 
> _______________________________________________
> Cs4800 mailing list
> Cs4800 at lists.ccs.neu.edu
> https://lists.ccs.neu.edu/bin/listinfo/cs4800
> 
> _______________________________________________
> Cs4800 mailing list
> Cs4800 at lists.ccs.neu.edu
> https://lists.ccs.neu.edu/bin/listinfo/cs4800