[Cs4800] Updated HSR tournament & Tips for HSR(100K,1)

Matthew Strax-Haber straxhaber at gmail.com
Fri Dec 2 12:24:23 EST 2011 

I'll be running another HSR tournament with 100K rungs Sunday afternoon for those that think they are able. If I find the time, I'm going to try and implement new versions of the four pieces below. If I do, I'll release a modified GenericSCG revision 76. If any of you has non-recursive solutions to some of these checks, ideas of what to write, or additional functions that need to be re-implemented, please send them over to save me some work ;).

For other students trying to get to 100,000 rungs, here are a couple of things you need to be aware of:
 - HSRInstance.valid, HSRInstance.quality, and HSRSolution.findDepth will have StackOverflows on most default JVM setups.
 - The way HSRInstance.valid is written, it will run slowly even if there isn't a StackOverflow.
 - Recursion in your code is precarious for k=1 because of the size of the tree. Use another technique (but I'll leave that to you to figure out).
 - I haven't investigated this one yet, but I think the mechanism for turning HSRSolutions into Strings for transfer also can't handle big trees.

Some may of already figured this out, but hopefully this helps those who have been confused by the system.

Also, as a challenge for those participating, can you beat these times?
	<1ms to solve HSR(n=1,k=1)
   <1ms to solve HSR(n=1000,k=1)
   <1ms to solve HSR(n=100000,k=1)
   669ms to solve HSR(n=1000000,k=1) (damn garbage collector)
   4ms to solve HSR(n=1000,k=5)
   74ms to solve HSR(n=100000,k=5)
   282ms to solve HSR(n=1000000,k=5)



Best regards,
-- 
~ Matthew Strax-Haber
Northeastern University

On Dec 2, 2011, at 9:23 AM, David Richards wrote:

> Yeah, I'm not sure what happened with my avatar given that it can solve 100,000 rung ladders
> in about 20 ms.  I tried running my own practice tournament and was getting stack overflows 
> on the admin side on every proposal.  It's worth noting that I'm not using up to date code since I
> didn't have time to do a reintegration and check it.  
> 
> Is anyone interested in a rematch once I figure out what's going on?
> 
> -David
> 
> On Dec 2, 2011, at 12:21 AM, Dennis Zografos wrote:
> 
>> Enter copy mode via: C-a [
>> 
>> then use `?' to do a backwards vi-like search for terms like "Exception" 
>> and "TheGreatGonzo"
>> 
>> (if you're using the default scrollback buffer size, the info might be 
>> lost, but it's worth a try)
>> 
>> also, to save the copybuffer to a file, use :hardcopy -h [file]
>> 
>> 
>> 
>> 
>> ----- "Nimrod E. Drizlikh" <nimdriz at ccs.neu.edu> wrote:
>> 
>>> That is pretty odd. Do you know if there is any kind of admin log I
>>> can look at? I have the admin running on a screen without saving any
>>> of its output so I will check that but I doubt that it will be enough
>>> to tell us what happened. 
>>> 
>>> ----- Original Message -----
>>> From: "Dennis Zografos" <dzog at ccs.neu.edu>
>>> To: "Nimrod E. Drizlikh" <nimdriz at ccs.neu.edu>
>>> Cc: "Ravishankar Rajagopal" <rajagopal.r at husky.neu.edu>, "CS4800
>>> Mailing List" <cs4800 at lists.ccs.neu.edu>, "David Richards"
>>> <dirich at ccs.neu.edu>
>>> Sent: Thursday, December 1, 2011 11:58:04 PM GMT -05:00 US/Canada
>>> Eastern
>>> Subject: Re: [Cs4800] Reg: HSR Counting Tournament
>>> 
>>> 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
> 
> 
> _______________________________________________
> Cs4800 mailing list
> Cs4800 at lists.ccs.neu.edu
> https://lists.ccs.neu.edu/bin/listinfo/cs4800

-------------- next part --------------
HTML attachment scrubbed and removed

More information about the Cs4800 mailing list