Got Questions? Get Answers.
Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
MATLAB Programming Contest: May 9 - May 16, 2007

Subject: MATLAB Programming Contest: May 9 - May 16, 2007

From: Helen Chen

Date: 26 Apr, 2007 18:39:05

Message: 1 of 221

Hello Community!

This is just a quick message to let everyone know that the MATLAB
Contest Masters have been hard at work! They have been crafting a
really exciting new challenge for our Spring event with some very
cool prizes waiting for our champions.

It's time to clear your calendars so that you can come join the fun!
The contest will start at noon Eastern time on May 9, ending at noon
on Mary 16th.

We will be announcing more details about the contest as we get
closer, so if you want a refresher about MATLAB Central contests,
check out the contest overview page at <http://www.mathworks.com/contest/overview.html>.
ou can checkout past contests using links on that page.

Stay tuned for more information...

Best wishes,
Helen Chen
MATLAB Central Team

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: Matthew Simoneau

Date: 9 May, 2007 09:29:02

Message: 2 of 221

Our contest will indeed begin today at noon EDT. I posted a welcome
message to the contest blog with some new information:

 <http://blogs.mathworks.com/contest/>

We have a few channels for contest conversation. This newsgroup
thread is the best place for general discussion. If you have a
response to anything we post on the blog, we encourage you to leave a
comment on the blog itself. Finally, if you'd like to communicate
with the contest team privately, e-mail us at contest@mathworks.com.

Good luck to everyone!

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: Alan Chalker

Date: 9 May, 2007 12:28:44

Message: 3 of 221

Thanks for organizing another contest. I'm looking forward to
participating as I'm sure a lot of people are.

Maybe this is in the code package, which I haven't looked at yet, but
what is the formula for the final result? In the past you've always
outlined it as something like

result = a*score + b*e^(c*time)

However with the new cyclomatic complexity variable it'd be helpful
to understand how that factors into the result.

Subject: solitaireGUI

From: Mike Bindschadler

Date: 9 May, 2007 12:53:37

Message: 4 of 221

The contest problem looks pretty interesting, thanks for setting it
up!

I tried to run the solitaireGUI.m function which came with zipped
contest files, and got an error message as follows:
 
Warning: Divide by zero.
> In solitaireGUI at 63
??? Undefined command/function 'bsxfun'.

Error in ==> solitaireGUI>drawGUI at 200
  c = c(:,~(sum(bsxfun(mf,1:size(c,2),(1:size(c,2))'))>1))';

Error in ==> solitaireGUI at 69
[hf,ha,sh,ht,hl] = drawGUI; printStats

I'm running MATLAB 7.1 student edition.

Subject: solitaireGUI

From: John D'Errico

Date: 9 May, 2007 12:58:47

Message: 5 of 221

Mike Bindschadler wrote:
>
>
> The contest problem looks pretty interesting, thanks for setting it
> up!
>
> I tried to run the solitaireGUI.m function which came with zipped
> contest files, and got an error message as follows:
>
> Warning: Divide by zero.
>> In solitaireGUI at 63
> ??? Undefined command/function 'bsxfun'.
>
> Error in ==> solitaireGUI>drawGUI at 200
> c = c(:,~(sum(bsxfun(mf,1:size(c,2),(1:size(c,2))'))>1))';
>
> Error in ==> solitaireGUI at 69
> [hf,ha,sh,ht,hl] = drawGUI; printStats
>
> I'm running MATLAB 7.1 student edition.
  
bsxfun only came out in the most recent release.

John

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: Matthew Simoneau

Date: 9 May, 2007 13:07:45

Message: 6 of 221

Hi Alan,

I added the scoring formula to the rules. It is the same as it was
before with k*complexity added on the end.

Thanks,
Matthew

Subject: runcontest

From: Windy Miller

Date: 9 May, 2007 13:08:13

Message: 7 of 221

I'm just trying to run "runcontest", to see what the basic unmodified
solver does to the testsuite. I have a choice of error messages...

>> runcontest
??? Too many inputs.

Error in ==> runcontest at 18
    solutions = cellfun(@solver,boards,'UniformOutput',false);

>> runcontest(true)
??? Function name must be a string.

Error in ==> solitaireGUI>drawGUI at 184
  ht = cellfun(@(f,p) uicontrol('Sty','Tex','Fore',f,'Back',[1 1
.83],...

Error in ==> solitaireGUI at 69
[hf,ha,sh,ht,hl] = drawGUI; printStats

Error in ==> runcontest at 27
       
solitaireGUI(testsuite(i).board,solution,min(1,5/size(solution,1)))

>>

(MATLAB version 7.0.1)

Any ideas?

Subject: runcontest

From: Lucio

Date: 9 May, 2007 13:17:53

Message: 8 of 221

This may also be due to the fact that we used 7.4.0 to create the
GUI, we will provide a backwards compatible version soon. Please bare
with us.

Lucio

 Windy Miller wrote:
>
>
> I'm just trying to run "runcontest", to see what the basic
> unmodified
> solver does to the testsuite. I have a choice of error messages...
>
>>> runcontest
> ??? Too many inputs.
>
> Error in ==> runcontest at 18
> solutions = cellfun(@solver,boards,'UniformOutput',false);
>
>>> runcontest(true)
> ??? Function name must be a string.
>
> Error in ==> solitaireGUI>drawGUI at 184
> ht = cellfun(@(f,p) uicontrol('Sty','Tex','Fore',f,'Back',[1 1
> .83],...
>
> Error in ==> solitaireGUI at 69
> [hf,ha,sh,ht,hl] = drawGUI; printStats
>
> Error in ==> runcontest at 27
>
> solitaireGUI(testsuite(i).board,solution,min(1,5/size(solution,1)))
>
>>>
>
> (MATLAB version 7.0.1)
>
> Any ideas?

Subject: Obfuscation

From: Markus

Date: 9 May, 2007 13:29:06

Message: 9 of 221

Hi!

I am having the same problem with the bsxfun error message, as I am
running R2006a. The contest team did a good job in obfuscation, or
what do you think about these lines?

% mf = @(g,h) arrayfun(@(h)
all(inpolygon(c{1,g},c{2,g},c{1,h},c{2,h})),h);
% c = c(:,~(sum(bsxfun(mf,1:size(c,2),(1:size(c,2))'))>1))';

This source couldn't be easier to read I guess :-)

A good contest to all of you!

Markus

Subject: Obfuscation

From: Alan Chalker

Date: 9 May, 2007 13:38:21

Message: 10 of 221

Markus wrote:
>
>
> Hi!
>
> I am having the same problem with the bsxfun error message, as I am
> running R2006a. The contest team did a good job in obfuscation, or
> what do you think about these lines?
>
> % mf = @(g,h) arrayfun(@(h)
> all(inpolygon(c{1,g},c{2,g},c{1,h},c{2,h})),h);
> % c = c(:,~(sum(bsxfun(mf,1:size(c,2),(1:size(c,2))'))>1))';
>
> This source couldn't be easier to read I guess :-)
>
> A good contest to all of you!
>
> Markus
  

It's not deliberate obscufation that I can tell. The first line is
setting up an nested anonymous function handle (search for anonymous
functions in the MATLAB help for info). bsxfun is a new one to me,
but it applies element by element binary operations to 2 arrays.

The bottom line is they have used some of the more advanced
functionality to setup a demo solver and runcontest program that is
vectorized versus containing a lot of loops. This also factors into
the new Complexity rating.

Kudos to them for setting the bar high on this contest by trying to
start us off on a vectorized path instead of the 'easier to follow'
looping path many people would prefer to take.

Subject: Obfuscation

From: Lucio

Date: 9 May, 2007 13:44:58

Message: 11 of 221

OK to run in 7.1 change the following lines, sorry for the wrapping,
we will update the zip file and investigate further the other Windy's
problem (Windy, what release are you using?)

% c = c(:,~(sum(bsxfun(mf,1:size(c,2),(1:size(c,2))'))>1))';
  
CHANGE TO:

  MF = zeros(size(c,2));
  for i1 = 1:size(c,2)
      for i2 = 1:size(c,2)
          MF(i1,i2) = mf(i1,i2);
      end
  end
  c = c(:,~sum(MF)>1)';

% patch(bsxfun(@plus,j(:)',.1*sin(-2*pi:pi/4:2*pi)'),...
% bsxfun(@plus,i(:)',.1*cos(-2*pi:pi/4:2*pi)'),...
% zeros(17,numel(i)),'faceC',[0 .5 0],'FaceL','none');

CHANGE TO:

patch(repmat(j(:)',17,1)+repmat(.1*sin(-2*pi:pi/4:2*pi)',1,numel(j)),.
..
       
repmat(i(:)',17,1)+repmat(.1*cos(-2*pi:pi/4:2*pi)',1,numel(i)),...
        zeros(17,numel(i)),'faceC',[0 .5 0],'FaceL','none');

Lucio

 Alan Chalker wrote:
>
>
> Markus wrote:
>>
>>
>> Hi!
>>
>> I am having the same problem with the bsxfun error message, as
I
> am
>> running R2006a. The contest team did a good job in obfuscation,
> or
>> what do you think about these lines?
>>
>> % mf = @(g,h) arrayfun(@(h)
>> all(inpolygon(c{1,g},c{2,g},c{1,h},c{2,h})),h);
>> % c =
c(:,~(sum(bsxfun(mf,1:size(c,2),(1:size(c,2))'))>1))';
>>
>> This source couldn't be easier to read I guess :-)
>>
>> A good contest to all of you!
>>
>> Markus
>
>
> It's not deliberate obscufation that I can tell. The first line is
> setting up an nested anonymous function handle (search for
> anonymous
> functions in the MATLAB help for info). bsxfun is a new one to me,
> but it applies element by element binary operations to 2 arrays.
>
> The bottom line is they have used some of the more advanced
> functionality to setup a demo solver and runcontest program that is
> vectorized versus containing a lot of loops. This also factors
> into
> the new Complexity rating.
>
> Kudos to them for setting the bar high on this contest by trying to
> start us off on a vectorized path instead of the 'easier to follow'
> looping path many people would prefer to take.

Subject: grade function

From: pete torrione

Date: 9 May, 2007 15:10:59

Message: 12 of 221

Marko wrote:
>
>
> Can somebody explain me this line in the grade.m function?
>
> if tb(f) && board(f(2),f(1))>0 % valid pick
>
> why isn't board(f(1),f(2)) checked? Do I have to read the contest
> rules more carefully?

I have the same question. This seems odd:

board = [1 5 0];
score = grade(board,[1 1 1 3])
gives 7 (because the jump is invalid)

but
score = grade(board,[1 1 3 1])
gives 2; the expected score, i thought...

Subject: grade function

From: Jan Langer

Date: 9 May, 2007 15:11:27

Message: 13 of 221

Marko wrote:
> Can somebody explain me this line in the grade.m function?
>
> if tb(f) && board(f(2),f(1))>0 % valid pick
>
> why isn't board(f(1),f(2)) checked? Do I have to read the contest
> rules more carefully?

I have also big problems with the grade function.
Jan

Subject: grade function

From: Marko

Date: 9 May, 2007 15:13:17

Message: 14 of 221

All indices of type x(2),x(1) must be x(1),x(2) i think

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: Nick Howe

Date: 9 May, 2007 15:14:37

Message: 15 of 221

Thanks once again to everybody at the Mathworks who works hard to
bring us a fun contest. I have a question concerning a possible
discrepancy in the starter files. The solver provided seems to
generate moves which the grade.m function considers invalid. In
looking into the matter, it appears that the expected order of
indices is swapped. So for example, the first set of commands will
generate a poorer score than the second:

moves = solver(board)
grade(moves)

moves = solver(board)
grade(moves(:,[2 1 4 3]))

Of course, runcontest does the former. So should we write our
solvers accordingly?

Subject: grade function

From: Peter Torrione

Date: 9 May, 2007 15:18:22

Message: 16 of 221

Marko wrote:
> All indices of type x(2),x(1) must be x(1),x(2) i think
It looks like doing this at the end of your 'solver' solves the problem:

moves = moves(:,[2 1 4 3]);

Subject: grade function

From: Marko

Date: 9 May, 2007 15:27:49

Message: 17 of 221

Peter Torrione wrote:

> It looks like doing this at the end of your 'solver' solves the
> problem:
>
> moves = moves(:,[2 1 4 3]);

Yes but it's not supposed to work like that and confusing shifting
from row,colum indices to colum,row

Maybe I should stop solving and start evaluating again :-)

Subject: grade function

From: Lucio

Date: 9 May, 2007 15:32:17

Message: 18 of 221

Peter is correct, the indexes got messed up when we set the grade.m
function from the GUI. Changing the lines

    f = moves(i,[1 2]);
    t = moves(i,[3 4]);

to

    f = moves(i,[2 1]);
    t = moves(i,[4 3]);

should be enough, albeit I will carefully revise it, when done we'll
update the zip file. Sorry for the inconvenience.

Lucio

Peter Torrione wrote:
>
>
> Marko wrote:
>> All indices of type x(2),x(1) must be x(1),x(2) i think
> It looks like doing this at the end of your 'solver' solves the
> problem:
>
> moves = moves(:,[2 1 4 3]);
>

Subject: grade function

From: Peter Torrione

Date: 9 May, 2007 15:34:40

Message: 19 of 221

Marko wrote:
> Peter Torrione wrote:
>
>> It looks like doing this at the end of your 'solver' solves the
>> problem:
>>
>> moves = moves(:,[2 1 4 3]);
>
> Yes but it's not supposed to work like that and confusing shifting
> from row,colum indices to colum,row
>
I agree. Plus the gui becomes useless...

Subject: grade function

From: Sergey Yurgenson

Date: 9 May, 2007 15:39:34

Message: 20 of 221

Sorry for repeat. Did not see Lucio’s response.

Subject: MATLAB Programming Contest: May 9 - May 16, 20 (180 second question)

From: Peter Torrione

Date: 9 May, 2007 15:40:33

Message: 21 of 221

Hi.

According to the web page, there is a 180 second time limit on our
programs. Is that for each board? How many boards will the programs be
expected to solve in 180 seconds?

-pete

Subject: MATLAB Programming Contest: May 9 - May

From: Lucio

Date: 9 May, 2007 15:49:09

Message: 22 of 221

Pete:

As usual, the testsuite sample that we provide has the
same level of complexity as the hidden testsuite. 180 seconds is the
time given to solve the whole testsuite.

Lucio

 Peter Torrione wrote:
>
>
> Hi.
>
> According to the web page, there is a 180 second time limit on our
> programs. Is that for each board? How many boards will the
> programs be
> expected to solve in 180 seconds?
>
> -pete
>

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: Matthew Simoneau

Date: 9 May, 2007 16:43:02

Message: 23 of 221

We've updated the File Exchange download to include a version of the
GUI that will run on older versions of MATLAB, solitareGUIb.m. We've
also made the fix to grade.m.

This same code was used on the scoring machine. We've updated
grade.m there as well. One of the reasons that we the administrators
like starting the contest in darkness is that we can patch up any
last-minute discoveries before it affects the game.

Lucio dreams in MATLAB code, so please forgive its terseness. He was
also a contest participant before he was an employee. Have y'all
checked out our list of job openings? We're hiring!

Thanks everyone for your patience.

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: Alan Chalker

Date: 9 May, 2007 17:16:59

Message: 24 of 221

Matthew Simoneau wrote:
>
>
> We've updated the File Exchange download to include a version of
> the
> GUI that will run on older versions of MATLAB, solitareGUIb.m.
> We've
> also made the fix to grade.m.
>
> This same code was used on the scoring machine. We've updated
> grade.m there as well. One of the reasons that we the
> administrators
> like starting the contest in darkness is that we can patch up any
> last-minute discoveries before it affects the game.
>
> Lucio dreams in MATLAB code, so please forgive its terseness. He
> was
> also a contest participant before he was an employee. Have y'all
> checked out our list of job openings? We're hiring!
>
> Thanks everyone for your patience.
  
I'm not sure you fixed grade.m. I manually did the fix outlined
above and everything was working fine. Then I just downloaded the
new version and it's giving high scores again. Looking at the file
you didn't switch the indexes you just switched the f = moves... and
t=moves... lines positions.

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: Leendert Combee

Date: 9 May, 2007 17:21:17

Message: 25 of 221

Matthew Simoneau wrote:
>
>
> We've updated the File Exchange download to include a version of
> the

Great, for all those (like me) that are on much older versions
without anonymous functions (the @), they are easy to replace by
ordinary functions. NB, does the complexity of an anonymous functions
add to the cyclomatic complexity of the function they are defined in?


Also I was suprised that the peg values are not integers but all
kinds of floats? Is that correct?

Otherwise a fun puzzle indeed!

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: Matthew Simoneau

Date: 9 May, 2007 17:27:26

Message: 26 of 221

Alan, you're right. I didn't read Lucio's instructions carefully
enough. The re-corrected version will be live shortly.

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: Gerbert Myburgh

Date: 9 May, 2007 18:02:48

Message: 27 of 221

Matthew Simoneau wrote:
>
>
> Alan, you're right. I didn't read Lucio's instructions carefully
> enough. The re-corrected version will be live shortly.
  

Damn...

I've been double checking my code for the last two hours.
Couldn't figure out why on earth every change I make keeps on
increasing my score.

Thanks for pointing out the fix guys.

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: Mike Gallamore

Date: 9 May, 2007 19:23:00

Message: 28 of 221

Leendert Combee wrote:
>
>
> Matthew Simoneau wrote:
>>
>>
>> We've updated the File Exchange download to include a version
of
>> the
>
> Great, for all those (like me) that are on much older versions
> without anonymous functions (the @), they are easy to replace by
> ordinary functions. NB, does the complexity of an anonymous
> functions
> add to the cyclomatic complexity of the function they are defined
> in?
>
>
> Also I was suprised that the peg values are not integers but all
> kinds of floats? Is that correct?
Probably so they can pop the number right into the evaluation
function. I'm not sure but I seem to recall PIV and Core 2 Duo's have
more floating point units than integer, good chance it could improve
performance (at least on compiled code :( )
>
> Otherwise a fun puzzle indeed!

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: peter torrione

Date: 9 May, 2007 19:59:44

Message: 29 of 221

I just downloaded the new score.m - last modified at 5:22 pm, is
something odd about:

>> board = [1 5 0];
>> moves = [1 1 1 3];
>> score = grade(board,moves)

score =

     6

?

I thought score should be 2...

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: Richard Brown

Date: 9 May, 2007 17:14:39

Message: 30 of 221

Are we allowed to use try ... catch constructs?

On May 10, 1:29 am, "Matthew Simoneau" <matt...@mathworks.com> wrote:
> Our contest will indeed begin today at noon EDT. I posted a welcome
> message to the contest blog with some new information:

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: Matthew Simoneau

Date: 9 May, 2007 20:24:25

Message: 31 of 221

Peter, I seem to be too sleepy for this! I still had it wrong in
grade.m. I'm updating it again. Please copy Lucio's fix above more
carefully than I did!

Richard, there's no problem with try/catch, but you're not allowed to
call ERROR explicitly.

Subject: MATLAB Programming Contest: May 9 - May 16, 2007

From: Abhi

Date: 10 May, 2007 05:47:57

Message: 32 of 221

Hi,

I'm using MATLAB Version 7.3.0.267 (R2006b).

Still getting error in GUI :
Undefined function or method 'bsxfun' for input arguments of type
'function_handle'.

How can I use the new GUI: solitaireGUIb.m

Any help?

Rgds,
Abhi

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: srach

Date: 10 May, 2007 06:18:24

Message: 33 of 221

Abhi wrote:
>
>
> Hi,
>
> I'm using MATLAB Version 7.3.0.267 (R2006b).
>
> Still getting error in GUI :
> Undefined function or method 'bsxfun' for input arguments of type
> 'function_handle'.
>
> How can I use the new GUI: solitaireGUIb.m
>
> Any help?
>
> Rgds,
> Abhi
  

Open runcontest.m and change line

       
solitaireGUI(testsuite(i).board,solution,min(1,5/size(solution,1)))

to

       
solitaireGUIb(testsuite(i).board,solution,min(1,5/size(solution,1)))

srach

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: Abhi

Date: 10 May, 2007 08:56:09

Message: 34 of 221

srach wrote:
>
>
>
> Open runcontest.m and change line
>
>
> solitaireGUI(testsuite(i).board,solution,min(1,5/size(solution,1)))
>
> to
>
>
>
solitaireGUIb(testsuite(i).board,solution,min(1,5/size(solution,1)))
>
>
> srach
 

Thnxx..that works...

Rgds,
Abhi

Subject: Unsynchronized clocks?

From: Nick Howe

Date: 10 May, 2007 12:07:55

Message: 35 of 221

There seems to be a discrepancy between the timestamp given on the
page you see after you submit an entry, and the timestamp you get
when you follow the "Entry Listing" link from the contest menu. The
latter seems to lag the former by two minutes or so. At least that's
how it looked to me at the end of Darkness. I submitted a (slightly
late) last-minute entry and the page said 12:01, then clicked the
Entry Listing link and got a page that said 11:59. My most recent
entry wasn't there yet, which sort of makes sense. Is the "Entry
Listing" link a time-delayed view, or are there two clocks? Just
curious. :-)

Subject: Unsynchronized clocks?

From: Matthew Simoneau

Date: 10 May, 2007 13:19:50

Message: 36 of 221

Hi Nick and welcome back. Most of the pages you see on the contest
site are refreshed only every couple of minutes. (We do this to keep
from having to hit the database every time someone views every page.)
 When you see "This page was generated..." on a page, the time
represents when this page was last refreshed, as late as a few
minutes ago, not the current time.

Subject: runcontest

From: B

Date: 10 May, 2007 14:16:30

Message: 37 of 221

Is there any possibility of getting this to work on say r12.1? I've
been making modifications to try to get this to happen but im getting
the following error i do not understand?

runcontest
??? Error: File: C:\contest\jumping\solver.m Line: 10 Column: 6
"identifier" expected, "(" found.

Error in ==> C:\contest\jumping\runcontest.m
On line 20 ==> solutions{i} = solver(testsuite(i).board);

which pertains to

s = @(i,j) sub2ind([m,n],i,j);

in solver.m

Does anyone know why this errors? Is this due to my old version of
matlab?

Thanks

 

Lucio wrote:
>
>
> This may also be due to the fact that we used 7.4.0 to create the
> GUI, we will provide a backwards compatible version soon. Please
> bare
> with us.
>
> Lucio
>
> Windy Miller wrote:
>>
>>
>> I'm just trying to run "runcontest", to see what the basic
>> unmodified
>> solver does to the testsuite. I have a choice of error
> messages...
>>
>>>> runcontest
>> ??? Too many inputs.
>>
>> Error in ==> runcontest at 18
>> solutions = cellfun(@solver,boards,'UniformOutput',false);
>>
>>>> runcontest(true)
>> ??? Function name must be a string.
>>
>> Error in ==> solitaireGUI>drawGUI at 184
>> ht = cellfun(@(f,p) uicontrol('Sty','Tex','Fore',f,'Back',[1 1
>> .83],...
>>
>> Error in ==> solitaireGUI at 69
>> [hf,ha,sh,ht,hl] = drawGUI; printStats
>>
>> Error in ==> runcontest at 27
>>
>>
> solitaireGUI(testsuite(i).board,solution,min(1,5/size(solution,1)))
>>
>>>>
>>
>> (MATLAB version 7.0.1)
>>
>> Any ideas?

Subject: runcontest

From: roberson@ibd.nrc-cnrc.gc.ca (Walter Roberson)

Date: 10 May, 2007 18:28:07

Message: 38 of 221

In article <ef55232.39@webcrossing.raydaftYaTP>,
B <Brian.Corwin@hotmail.com> wrote:
>Is there any possibility of getting this to work on say r12.1? I've
>been making modifications to try to get this to happen but im getting
>the following error i do not understand?

>runcontest
>??? Error: File: C:\contest\jumping\solver.m Line: 10 Column: 6
>"identifier" expected, "(" found.

>Error in ==> C:\contest\jumping\runcontest.m
>On line 20 ==> solutions{i} = solver(testsuite(i).board);

>which pertains to

>s = @(i,j) sub2ind([m,n],i,j);

>in solver.m

>Does anyone know why this errors? Is this due to my old version of
>matlab?

Did R12.1 support anonymous functions?
--
  "It is important to remember that when it comes to law, computers
  never make copies, only human beings make copies. Computers are given
  commands, not permission. Only people can be given permission."
                                               -- Brad Templeton

Subject: runcontest

From: Steven Lord

Date: 10 May, 2007 16:31:46

Message: 39 of 221


"Walter Roberson" <roberson@ibd.nrc-cnrc.gc.ca> wrote in message
news:f1vo7n$cph$1@canopus.cc.umanitoba.ca...
> In article <ef55232.39@webcrossing.raydaftYaTP>,
> B <Brian.Corwin@hotmail.com> wrote:
>>Is there any possibility of getting this to work on say r12.1? I've
>>been making modifications to try to get this to happen but im getting
>>the following error i do not understand?
>
>>runcontest
>>??? Error: File: C:\contest\jumping\solver.m Line: 10 Column: 6
>>"identifier" expected, "(" found.
>
>>Error in ==> C:\contest\jumping\runcontest.m
>>On line 20 ==> solutions{i} = solver(testsuite(i).board);
>
>>which pertains to
>
>>s = @(i,j) sub2ind([m,n],i,j);
>
>>in solver.m
>
>>Does anyone know why this errors? Is this due to my old version of
>>matlab?
>
> Did R12.1 support anonymous functions?

No. Anonymous functions were introduced in MATLAB 7.0 (R14). Brian, you
could try converting the anonymous functions into a regular function, but
you'd also need to modify the locations where those anonymous functions are
called to pass in the correct parameters in the correct order.

--
Steve Lord
slord@mathworks.com

Subject: runcontest

From: B

Date: 10 May, 2007 16:57:25

Message: 40 of 221

Perhaps this is a topic for another thread but, im not exactly sure
of what the purpose of using the anonymous function in this case is?

with the statement s=@(i,j) sub2ind([m,n],i,j);
am i just declaring a function S that takes in values i and j and is
simply using the sub2ind function?

when i call the s function in the above case as s(i,j) the value
returned in place of s(i,j) is just the value of sub2ind([m,n],i,j)?

Aside from having multiple script files what is the benefit in this
situation of using the anonymous function?

Thanks,
Brian

>
>
>
> "Walter Roberson" <roberson@ibd.nrc-cnrc.gc.ca> wrote in
message
> news:f1vo7n$cph$1@canopus.cc.umanitoba.ca...
>> In article <ef55232.39@webcrossing.raydaftYaTP>,
>> B <Brian.Corwin@hotmail.com> wrote:
>>>Is there any possibility of getting this to work on say
r12.1?
> I've
>>>been making modifications to try to get this to happen but
im
> getting
>>>the following error i do not understand?
>>
>>>runcontest
>>>??? Error: File: C:\contest\jumping\solver.m Line: 10
Column: 6
>>>"identifier" expected, "(" found.
>>
>>>Error in ==> C:\contest\jumping\runcontest.m
>>>On line 20 ==> solutions{i} = solver(testsuite(i).board);
>>
>>>which pertains to
>>
>>>s = @(i,j) sub2ind([m,n],i,j);
>>
>>>in solver.m
>>
>>>Does anyone know why this errors? Is this due to my old
version
> of
>>>matlab?
>>
>> Did R12.1 support anonymous functions?
>
> No. Anonymous functions were introduced in MATLAB 7.0 (R14).
> Brian, you
> could try converting the anonymous functions into a regular
> function, but
> you'd also need to modify the locations where those anonymous
> functions are
> called to pass in the correct parameters in the correct order.
>
> --
> Steve Lord
> slord@mathworks.com
>
>
>

Subject: runcontest

From: Leendert Combee

Date: 10 May, 2007 17:59:24

Message: 41 of 221

> with the statement s=@(i,j) sub2ind([m,n],i,j);
> am i just declaring a function S that takes in values i and j and

yes, that's right and all, just a more compact code...

to Walter: just replace s(x,y) in the code by sub2ind([m,n],x,y)
where x and y are the actual arguments used whereever you encounter
s. In grade.m you need to do something similar to t(f)

Subject: runcontest

From: B

Date: 10 May, 2007 18:43:43

Message: 42 of 221

Thanks all, I believe I am close to having a package that will
atleast let me try to develop contest solutions. I am curious though
if someone can do me a favor so i can validate my results. Can
someone run the testsuite for say the first 3 boards, and tell me
what the results are when running the test suite unchanged? I'd like
to verify that all of my modifications are still kosher.

b

 Leendert Combee wrote:
>
>
>> with the statement s=@(i,j) sub2ind([m,n],i,j);
>> am i just declaring a function S that takes in values i and j
and
>
> yes, that's right and all, just a more compact code...
>
> to Walter: just replace s(x,y) in the code by sub2ind([m,n],x,y)
> where x and y are the actual arguments used whereever you encounter
> s. In grade.m you need to do something similar to t(f)

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: eigenvector

Date: 10 May, 2007 20:32:34

Message: 43 of 221

Hi,
 
I get this error:
 
Error using ==> filefilt at 123 The function ER...
 
What does it mean? I am quite puzzled...
 
Thanks!

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: Matthew Simoneau

Date: 10 May, 2007 20:59:05

Message: 44 of 221

> Error using ==> filefilt at 123 The function ER...

The rest of this message is "The function ERROR has been disabled".
ERROR is on our list of blocked functions.

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: eigenvector

Date: 11 May, 2007 05:56:58

Message: 45 of 221

Your are right, thanks!

While we are at it, it turns out that ERROR appeared in the function
grade which you supplied and I used. Maybe you want to consider
removing it from grade... :)

Thanks again!

 Matthew Simoneau wrote:
>
>
>> Error using ==> filefilt at 123 The function ER...
>
> The rest of this message is "The function ERROR has been disabled".
>
> ERROR is on our list of blocked functions.

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: Volkan

Date: 11 May, 2007 18:11:43

Message: 46 of 221

Hi all,

Does anyone know what the number in paranthesis just below the
Results field is? Does it have anything to do with the submissions
cyclomatic complexity?

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: the cyclist

Date: 11 May, 2007 18:37:00

Message: 47 of 221

Volkan wrote:
>
>
> Hi all,
>
> Does anyone know what the number in paranthesis just below the
> Results field is? Does it have anything to do with the submissions
> cyclomatic complexity?
  
Yes. It IS the cyclomatic complexity.

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: Matthew Simoneau

Date: 11 May, 2007 20:55:08

Message: 48 of 221

the cyclist wrote:
> Yes. It IS the cyclomatic complexity.

Cyclistmatic?

I added "cyc: " in front of the number so everyone will have a chance
of guessing what it means. Someday we'll get this thing its own
column.

Subject: Commented code

From: Markus

Date: 12 May, 2007 05:58:02

Message: 49 of 221

Alan Chalker wrote:
> For those of you interested, I've submitted a heavily commented
> version of the current leading code

Great idea Alan! That is really in the spirit of the contest!

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: Helen Chen

Date: 12 May, 2007 07:21:18

Message: 50 of 221

Hi Markus !

We definitely think think that this is a good idea but unfortunately
do not have the resources to redo the contest site at this time. We
are looking to do something along those lines in the future.

Helen

 Markus wrote:
>
>
> To the contest team:
>
> In the last contests we were already crying for inserting a
> "captcha"
> on the entry submit page. Just as I have to fill "BTQNT" in a Word
> verfication line below the form where I currently am typing this
> text
> in. This would prevent spamming the queue and searching for the
> best
> parameters by multiple entries.
>
> Did you not include it because you don't like the idea or because
> you
> did not have the resources to do the modification to the interface?
>
>
> Markus

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: the cyclist

Date: 12 May, 2007 09:00:52

Message: 51 of 221

> This is just a quick message to let everyone know that the MATLAB
> Contest Masters have been hard at work!

Looks like there might be some small problems with the statistics
page. The Saturday "Contributions in Daylight" seem to be being
counted in Friday as well. Also, I think some or all of the graphs
on that page are not being updated.

Thanks again for putting on the contest.

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: Helen Chen

Date: 12 May, 2007 09:09:33

Message: 52 of 221

Thanks for pointing this out! We'll take a look at this, although
maybe not until Monday.

Helen

  the cyclist wrote:
>
>
>> This is just a quick message to let everyone know that the
MATLAB
>> Contest Masters have been hard at work!
>
> Looks like there might be some small problems with the statistics
> page. The Saturday "Contributions in Daylight" seem to be being
> counted in Friday as well. Also, I think some or all of the graphs
> on that page are not being updated.
>
> Thanks again for putting on the contest.

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: Nick Howe

Date: 12 May, 2007 09:54:12

Message: 53 of 221

I want to credit Jim Mikola's entry Juno39 for providing the grist
for my EarlyBird winner. A number of entries were doing better on
small problems than the current leader at the time, so I decided to
try combining them. I had intended to use my own Darkness solution in
this role (and submitted a few attempts that did so) but the
combination with Jim's solution worked the best. Thanks Jim!

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: Matthew Simoneau

Date: 13 May, 2007 09:18:48

Message: 54 of 221

I fixed the bug in the "Contributions in Daylight" section of the
Statistics page that the cyclist noticed. Thanks for letting us know.

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: Gautam Roy

Date: 13 May, 2007 10:26:51

Message: 55 of 221

Hi,
I am trying to use Matlab 6.0 R12. I have changed the anonymous
functions s and tb to
%%%% function s
function ret = s(siz,i,j)
ret = sub2ind(siz,i,j);

%%%%% function tb
function p = tb(p,siz)
all([p>0 p<=[siz(2) siz(1)] ~rem(p,1)]);

Is this correct?

Also I received errors on all if statements which use || or && and
that was solved by changing them to | and & respectively.
Have these operators changed in recent versions ?

After this on runcontest I am getting
ans =

results: 130055.0797
time: 0.59

Is this what i am supposed to get?

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: the cyclist

Date: 13 May, 2007 11:07:38

Message: 56 of 221

Matthew Simoneau wrote:
>
>
> I fixed the bug in the "Contributions in Daylight" section of the
> Statistics page that the cyclist noticed. Thanks for letting us
> know.
  
Thanks! The only issue I see right now on the Statistics page is
that the font on the Contest History graph is huge.

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: Jason Nicholson

Date: 13 May, 2007 22:29:49

Message: 57 of 221

I have been following the last two contests. I am amazed at the
programming ability of many of the contestants. For a senior
mechanical engineering student, I am good with MATLAB. Compared to
what is going on here, I am not in the same league. How have all of
you become such guru's? How do I become a matlab guru?

Note: I started a new thread on the MATLAB Newsgroup page that you
can reply to this. I only posted this message so that some of the
contestants would see and reply.

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: the cyclist

Date: 14 May, 2007 12:55:21

Message: 58 of 221

Matthew Simoneau wrote:
>
>
> I fixed the bug in the "Contributions in Daylight" section of the
> Statistics page that the cyclist noticed. Thanks for letting us
> know.
  

Continuing to be the watchdog of the Stats page ...

I think the Most Active Participants graph is not being updated.

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: Alan Chalker

Date: 14 May, 2007 14:08:25

Message: 59 of 221

For those of you interested, I've posted another heavily commented
version of the leading code as of mid-day today, Monday. The code is
"Guided Tour Part 2" (id: 40979).

Unfortunately, with the number of subfunctions and recursive calls
the code has become much more difficult to understand than in my
previous attempt at this. Hopefully you'll find this of value /
interest.

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: Matthew Simoneau

Date: 14 May, 2007 14:24:09

Message: 60 of 221

cyclist, these images seem to be up-to-date on my end. Your browser
may be caching old versions. Try forcing a reload with ctrl-shift-R
or whatever your browser uses.

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: Leendert Combee

Date: 14 May, 2007 18:42:22

Message: 61 of 221

Alan Chalker wrote:
>
> Unfortunately, with the number of subfunctions and recursive calls
> the code has become much more difficult to understand than in my
> previous attempt at this. Hopefully you'll find this of value /
> interest.
  
I wish I could get the code rewritten without nested functions that
seem to inherit and pass on variables without properly included in
the argument lists. I am on an older Matlab version and just can't
get the first method (based on solveri) to work properly, it's making
wrong moves. I have tried twice, but to no avail. D@mn.

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: the cyclist

Date: 14 May, 2007 19:53:26

Message: 62 of 221

Matthew Simoneau wrote:
>
>
> cyclist, these images seem to be up-to-date on my end. Your
> browser
> may be caching old versions. Try forcing a reload with
> ctrl-shift-R
> or whatever your browser uses.
  
I tried clearing my cache, and I also tried using IE instead of
Firefox, and I still see the same stale graphs.

Subject: Nested functions are evil

From: srach

Date: 15 May, 2007 04:25:31

Message: 63 of 221

Since quite a while I haven't been able to reach the contest site (http://www.mathworks.com/contest/jumping/home.html).
t just diplays a "Page not found" message.

Is this problem related to my internet connection or is the site
down, i.e., does anybody experience the same problem?

Best,
srach

Subject: Nested functions are evil

From: Matthew Simoneau

Date: 15 May, 2007 04:41:21

Message: 64 of 221

srach, the site is back up.

Subject: MATLAB Programming Contest: May 9 - May 16, 2007

From: abdeldjebar

Date: 15 May, 2007 05:32:45

Message: 65 of 221

Helen Chen wrote:
>
>
> Hello Community!
>
> This is just a quick message to let everyone know that the MATLAB
> Contest Masters have been hard at work! They have been crafting a
> really exciting new challenge for our Spring event with some very
> cool prizes waiting for our champions.
>
> It's time to clear your calendars so that you can come join the
> fun!
> The contest will start at noon Eastern time on May 9, ending at
> noon
> on Mary 16th.
>
> We will be announcing more details about the contest as we get
> closer, so if you want a refresher about MATLAB Central contests,
> check out the contest overview page at <http://www.mathworks.com/contest/overview.html>.
> ou can checkout past contests using links on that page.
>
> Stay tuned for more information...
>
> Best wishes,
> Helen Chen
> MATLAB Central Team

Subject: Scoring k_1 k_2 etc.

From: the cyclist

Date: 15 May, 2007 07:43:06

Message: 66 of 221

Shashi Khatri wrote:
>
>
> Has anyone estimated k_1, k_2, k_3 and k_4. It seems like time
> plays
> almost no role in the score!
>
> Isn't the maximum time allowed 180 seconds? How come I'm yet to see
> an entry that takes more than 60 seconds?
>
> Thanks people...
>
> Shashi
  
Alan Chalker posted the following coefficients in the contest blog:

k1 = 0.1
k2 = 2
k3 = 0.05
k4 = 1

Subject: Scoring k_1 k_2 etc.

From: Sergey Yurgenson

Date: 15 May, 2007 08:01:18

Message: 67 of 221

To Shashi,
In a contrary, I think that at the moment time plays too important
role. It is very easy just to improve result, but time penalty will
be significant. So, collective wisdom tells us that current sweet
spot is around 50 sec.
It resembles the situation with Blockbuster contest. However during
BlackBox contest times played less important role and participants
spent more time optimizing actual logic of algorithm then trying to
shave extra 0.01 sec from running time.
Saying that, I have to admit that it is practically impossible to set
coefficients in advance and create perfect result/time balance

SY

Shashi Khatri wrote:
>
>
> Has anyone estimated k_1, k_2, k_3 and k_4. It seems like time
> plays
> almost no role in the score!
>
> Isn't the maximum time allowed 180 seconds? How come I'm yet to see
> an entry that takes more than 60 seconds?
>
> Thanks people...
>
> Shashi

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: the cyclist

Date: 15 May, 2007 13:25:48

Message: 68 of 221

Helen Chen wrote:
>
>
> Hello Community!
>
> This is just a quick message to let everyone know that the MATLAB
> Contest Masters have been hard at work!

Bad timing for "planned server maintenance". I hope Brian Welch
wasn't behind this!

Subject: Scoring k_1 k_2 etc.

From: Shashi Khatri

Date: 15 May, 2007 13:31:02

Message: 69 of 221

Thanks guys.

Another dumb question, the contest is open till Wednesday 12PM EDT,
right?

Sergey Yurgenson wrote:
>
>
> To Shashi,
> In a contrary, I think that at the moment time plays too important
> role. It is very easy just to improve result, but time penalty will
> be significant. So, collective wisdom tells us that current sweet
> spot is around 50 sec.
> It resembles the situation with Blockbuster contest. However during
> BlackBox contest times played less important role and participants
> spent more time optimizing actual logic of algorithm then trying to
> shave extra 0.01 sec from running time.
> Saying that, I have to admit that it is practically impossible to
> set
> coefficients in advance and create perfect result/time balance
>
> SY
>
> Shashi Khatri wrote:
>>
>>
>> Has anyone estimated k_1, k_2, k_3 and k_4. It seems like time
>> plays
>> almost no role in the score!
>>
>> Isn't the maximum time allowed 180 seconds? How come I'm yet to
> see
>> an entry that takes more than 60 seconds?
>>
>> Thanks people...
>>
>> Shashi

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: MikeR

Date: 15 May, 2007 15:48:48

Message: 70 of 221

I have a concern about the contest score calculation, two entries
which are near or at the top currently appear to be identical with
scores differing solely based on computation time.

My entry 'Lions' : ID - 41452 - 2007-05-15 14:26:18 - Score -
3947.6295
and
nathan q's entry 'Filigree Siberian Hamster 2': ID - 41457 -
2007-05-15 14:29:33 - Score - 3947.3199

Performing a diff on these produced no differences, then examining
submission time shows that nathans was submitted after mine.

Is is it explained anywhere the effect of a high number of entries
waiting in the queue and the actual score. I assumed that each file
was tested in the same environment?

Thanks!

PS. This contest is addictive

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: the cyclist

Date: 15 May, 2007 16:05:46

Message: 71 of 221

MikeR wrote:
>
>
> I have a concern about the contest score calculation, two entries
> which are near or at the top currently appear to be identical with
> scores differing solely based on computation time.
>
> My entry 'Lions' : ID - 41452 - 2007-05-15 14:26:18 - Score -
> 3947.6295
> and
> nathan q's entry 'Filigree Siberian Hamster 2': ID - 41457 -
> 2007-05-15 14:29:33 - Score - 3947.3199
>
> Performing a diff on these produced no differences, then examining
> submission time shows that nathans was submitted after mine.
>
> Is is it explained anywhere the effect of a high number of entries
> waiting in the queue and the actual score. I assumed that each file
> was tested in the same environment?
>
> Thanks!
>
> PS. This contest is addictive
  
It is well known (but perhaps not widely known?) that identical
entries will produce identical result but not identical time. This
is not hard to understand when you consider that all the things going
on with the computer that runs the entries. I know that Mathworks
has stripped it down pretty well, and take a lot of measures to keep
timing as consistent as reasonably possible. But it can't be
perfect. Small time-improvement tweaks are swamped by the
variability in timing.

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: Alan Chalker

Date: 15 May, 2007 16:20:00

Message: 72 of 221

the cyclist wrote:
>
> It is well known (but perhaps not widely known?) that identical
> entries will produce identical result but not identical time. This
> is not hard to understand when you consider that all the things
> going
> on with the computer that runs the entries. I know that Mathworks
> has stripped it down pretty well, and take a lot of measures to
> keep
> timing as consistent as reasonably possible. But it can't be
> perfect. Small time-improvement tweaks are swamped by the
> variability in timing.
  

Since the contest is drawing to a close, this presents an opportunity
to start making suggestions for improvements. Its been suggested
many times in the past, but I'll again suggest that the number 1
improvement would be to put a roundoff in the time contribution to
overall score. I think rounding off to the nearest tenth or quarter
of a second would still entice people to try to tweak parameters ,
but would eliminate the variability due to system variations.

On both occasions during this contest when I submitted a heavily
commented version of the leading code, my commented version took the
lead for quite a while. I made no algorithmic changes to the code,
yet due to the fact I submitted them when the queue's were empty and
machine basically idle I got a slight speedup in the run-time. While
that was a nice quirk, it clearly illustrates the variability queue
load has on the timing calculations.

Anybody have any other suggestions for way to improve the contest?

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: Ned Gulley

Date: 15 May, 2007 16:33:16

Message: 73 of 221

MikeR wrote:
>
> I have a concern about the contest score calculation,
> two entries which are near or at the top currently
> appear to be identical with scores differing solely
> based on computation time.

Hi Mike:

The cyclist is right to say that, try as hard as we might (and we do
try) identical files get different running times.

I carefully diff'd the two files you describe, and you're right, they
are identical. If this were a matter of winning the contest (or
winning one of our mini-contest challenges), we would award the prize
to the person who first submitted the code that did the best. In this
case, you would get the prize. But since there's no prize at stake,
we just let stuff like this ride.

As the contest nears its end, people are often working near the
"noise floor" of our measuring capability. They are making tiny
improvements that could easily be negated by a passing cosmic ray. We
like to think that this is part of the charm of the contest. In any
event, we ask that people not intentionally resubmit identical code.
It won't help you win a prize.

-Ned.

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: nathan q

Date: 15 May, 2007 18:08:54

Message: 74 of 221

Hi Mike and all

For the record, these two entries were developed independently. In
fact, according to the "based on" credits, both came from BirdBrain's
Bill Murray's Explosive Gerbil, which was the leader at the time. I
was just fiddling with the obvious parameters - it's not surprising
that two of us would come up with identical tweaks. It's right that
the earlier submission should get the credit if a prize is at stake.

Nathan

PS thanks, Mathworkers, for another great contest.

MikeR wrote:

> My entry 'Lions' : ID - 41452 - 2007-05-15 14:26:18 - Score -
> 3947.6295
> and
> nathan q's entry 'Filigree Siberian Hamster 2': ID - 41457 -
> 2007-05-15 14:29:33 - Score - 3947.3199

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: Jin

Date: 15 May, 2007 21:45:32

Message: 75 of 221

The "Best Result by 4 PM Challenge" seems a bad idea in some senses.
The big tweaking bomb will suppress the all the remaining time of
Tuesday.(100*3/60=5hours) The most are waiting for the random
*magic*. Maybe contest team could add more PCs to process the queue?

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: Alan Chalker

Date: 15 May, 2007 21:53:31

Message: 76 of 221

Jin wrote:
>
>
> The "Best Result by 4 PM Challenge" seems a bad idea in some
> senses.
> The big tweaking bomb will suppress the all the remaining time of
> Tuesday.(100*3/60=5hours) The most are waiting for the random
> *magic*. Maybe contest team could add more PCs to process the
queue?
  

To the contrary, I think this was a brilliant move on their part. By
effectively 'shutting down the feedback loop' they've dropped us into
a 'dusk' like state. Unlike twilight where we can see all the scores
but not the code, here we can see the code but not the scores.
Something like this has been suggested several times in the past as a
way to reduce the effect of last minute tweaking on the final grand
prize winner and put more focus on algorithm development.

I personally hope the queue gets filled up even more overnight such
that tomorrow morning we are in a similar situation.

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: Jin

Date: 15 May, 2007 22:16:22

Message: 77 of 221

AC, if considered for a algorithm development, you are really
right^_^ And I like your well-documented codes^_^

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: Sergey Yurgenson

Date: 16 May, 2007 08:16:06

Message: 78 of 221

Anybody who wants to overload queue and create “dusk” state can
easily do it.
I just do not know if it is consistent with extremely cooperative
spirit of current contest.
On another side, last second meaningless tweak of somebody else
significant code improvement is not good either.

Sergey

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: Steve Hoelzer

Date: 16 May, 2007 10:01:23

Message: 79 of 221

My thoughts on improving future contests:

- Round cpu time to 0.1 sec to avoid timing inconsistencies.

- Add column for cyclomatic complexity.

- Show statistics page earlier in the contest.

- Add a reasonably accurate timestamp of The Mathwork's official time
to the top of the submit page. It doesn't have to be perfect, but it
would help with last minute entries.

- For the 1000 character challenge, don't count whitespace
(whitespace = spaces, tabs, and newlines). That way, entries can have
commands on different lines and keep proper indentation. I included a
simple script below that can do the counting.

All that said, it has been another great contest. Thanks Mathworks
team! Also thanks to all the contestants for the well-commented code
and following the 'no welching' rule.

Steve

------------------------------------------------

function c = charcountnowhitespace(fn)
% Count the characters in a file, excluding whitespace (spaces, tabs,
and
% newlines). Returns the character count, or -1 if file error.
%
% Example call: c = charcountnowhitespace('charcountnowhitespace.m')

% Steve Hoelzer 2007-05-16

fid = fopen(fn);
if fid == -1
    c = -1; % error opening file
    return
end

% Count chars
c = 0;
line = fgetl(fid);
while isempty(line) || line(1) ~= -1
    line(line == 32) = []; % remove spaces
    line(line == 9) = []; % remove tabs
    line(line == 10) = []; % remove newlines
    c = c + length(line);
    line = fgetl(fid);
end

if fclose(fid)
    c = -1; % error closing file
end

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: KSz

Date: 16 May, 2007 10:57:41

Message: 80 of 221

and don't let anyone post a new code five times a minute...

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: the cyclist

Date: 16 May, 2007 12:10:49

Message: 81 of 221

Helen Chen wrote:
>
>
> Hello Community!
>
> This is just a quick message to let everyone know that the MATLAB
> Contest Masters have been hard at work!

So, it's all over but the crying. Thanks to the team for an
exceptionally smooth contest. I was really happy that obfuscation
didn't really enter, and that folks adhered to the request for no
Welching. The most infuriating part of the last couple contests was
when the queue broke down completely, so it was nice that that did
not happen this time around.

Good luck to all entries still in the queue. I estimate that it will
be done processing by around 15:00 EDT, all the entries run in about
the same CPU time as the current leader.

the cyclist (aka "tev")

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: MikeR

Date: 16 May, 2007 12:24:15

Message: 82 of 221

Community,

I concur, this contest has been blast! The Matlab team deserves
thanks for keeping this running without any hitches!

Now we get to eagerly await the final outcome, I have a strong
feeling that "tev" will overtake me. It will be interesting if
another approach bests the current leader.

My effective entry popped a little to early,~10mins, so the masses
have consumed :)

sidenote: Ken Eaton you sure do know how to make this suspenseful.

- MikeR

the cyclist wrote:
>
>
> Helen Chen wrote:
>>
>>
>> Hello Community!
>>
>> This is just a quick message to let everyone know that the
MATLAB
>> Contest Masters have been hard at work!
>
> So, it's all over but the crying. Thanks to the team for an
> exceptionally smooth contest. I was really happy that obfuscation
> didn't really enter, and that folks adhered to the request for no
> Welching. The most infuriating part of the last couple contests
> was
> when the queue broke down completely, so it was nice that that did
> not happen this time around.
>
> Good luck to all entries still in the queue. I estimate that it
> will
> be done processing by around 15:00 EDT, all the entries run in
> about
> the same CPU time as the current leader.
>
> the cyclist (aka "tev")

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: the cyclist

Date: 16 May, 2007 12:56:18

Message: 83 of 221

MikeR wrote:

> It will be interesting if
> another approach bests the current leader.

I am curious what improvements are in the queue. Obviously, there is
some pure parameter tweaking, and that is always a threat.

I personally have two separate time improvements. They are small but
"real", and should both get over the timing variability, I think.

1) I replaced "sum(board(:)>0)" with "nnz(board)".

2) I defined iii=[i;i], and did a wholesale replacement of "i;i" with
"iii", along with a couple related efficiencies. Ditto with jjj.

I had a third replacement that I thought would be an improvement,
which was to define a variable "peg=board(:)>0", which identified
where pegs were. This could be used later in the calculation of the
count of pegs, and a couple of other ways. However, it seems this
did not really improve the time.

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: Hannes Naudé & Cobus Potgieter

Date: 16 May, 2007 13:01:56

Message: 84 of 221

We have been working offline for a bit, so have only now had the
chance to take a look of some of the code in the queue.

We are a bit baffled by how the following code could possibly come to
exist without some probing of the contest suite going on. Yet many
appear to be using it??

fc=((pegCount < 250)||...
    (pegCount==272)||...
    (pegCount==516)||...
    (pegCount==544)||...
    (pegCount==535)||...
    (pegCount==540)||...
    (pegCount==542)||...
    (pegCount==542)||...

To be clear, we are not accusing anyone of anything. just asking...?

Thanks to the Mathworks contest team for one of he best contests yet.

Regards
Hannes & Cobus
a.k.a. Jacob & matlabboy
P.S. Yes we now our aliases and submission titles are stupid but you
do what you can to avoid being picked up by cyc's improvement radar.
Allthough it looks like this time it was Yi that caught us.

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: Sergey Yurgenson

Date: 16 May, 2007 13:29:56

Message: 85 of 221

I want to thank organizers and participants for great competition. It
was a real pleasure to be here. Very good cooperative spirit this
time. (It would be really unfortunate if somebody decided to use
probing. Frankly speaking it just kills competition)

At the end I was trying to introduce three minor algorithm
modifications:

1. Make “random loop” run longer for board with higher mean weight
2. Combine subsol and solveri (run solveri inside subsol when there
are few pegs left) . Too much time penalty here, probably.
3. Count pegs on “black fields and white fields” (imagine that board
is colored as chess board, black pegs always stay black and always
remove white and vise versa) and introduce additional weight
parameter depending on ratio of sizes of two peg groups.

Best wishes to everybody,

Sergey

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: Ken Eaton

Date: 16 May, 2007 13:51:45

Message: 86 of 221

MikeR wrote:
>
> sidenote: Ken Eaton you sure do know how to make this suspenseful.

Is that in reference to my frantic last-minute submissions of what
will likely be unsuccessful attempts?

First I'd like to say thanks to all the MathWorks staff. Although I
am a long time MATLAB user, this was only the first contest I
submitted anything for (I tried for the Black Box, but never finished
anything in time to submit). Unfortunately, for this contest I didn't
have enough time to really dig in and see what other algorithms were
being tried by others. Still had fun though!

Most of my attempts centered around the idea of "black" and "white"
squares competing with one another (mentioned by a few people on
here), hence why I prefaced all my submissions with "predator/prey".
We'll see how my newest ones do (probably not as good as the top
contenders).

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: Joseph

Date: 16 May, 2007 13:57:54

Message: 87 of 221

Tev,

How did you send over 15 tweaks of entries in the queue in less than
2 minutes? That is 1 every 8 seconds! You must have been pedaling
really fast...

Joseph

 MikeR wrote:
>
>
> Community,
>
> I concur, this contest has been blast! The Matlab team deserves
> thanks for keeping this running without any hitches!
>
> Now we get to eagerly await the final outcome, I have a strong
> feeling that "tev" will overtake me. It will be interesting if
> another approach bests the current leader.
>
> My effective entry popped a little to early,~10mins, so the masses
> have consumed :)
>
> sidenote: Ken Eaton you sure do know how to make this suspenseful.
>
> - MikeR
>

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: Yi Cao

Date: 16 May, 2007 14:35:21

Message: 88 of 221

Hannes Naudé & Cobus Potgieter wrote:
>
>
> We have been working offline for a bit, so have only now had the
> chance to take a look of some of the code in the queue.
>
> We are a bit baffled by how the following code could possibly come
> to
> exist without some probing of the contest suite going on. Yet many
> appear to be using it??
>
> fc=((pegCount < 250)||...
> (pegCount==272)||...
> (pegCount==516)||...
> (pegCount==544)||...
> (pegCount==535)||...
> (pegCount==540)||...
> (pegCount==542)||...
> (pegCount==542)||...
>
> To be clear, we are not accusing anyone of anything. just
> asking...?
>
> Thanks to the Mathworks contest team for one of he best contests
> yet.
>
> Regards
> Hannes & Cobus
> a.k.a. Jacob & matlabboy
> P.S. Yes we now our aliases and submission titles are stupid but
> you
> do what you can to avoid being picked up by cyc's improvement
> radar.
> Allthough it looks like this time it was Yi that caught us.

Hannes & Cobus,

Thanks let us know your aliases. I pick up entries submitted by
matboy by chance. This morning, when I opened an IE window to look
the queue, I found a suspicious entry in the queue by matlabboy
without a valid email address. By searching matlabboy I found three
entries. All codes have a return with moves = [0 0 0 0] at the end.
Clearly, these entries is to test some improvement on solveri code.
Therefore, I copied one of these codes into my codes for the final
submission. For the above codes, I found from Jin's entry Iamcrazy31,
I belieave this is a prob series.

I wish to think to Mathwork team to organize this contest. This is a
very interesting problem. One can easily get an idea to improve the
algorithm. However, the time penalty makes many of them. This
morning, I just got an idea to improve the speed. After an hour's
work, finally I made it works. To make this code more valuable, I
waited until almost last minutes to scan the queue to try to catch
some new code to combine with this improvement. Wish myself good
luck.

Yi Cao

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: the cyclist

Date: 16 May, 2007 14:40:45

Message: 89 of 221

Yi Cao wrote:
>
> Thanks let us know your aliases. I pick up entries submitted by
> matboy by chance. This morning, when I opened an IE window to look
> the queue, I found a suspicious entry in the queue by matlabboy
> without a valid email address. By searching matlabboy I found three
> entries. All codes have a return with moves = [0 0 0 0] at the end.
> Clearly, these entries is to test some improvement on solveri code.
> Therefore, I copied one of these codes into my codes for the final
> submission. For the above codes, I found from Jin's entry
> Iamcrazy31,
> I belieave this is a prob series.
>

  
Wow. And I thought I was using radar. I am using two tin cans and a
piece of string compared to this.

I am pretty sure I am out of the running. My best entry will not
beat Yi Cao.

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: Nathan Quinlan

Date: 16 May, 2007 15:07:27

Message: 90 of 221

Hi all

I found a timing improvement in subsol and subsoltweak, in the most
expensive line of code:

validMoves(allMoves) = Bpos(F(allMoves)) & Bzero(T(allMoves)) &
Bpos(M(allMoves));

becomes

for i=1:length(allMoves)
    validMoves(allMoves(i)) = Bpos(F(allMoves(i))) &&
Bzero(T(allMoves(i))) && Bpos(M(allMoves(i)));
end

and knocks about 3 seconds off the runtime. The motivation for this
was to use the short-circuit && operators, but in fact the loop form
is nearly as quick with ordinary &. I don't know why it works - the
vectorised form is just a lot slower. Can anybody explain?

I was pretty pleased with this improvement, but Yi Cao has blown it
away! Well done Yi- maybe there is more to come...?

I was watching the queue in the last few minutes of the contest and
patching the above code into entries from some of the more notorious
competitors in the queue. I even did a diff of Yi's new code against
the current leader, but at a first glance the new code (like the
segment mentioned by Hannes and Cobus) looked like harmless parameter
tuning, so I moved on. I should have known better :)

Thanks again to the organising team, and to all the competitors, for
a great contest.

Nathan

Subject: MATLAB Programming Contest: May 9 - May 16, 2007

From: Yi Cao

Date: 16 May, 2007 15:37:30

Message: 91 of 221

the cyclist wrote:
>
> Wow. And I thought I was using radar. I am using two tin cans and
> a
> piece of string compared to this.
>
> I am pretty sure I am out of the running. My best entry will not
> beat Yi Cao.

Thanks. However, on Tuesday, my entry CollaborationSolver was
submitted with several improvements, but even did not get to the top
because of tuning parameters. But then, I found this entry had been
taken by Jin with other tuning parameters to win the Tusday Push
Prize. It was so sad to me at that time.

Yi

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: the cyclist

Date: 16 May, 2007 15:46:06

Message: 92 of 221

Yi Cao wrote:

> It was so sad to me at that time.

I expect you are feeling better now. Congrats on winning the contest!

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: Yi Cao

Date: 16 May, 2007 15:49:39

Message: 93 of 221

Nathan Quinlan wrote:
>
>
> Hi all
>
> I found a timing improvement in subsol and subsoltweak, in the most
> expensive line of code:
>
> validMoves(allMoves) = Bpos(F(allMoves)) & Bzero(T(allMoves)) &
> Bpos(M(allMoves));
>
> becomes
>
> for i=1:length(allMoves)
> validMoves(allMoves(i)) = Bpos(F(allMoves(i))) &&
> Bzero(T(allMoves(i))) && Bpos(M(allMoves(i)));
> end
>
> and knocks about 3 seconds off the runtime. The motivation for this
> was to use the short-circuit && operators, but in fact the loop
> form
> is nearly as quick with ordinary &. I don't know why it works - the
> vectorised form is just a lot slower. Can anybody explain?
>
> I was pretty pleased with this improvement, but Yi Cao has blown it
> away! Well done Yi- maybe there is more to come...?
>
> I was watching the queue in the last few minutes of the contest and
> patching the above code into entries from some of the more
> notorious
> competitors in the queue. I even did a diff of Yi's new code
> against
> the current leader, but at a first glance the new code (like the
> segment mentioned by Hannes and Cobus) looked like harmless
> parameter
> tuning, so I moved on. I should have known better :)
>
> Thanks again to the organising team, and to all the competitors,
> for
> a great contest.
>
> Nathan

The improvement I submitted was to move most calculations of allMoves
out of the main loop by using a new matrix, rMap. I also tried to do
the same for subsoltweak, but was not successful because the matrix
becomes ao complicated that it take even more time to calculate
before the loop because subsoltweak was lightly used. I also combined
codes from matlabboy, Jin, David Jones and MikeR to make it be the
current top. Thanks to all of you contributed to the code. Wish to
see you all next time.

Yi

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: Alan Chalker

Date: 16 May, 2007 15:58:15

Message: 94 of 221

the cyclist wrote:
>
>
> Yi Cao wrote:
>
>> It was so sad to me at that time.
>
> I expect you are feeling better now. Congrats on winning the
> contest!
  

Congrats Yi. It's another testament to the uniqueness of this
particular competition that you were able to pull together a variety
of small tweaks to create the final winning entry (and not rely just
on parameter tweaking like some others do). I particularly find it
interesting that you neither had the fastest entry in the top ten nor
the best scoring one. You were able to strike a good balance between
the tradeoff of the two components of the score.

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: MikeR

Date: 16 May, 2007 16:01:07

Message: 95 of 221

Yi Cao wrote:
>
>
> Nathan Quinlan wrote:
>>
>>
>> Hi all
>>
>> I found a timing improvement in subsol and subsoltweak, in the
> most
>> expensive line of code:
>>
>> validMoves(allMoves) = Bpos(F(allMoves)) & Bzero(T(allMoves)) &
>> Bpos(M(allMoves));
>>
>> becomes
>>
>> for i=1:length(allMoves)
>> validMoves(allMoves(i)) = Bpos(F(allMoves(i))) &&
>> Bzero(T(allMoves(i))) && Bpos(M(allMoves(i)));
>> end
>>
>> and knocks about 3 seconds off the runtime. The motivation for
> this
>> was to use the short-circuit && operators, but in fact the loop
>> form
>> is nearly as quick with ordinary &. I don't know why it works -
> the
>> vectorised form is just a lot slower. Can anybody explain?
>>
>> I was pretty pleased with this improvement, but Yi Cao has
blown
> it
>> away! Well done Yi- maybe there is more to come...?
>>
>> I was watching the queue in the last few minutes of the contest
> and
>> patching the above code into entries from some of the more
>> notorious
>> competitors in the queue. I even did a diff of Yi's new code
>> against
>> the current leader, but at a first glance the new code (like
the
>> segment mentioned by Hannes and Cobus) looked like harmless
>> parameter
>> tuning, so I moved on. I should have known better :)
>>
>> Thanks again to the organising team, and to all the
competitors,
>> for
>> a great contest.
>>
>> Nathan
>
> The improvement I submitted was to move most calculations of
> allMoves
> out of the main loop by using a new matrix, rMap. I also tried to
> do
> the same for subsoltweak, but was not successful because the matrix
> becomes ao complicated that it take even more time to calculate
> before the loop because subsoltweak was lightly used. I also
> combined
> codes from matlabboy, Jin, David Jones and MikeR to make it be the
> current top. Thanks to all of you contributed to the code. Wish to
> see you all next time.
>
> Yi
  

Good Job Yi,

You were quick to incorporate all the improvements that had been
posted.

I will be very interested in understanding what the test machine
threw at the scripts. I optimized my entries largely to reduce scores
and secondly to reduce processing time. Alan Chalker pointed out in
his summary yesterday the interesting relationship between time and
score.

Unfortunately the test machine must be very different from my
computer because dramatic improvements on my machine were always
registered as steps backwards on the test machine.

Overall a very interesting and exciting contest. I look forward to a
post analysis and the next contest.

- MikeR

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: Alan Chalker

Date: 16 May, 2007 16:07:30

Message: 96 of 221

the cyclist wrote:
>
> So, it's all over but the crying. Thanks to the team for an
> exceptionally smooth contest. I was really happy that obfuscation
> didn't really enter, and that folks adhered to the request for no
> Welching. The most infuriating part of the last couple contests
> was
> when the queue broke down completely, so it was nice that that did
> not happen this time around.
>

I have to second your sentiments here. Hopefully having a very
'clean' contest will set a precedence for future contests. It
definitely made it more enjoyable throughout. Now if only something
can be done to reduce the amount of parameter tweaking without
completely eliminating it from the equation........

See you all in the Fall.

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: Yi Cao

Date: 16 May, 2007 16:59:49

Message: 97 of 221

Nathan Quinlan wrote:
>
> I found a timing improvement in subsol and subsoltweak, in the most
> expensive line of code:
>
> validMoves(allMoves) = Bpos(F(allMoves)) & Bzero(T(allMoves)) &
> Bpos(M(allMoves));
>
> becomes
>
> for i=1:length(allMoves)
> validMoves(allMoves(i)) = Bpos(F(allMoves(i))) &&
> Bzero(T(allMoves(i))) && Bpos(M(allMoves(i)));
> end
>
> and knocks about 3 seconds off the runtime. The motivation for this
> was to use the short-circuit && operators, but in fact the loop
> form
> is nearly as quick with ordinary &. I don't know why it works - the
> vectorised form is just a lot slower. Can anybody explain?
>
I just tried two different versions:

1)
    for i=1:length(allMoves)
        ii=allMoves(i);
        validMoves(ii)=Bpos(F(ii)) && Bpos(M(ii)) && Bzero(T(ii));
    end
This reduces my winning code time from 31 sec to 28 sec on my PC.

2)
    for i=allMoves
        validMoves(i)=Bpos(F(i)) && Bpos(M(i)) && Bzero(T(i));
    end
Initially, I thought the second version should be quiker because it
saves time to calculate the index. However, time actually increases
to 50 seconds!

All these are due to JIT acceleration. The first version is more
standard, hence it is a simple loop for JIT to accelerate. The second
version looks more clever, but for JIT, it is non-simple loop, hence
refuces to accelerate it. A good explaination about JIT is available
on the contest website: <http://www.mathworks.com/contest/protein.cgi/jitstory.html>

But personally, I am not used to work with JIT. Vectorization is
still my favorable way to solve problems. I delight to see
vectorization played a central role in this contest

Yi

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: n

Date: 16 May, 2007 18:50:16

Message: 98 of 221

Yi,

thanks for that note, and congratulations on a stylish win.

Nathan

 Yi Cao wrote:

> I just tried two different versions:
>
> 1)
> for i=1:length(allMoves)
> ii=allMoves(i);
> validMoves(ii)=Bpos(F(ii)) && Bpos(M(ii)) && Bzero(T(ii));
> end
> This reduces my winning code time from 31 sec to 28 sec on my PC.
>
> 2)
> for i=allMoves
> validMoves(i)=Bpos(F(i)) && Bpos(M(i)) && Bzero(T(i));
> end
> Initially, I thought the second version should be quiker because it
> saves time to calculate the index. However, time actually increases
> to 50 seconds!
>
> All these are due to JIT acceleration. The first version is more
> standard, hence it is a simple loop for JIT to accelerate. The
> second
> version looks more clever, but for JIT, it is non-simple loop,
> hence
> refuces to accelerate it. A good explaination about JIT is
> available
> on the contest website: <http://www.mathworks.com/contest/protein.cgi/jitstory.html>
>
> But personally, I am not used to work with JIT. Vectorization is
> still my favorable way to solve problems. I delight to see
> vectorization played a central role in this contest
>
> Yi

Subject: MATLAB Programming Contest: May 9 - May 16, 2007

From: Volkan

Date: 16 May, 2007 19:29:17

Message: 99 of 221

Congratulations Yi, it is nice to see the contest being won by some
strategy other than random parameter tweaking, or obfuscation.

Speaking of which, thank you Alan for your great and selfless effort
on documenting the code. I had to stay on the spectator side for this
contest, and you are the one who made it possible for me to keep up
until the end.

Volkan,

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: Jin

Date: 16 May, 2007 19:47:21

Message: 100 of 221

Yi Cao and other participants,
My Iamcrazy series is really a probe series in the last segement.
This probe is based on the analysis of two solver. In the big
pegCount board, the solveri is very slower than subsol. But I find
even in the this case there are relatively big improvement for
solveri im sample testsuite. I do a detail analysis to testsuite to
try to understand the well condition of solveri. I failed. The subsol
is 2-step-lookfor based algorithm, a strategy-fixed algorithm. So,in
some case, this algorithm is definitely not good. And So I think do
some probes may be not bad. Then I do about 30 probes in 3-4 hours.
Then...
One thing I must say I do *NOT* like tweaking bomb. And I will *NOT*
do this. For my case, I just do some fit(smart) probes to improve the
fun of contest. In the last segement(several hours), it is hard to
develope a new algorithm to beat the Highly *MAGIC* entries(before my
probes, such as ddlist, rand(57,1)...). We know it is impossible to
build one code to win in all cases. This leave magic to the every ML
contests.
Jin

Subject: MATLAB Programming Contest: May 9 - May 16, 2007

From: Volkan

Date: 16 May, 2007 21:18:15

Message: 101 of 221

By the way, somethings fishy about complexity values.

Contest winner 'Buy a ticket' and second place holder 'buy two
tickets' differ only by the following lines:

Buy a ticket has:
if (pegCount < 272) && (fill < .96)*(score < maxsum*0.775)

While the line is replaced by the following in buy two tickets:
fc=((pegCount < 250)||...
    (pegCount==272)||...
    (pegCount==516)||...
    (pegCount==544)||...
    (pegCount==535)||...
    (pegCount==540)||...
    (pegCount==542)||...
    (pegCount==542)||...
    ((pegCount>251)&&(pegCount<271))||...
    ((pegCount>550)&&(pegCount<555)))...
    &&(fill < .96)*(score < maxsum*0.775);
if fc

However, Buy a ticket has a complexity of 10, while buy two tickets
claims it to be as large as 21. Any ideas?

Subject: MATLAB Programming Contest: May 9 - May 16, 2007

From: Jin

Date: 16 May, 2007 21:46:28

Message: 102 of 221

Volkan:

'Buy a ticket' has not combined with my guessed *magic* number. The
*magic* number can improve the results but waste more time. for cyc -
21 and 10, there are a trick not employed by YiCao. That is,
converting "||" to "|".( I'm not sure whether this is a bug or not,
but it really works.) If cyc goes from 21 to 10(or11), maybe 'buy two
tickets' will win.

Jin

Subject: Scores

From: CopyCat

Date: 17 May, 2007 01:54:44

Message: 103 of 221

Can the MATLAB team post the best score they were able to get from
their solution - just to compare with how close the leading entry
came.

This was my first contest and I am amazed at how well people code. I
am addicted. Looking forward to Fall contest.

Vishal

Subject: MATLAB Programming Contest: May 9 - May 16, 2007

From: Hannes Naudé

Date: 17 May, 2007 02:20:50

Message: 104 of 221

WARNING : LONG POST WITH RAMBLING SENTENCES ! ;-)

Hi all

Just a couple of random thoughts.

Firstly, my subjective opinion is that the amount of algorithmic
"heavy lifting" that goes into contest entries has declined
significantly since the early contests. It seems as if the algorithm
developers are one by one realising that they can't compete with
heavily tweaked and tuned leaders during daylight.

My first contest was trucking and I remember completely new
"homebrew" solvers being added to the mix throughout the run of the
contest. A quick look at the "differences from winner" plot reveals
that the leading code at the start of the final day still differed by
70-80% from the final winning code. This plot hasn't been present in
recent contest evolution reports so it is hard to make direct
comparisons and they may be spurious anyway.

Some other circumstantial evidence for the theory that fewer and
fewer people are focussing on algorithms is the fact that the leading
solvers were optimising an objective function that was WRONG and can
be shown to be wrong with a fairly elementary argument. Fixing this
objective function would have a significant impact, but apparently no
one picked up on it. Perhaps because we were all too busy adjusting
random seeds and shaving picoseconds off runtime ;-). This lasted
right up until the point where Yi's entries made it through the
queue. I think it is safe to say that after 7 days we are still quite
far away from a near-optimal solution.

Anyway, now that that is off my mind, some constructive suggestions.

Firstly it would be very nice if the contest machinery allowed one to
schedule a posting. In other words, when you submit an entry you can
choose to only have it appear at a later time. It may actually be
processed by the server earlier, but will only appear on the queue
when the scheduled time arrives (If it has allready been processed it
can appear directly on the rankings). This will significantly ease
the load on the contest server during submission "rush hour", it
hugely decrease the amount of time that is required for the queue to
finish processing entries after a given deadline has passed, and it
levels the playing field for those of us in other time zones and on
dial-up connections.

I can only assume that the above suggestion may very well fall into
the category of "Nice idea, but we don't have the time to implement
it." and I fully understand that, which brings me to my secnd
suggestion.

The entire contest is run in the spirit of open source so why not
extend this to the contest machinery. If the community agrees that a
specific change would be a good thing (I think there is fairly wide
agreement on a submission CAPTCHA for example) and the contest
machinery code is available, I am sure there would be volunteers to
implement the proposed changes. In the past making the code for the
contest machinery visible may have been considered a security risk
but since contest hacking and probing has now been consigned to the
dusbin of history based on the honour system, this is no longer a
concern.

Sorry for the long post and thanks again to all contestants and
especially the contest team for making this a brilliant event.

Regards
Hannes Naudé

Subject: MATLAB Programming Contest: May 9 - May 16, 2007

From: Yi Cao

Date: 17 May, 2007 04:13:45

Message: 105 of 221

Jin wrote:
>
>
> Volkan:
>
> 'Buy a ticket' has not combined with my guessed *magic* number. The
> *magic* number can improve the results but waste more time. for cyc
> -
> 21 and 10, there are a trick not employed by YiCao. That is,
> converting "||" to "|".( I'm not sure whether this is a bug or not,
> but it really works.) If cyc goes from 21 to 10(or11), maybe 'buy
> two
> tickets' will win.
>
> Jin

Does that mean cyc disencourages probing?

Yi

Subject: MATLAB Programming Contest: May 9 - May 16, 2007

From: Sergey Yurgenson

Date: 17 May, 2007 07:12:37

Message: 106 of 221

1.
“Firstly it would be very nice if the contest machinery allowed one
to schedule a posting. In other words, when you submit an entry you
can choose to only have it appear at a later time. It may actually be
processed by the server earlier, but will only appear on the queue
when the scheduled time arrives”

Really good idea. Poor man modification of this idea may be something
like:
“If submission title contains word ‘final’ time stamp it but do not
put it into queue until deadline”
It will resolve only one issue mentioned by Hannes Naudé, but,
probably,much easy to implement

2.
“Does that mean cyc disencourages probing?”
Probably not. Looks like all “||” are counted as nested loops. One
can use switch… case and avoid cyc penalty.

Regards,
Sergey

Subject: MATLAB Programming Contest: May 9 - May 16, 2007

From: Sergey Yurgenson

Date: 17 May, 2007 07:27:55

Message: 107 of 221

Erratum:

I mean “nested ifs” not “nested loops”

Sergey

 Sergey Yurgenson wrote:
>
>
> 1.
> “Firstly it would be very nice if the contest machinery allowed one
> to schedule a posting. In other words, when you submit an entry you
> can choose to only have it appear at a later time. It may actually
> be
> processed by the server earlier, but will only appear on the queue
> when the scheduled time arrives”
>
> Really good idea. Poor man modification of this idea may be
> something
> like:
> “If submission title contains word ‘final’ time stamp it but do not
> put it into queue until deadline”
> It will resolve only one issue mentioned by Hannes Naudé, but,
> probably,much easy to implement
>
> 2.
> “Does that mean cyc disencourages probing?”
> Probably not. Looks like all “||” are counted as nested loops. One
> can use switch… case and avoid cyc penalty.
>
> Regards,
> Sergey

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: srach

Date: 17 May, 2007 08:09:20

Message: 108 of 221

Congrats to Yi Cao for winning the final contest with an entry
leading to such a big improvement in score.

Moreover, thanks to the contest team for making this such a smooth
and interesting contest. And of course, thanks to all contestants.

Hope to see you all in Fall,
srach

Subject: MATLAB Programming Contest: May 9 - May 16, 2007

From: Yi Cao

Date: 17 May, 2007 08:25:38

Message: 109 of 221

Sergey Yurgenson wrote:
>
>
> 1.
> “Firstly it would be very nice if the contest machinery allowed one
> to schedule a posting. In other words, when you submit an entry you
> can choose to only have it appear at a later time. It may actually
> be
> processed by the server earlier, but will only appear on the queue
> when the scheduled time arrives”
>
> Really good idea. Poor man modification of this idea may be
> something
> like:
> “If submission title contains word ‘final’ time stamp it but do not
> put it into queue until deadline”
> It will resolve only one issue mentioned by Hannes Naudé, but,
> probably,much easy to implement
>
> 2.
> “Does that mean cyc disencourages probing?”
> Probably not. Looks like all “||” are counted as nested loops. One
> can use switch… case and avoid cyc penalty.
>
> Regards,
> Sergey

OK, I see the point. As Jin suggested, replacing all || to | and &&
to & can reduce cyc to 10. Hence it can save 11 points in the score.
In this case, "buy two tickets" would be the winner.

Yi

Subject: MATLAB Programming Contest: May 9 - May 16, 2007

From: Sergey Yurgenson

Date: 17 May, 2007 09:31:33

Message: 110 of 221

Replacing || by | will generate small time penalty (probably not
significant).
“The real winner” I think is “but four tickets”.
In any case, congratulations with wonderful job.

Sergey

 Yi Cao wrote:
> OK, I see the point. As Jin suggested, replacing all || to | and &&
> to & can reduce cyc to 10. Hence it can save 11 points in the
> score.
> In this case, "buy two tickets" would be the winner.
>
> Yi

Subject: MATLAB Programming Contest: May 9 - May 16, 2007

From: Jin

Date: 17 May, 2007 10:20:27

Message: 111 of 221

Yeah, the "but four tickets" has passed by the subsol and save some
seconds^_^
Jin

Subject: MATLAB Programming Contest: May 9 - May 16, 2007

From: Jin

Date: 17 May, 2007 10:35:14

Message: 112 of 221

The constranit of cyc<=10 may be just used to reduce the
complexity of programme. Maybe the constranit is not very useful.
Jin
>
> Does that mean cyc disencourages probing?
>
> Yi

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: Farhad

Date: 17 May, 2007 11:45:10

Message: 113 of 221

I would like to congratulate Yi Cao for winning this contest and also
the Matlab contest team for organizing another exicting contest. I
would like to especilly thank Lucio for being so responsive on the
first day of the contest.

I have participated in the last three contests of Matlab and I am
glad that this time someone won the contest who has throughly
contribued to the developement of winning code in all stages of the
contest, not a tweaker or a prober.

In the current format of the contest, there is simple strategy that
one can pick and have a high chance to win the grand prize: In the
last minutes of the contest, look into each entry, pick any parameter
from that entry and just change it by +/- 0.5% and submit two new
enteries based on that.

There have been several nice suggestions on how to make this contest
better. If they take time to implement, I woule like to reiterate one
which is fairly simple to implement: After darkness, let each day be
a twilight phase on its own where we can see the enteries from
previous days but not the ones from the current day. This way, both
objetive of fairness and cooperation can be achieved.

 Jin wrote:
>
>
> The constranit of cyc<=10 may be just used to reduce the
> complexity of programme. Maybe the constranit is not very useful.
> Jin
>>
>> Does that mean cyc disencourages probing?
>>
>> Yi

Subject: MATLAB Programming Contest: May 9 - May 16, 2007

From: Jin

Date: 17 May, 2007 11:46:03

Message: 114 of 221

" after 7 days we are still quite far away from a near-optimal
solution".
I definitely argee with you. One example is mentioned in the
mid-contest analysis by Lucio. However, this mid-contest analysis is
very far from mid-contest^_^ One thing, to my interesting, is who
consider the ideas mentioned by Lucio carefully. I think his solution
seem very promising in the small-scale peg's case. I sugguest doing
some discuss this agorithm more.
Jin

 Hannes Naudé wrote:
>
>
> WARNING : LONG POST WITH RAMBLING SENTENCES ! ;-)
>
> Hi all
>
> Just a couple of random thoughts.
>
> Firstly, my subjective opinion is that the amount of algorithmic
> "heavy lifting" that goes into contest entries has declined
> significantly since the early contests. It seems as if the
> algorithm
> developers are one by one realising that they can't compete with
> heavily tweaked and tuned leaders during daylight.
>
> My first contest was trucking and I remember completely new
> "homebrew" solvers being added to the mix throughout the run of the
> contest. A quick look at the "differences from winner" plot reveals
> that the leading code at the start of the final day still differed
> by
> 70-80% from the final winning code. This plot hasn't been present
> in
> recent contest evolution reports so it is hard to make direct
> comparisons and they may be spurious anyway.
>
> Some other circumstantial evidence for the theory that fewer and
> fewer people are focussing on algorithms is the fact that the
> leading
> solvers were optimising an objective function that was WRONG and
> can
> be shown to be wrong with a fairly elementary argument. Fixing this
> objective function would have a significant impact, but apparently
> no
> one picked up on it. Perhaps because we were all too busy adjusting
> random seeds and shaving picoseconds off runtime ;-). This lasted
> right up until the point where Yi's entries made it through the
> queue. I think it is safe to say that after 7 days we are still
> quite
> far away from a near-optimal solution.
>
> Anyway, now that that is off my mind, some constructive
> suggestions.
>
> Firstly it would be very nice if the contest machinery allowed one
> to
> schedule a posting. In other words, when you submit an entry you
> can
> choose to only have it appear at a later time. It may actually be
> processed by the server earlier, but will only appear on the queue
> when the scheduled time arrives (If it has allready been processed
> it
> can appear directly on the rankings). This will significantly ease
> the load on the contest server during submission "rush hour", it
> hugely decrease the amount of time that is required for the queue
> to
> finish processing entries after a given deadline has passed, and it
> levels the playing field for those of us in other time zones and on
> dial-up connections.
>
> I can only assume that the above suggestion may very well fall into
> the category of "Nice idea, but we don't have the time to implement
> it." and I fully understand that, which brings me to my secnd
> suggestion.
>
> The entire contest is run in the spirit of open source so why not
> extend this to the contest machinery. If the community agrees that
> a
> specific change would be a good thing (I think there is fairly wide
> agreement on a submission CAPTCHA for example) and the contest
> machinery code is available, I am sure there would be volunteers to
> implement the proposed changes. In the past making the code for the
> contest machinery visible may have been considered a security risk
> but since contest hacking and probing has now been consigned to the
> dusbin of history based on the honour system, this is no longer a
> concern.
>
> Sorry for the long post and thanks again to all contestants and
> especially the contest team for making this a brilliant event.
>
> Regards
> Hannes Naudé

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: Yi Cao

Date: 17 May, 2007 12:18:10

Message: 115 of 221

Farhad wrote:
>
>
> I would like to congratulate Yi Cao for winning this contest and
> also
> the Matlab contest team for organizing another exicting contest. I
> would like to especilly thank Lucio for being so responsive on the
> first day of the contest.
>
> I have participated in the last three contests of Matlab and I am
> glad that this time someone won the contest who has throughly
> contribued to the developement of winning code in all stages of the
> contest, not a tweaker or a prober.
>
> In the current format of the contest, there is simple strategy that
> one can pick and have a high chance to win the grand prize: In the
> last minutes of the contest, look into each entry, pick any
> parameter
> from that entry and just change it by +/- 0.5% and submit two new
> enteries based on that.
>
> There have been several nice suggestions on how to make this
> contest
> better. If they take time to implement, I woule like to reiterate
> one
> which is fairly simple to implement: After darkness, let each day
> be
> a twilight phase on its own where we can see the enteries from
> previous days but not the ones from the current day. This way, both
> objetive of fairness and cooperation can be achieved.
>
I wish to support this idea. Maybe not exactly one day delay, but a
few hours at least? We wish to encourage true algorithm development.

Yi

Subject: MATLAB Programming Contest: May 9 - May 16, 2007

From: Yi Cao

Date: 17 May, 2007 13:06:42

Message: 116 of 221

Jin wrote:
>
>
> " after 7 days we are still quite far away from a near-optimal
> solution".
> I definitely argee with you. One example is mentioned in the
> mid-contest analysis by Lucio. However, this mid-contest analysis
> is
> very far from mid-contest^_^ One thing, to my interesting, is who
> consider the ideas mentioned by Lucio carefully. I think his
> solution
> seem very promising in the small-scale peg's case. I sugguest doing
> some discuss this agorithm more.
> Jin
>
I have thought this direction, but do not have time to develop. The
key point here is that different solutions can be compared in several
subsections. In this way, we can reduce the number of total
combinations to a manageable level. Since we have significantly
improved the efficiency of subsol, here is my rough idea to implement
such comparison:

1. prepara the initial moves suing subsol get moves and scores
corresponding to each move.
2. set t=1;
3. call a recurrent function to find an improvement to the reference
moves:

Inputs to the recurrent function:
Bpos, Bzero, Bmax, rMap, F, M, T, moves, scores and t

Output of the recurrent function:
new_moves, new_scores

In the function:
1) find validMoves
2) loop to go through each element of valid Moves
3) at k element, form a new_move and score for step t.
4) update Bpos, Bzero and Bmax based on the t step of the reference
moves and update another set of Bpos, Bzero, Bmax based on the t step
of the new moves.
5) if 2 sets of Bpos and Bzero are equal, then this section of the
new move is parallel to the reference move. Compare sum of score of
this section between new_move and reference move and return the
better one.
6) if not equal, then parallel section has not been found. Hence, we
need one step further. Call the recurrent function again.

Current subsol tries to optimize each step of moves, but the above
algorithm aims to optimize a section of moves, hence should be
better. If the comparison includes Bmax, then it will be the true
optimal solution. But, it will take more steps to get converged or
may even never get converged hence runing out of time. To avoid
runing over time, we have to limit the maximum number of recureent
calls. If the maximum step reaches, them we assume we faild to find
parallel sections. We have to change the mode to single step optimal
from that point to the end.
If you wish to test this idea, please let me know the outcome.

Yi

Subject: MATLAB Programming Contest: May 9 - May 16, 2007

From: Sergey Yurgenson

Date: 17 May, 2007 13:32:00

Message: 117 of 221

Very interesting.
One simpler (and much faster) modification of this approach maybe
based on the fact that in our current version we are calculating
multiple paths already.
One can cheek if those solutions are intercepting each other
somewhere on graph and then choose the best segment.

Sergey

 Yi Cao wrote:
>
>
> I have thought this direction, but do not have time to develop. The
> key point here is that different solutions can be compared in
> several
> subsections. In this way, we can reduce the number of total
> combinations to a manageable level. Since we have significantly
> improved the efficiency of subsol, here is my rough idea to
> implement
> such comparison:
>
> 1. prepara the initial moves suing subsol get moves and scores
> corresponding to each move.
> 2. set t=1;
> 3. call a recurrent function to find an improvement to the
> reference
> moves:
>
> Inputs to the recurrent function:
> Bpos, Bzero, Bmax, rMap, F, M, T, moves, scores and t
>
> Output of the recurrent function:
> new_moves, new_scores
>
> In the function:
> 1) find validMoves
> 2) loop to go through each element of valid Moves
> 3) at k element, form a new_move and score for step t.
> 4) update Bpos, Bzero and Bmax based on the t step of the reference
> moves and update another set of Bpos, Bzero, Bmax based on the t
> step
> of the new moves.
> 5) if 2 sets of Bpos and Bzero are equal, then this section of the
> new move is parallel to the reference move. Compare sum of score of
> this section between new_move and reference move and return the
> better one.
> 6) if not equal, then parallel section has not been found. Hence,
> we
> need one step further. Call the recurrent function again.
>
> Current subsol tries to optimize each step of moves, but the above
> algorithm aims to optimize a section of moves, hence should be
> better. If the comparison includes Bmax, then it will be the true
> optimal solution. But, it will take more steps to get converged or
> may even never get converged hence runing out of time. To avoid
> runing over time, we have to limit the maximum number of recureent
> calls. If the maximum step reaches, them we assume we faild to find
> parallel sections. We have to change the mode to single step
> optimal
> from that point to the end.
> If you wish to test this idea, please let me know the outcome.
>
> Yi

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: Jimmy Ray

Date: 17 May, 2007 14:22:29

Message: 118 of 221

Having peripherally participated in this contest, I would like to
second the motion. I think each day should be twilight, independent
of the day before. This levels the playing field for all our
international participants and those of us with full-time jobs!

Thanks to the Mathworks team for a fun distraction.

 Farhad wrote:

> There have been several nice suggestions on how to make this
> contest
> better. If they take time to implement, I woule like to reiterate
> one
> which is fairly simple to implement: After darkness, let each day
> be
> a twilight phase on its own where we can see the enteries from
> previous days but not the ones from the current day. This way, both
> objetive of fairness and cooperation can be achieved.

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: srach

Date: 17 May, 2007 14:53:19

Message: 119 of 221

Yi Cao wrote:
...
> To avoid
> runing over time, we have to limit the maximum number of recureent
> calls.

I guess finding that this limit would not be a problem, since the
contest engine already limited the number of recursions to 100.
Trying to code a recursive connectivity graph, this limit seemed to
me quite harsh.

Another thing that crossed my mind, how about awarding Alan Chalker
with a "Fair Play" price or such. The "guided tour ..."
submissions,his comments about the weighting coefficients of the
score calculation and the relation between time and results seemed
really helpful to me and supported the idea of the contest.

Best,
srach

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: Nathan

Date: 17 May, 2007 16:08:48

Message: 120 of 221

Hi Hannes

> Some other circumstantial evidence for the theory that fewer and
> fewer people are focussing on algorithms is the fact that the
> leading solvers were optimising an objective function that was
WRONG
> and can be shown to be wrong with a fairly elementary argument.

Are you referring to the objective function C0+CV*d? Score of first
move + weight*(score of second move), as I understand it. It seems
weird that this works with weight values far from 1, but the
fundamental flaw with the function itself is not obvious to me. Could
you elaborate on your comment?

thanks

Nathan

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: Alan Chalker

Date: 17 May, 2007 16:45:27

Message: 121 of 221

Yi Cao wrote:
>
>

> I wish to support this idea. Maybe not exactly one day delay, but a
> few hours at least? We wish to encourage true algorithm
> development.
>
> Yi
  

For all those calling for changes to eliminate the ability to tweak
and just focus on 'algorithm development', please keep in mind that
The Mathworks runs these contests to engage and excite the MATLAB
community AT LARGE. A balance needs to be struck between those
people with the time and expertise to really dive deep into the
problem at hand and those people who just want to be more
superficially involved (yet potentially learn something new about
MATLAB).

I'd suggest that the balance is reasonably good right now, due to the
fact that the vast majority of the winners for the past few
competitions haven't been 'tweakers'. However, as I suggested
earlier, there are small changes that could be made to the contest
mechanisms that wouldn't eliminate the ability the parameter tweak,
yet would drastically improve the experience of 'algo guys'.

The sub-contests are obviously geared towards different types of
players. The Tuesday leap is an algorithm improvement one, whereas
the Sunday push is a tweaking one.

Also, I think the Contest team is sensitive to the various time zones
involved. Just look at the range of end times for the various
sub-contests we just had. Everything from 9AM, Noon, 4PM, 9PM to
Midnight. This covers most of the possible time zones. Perhaps a
4-5AM one could be added in the future to cover the only gap that
exists.

All in all, I think the Contest Team does a really good job of trying
to cater to the spectrum of possible participants (except of course
for maybe us 'white-hat' types who want to probe and hack a bit;) and
should be commended for what is clearly a difficult task.

Any event like this will obviously evolve and improve based upon
lessons learned. As you make suggestions to the Content Team, please
keep these points in mind and maintain the proper mindset regarding
these wonderful and cost-free (to us at least) events that regularly
held for OUR enjoyment.

I'm sure I echo the sentiments of all the participants when I say
THANK YOU once again to the Contest Team and The Mathworks management
for holding these events. Please let us know if there is anything we
can do to encourage or facilitate the contests in the future.

Subject: MATLAB Programming Contest: May 9 - May 16, 2007

From: Yi Cao

Date: 17 May, 2007 17:26:34

Message: 122 of 221

Jin wrote:

> very far from mid-contest^_^ One thing, to my interesting, is who
> consider the ideas mentioned by Lucio carefully. I think his
> solution
> seem very promising in the small-scale peg's case. I sugguest doing
> some discuss this agorithm more.

Has anyone tried Lucio's function? I just found it does not work with
even very small problems, such as the first board in the testsuit. ML
gives an error. I think it is simply because
sum(2.^(numel(hs)-1:-1:0)) is too large to be used as a size to
construct a sparse matrix.

Yi

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: David Jones

Date: 17 May, 2007 19:14:16

Message: 123 of 221

Alan Chalker wrote:
>
> The Mathworks runs these contests to engage and excite the MATLAB
> community AT LARGE. A balance needs to be struck between those
> people with the time and expertise to really dive deep into the
> problem at hand and those people who just want to be more
> superficially involved (yet potentially learn something new about
> MATLAB).
>
> I'd suggest that the balance is reasonably good right now, ...

I just want to add my voice in agreement with Alan Chalker.

The Matlab Contest, as it is currently organized,
provides something that is ENGAGING and EXCITING
for a wide variety of people who use Matlab and
want to learn more and improve (or show off) their skills.
I hope the organizers will stick with the current contest format.

Perhaps Darkness or Twilight winners deserve greater respect
for their own algorithmic insights, ... but through the rest
of the contest the actual algorithmic insights that arise
are remarkably few and far between. We rarely see wholesale
shifts from one high-level algorithm to another.
Instead, we see incremental changes at various levels.
Yes, realizing an advantage by "padding" the board
is more "algorithmic" than realizing that "nnz(B(:)>0)"
is faster than "sum(B(:)>0)", but in the end they are
both incremental and the main algorithm remains the same.

In previous contests, winners have *sometimes* been rewarded
for ignoring the ongoing tweakfest and focusing on their
own independent algorithm development ... which then needs
to be kept secret and submitted at the last strategic moment.

A big difference between writing efficient programs
in Matlab versus "C" is recognizing how to "vectorize"
your algorithm and eliminate things like "for" loops.

I have equal respect for a Tuesday Leap winner
who dreams up a new algorithm that suddenly takes the lead
by a wide margin and another contest winner who recognizes
a major speedup of the same algorithm that further advances
the lead by a wide margin. Which is more insightful?
the algorithm change or the program tweak? I'd say, ...
the one that makes the larger leap.

We could debate endlessly whether adding randomization
to an algorithm is insightful or just a tweak ...

... but I think over the years the Matlab Contest organizers
have optimized the contest format to be engaging and exciting
for a wide variety of Matlab users and I hope they keep it
pretty much the same for future contets.

Regards,
  David Jones

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: David Jones

Date: 17 May, 2007 19:15:54

Message: 124 of 221

Congratulations to the organizers for another great Matlab contest!

Everything ran smoothly. I only noticed two tiny glitches:
with just a brief bug-fix in the sample code,
and the queue stalled late one night.

... and Congratulations to all the prize winners on well-deserved
victories.

I would like to share some thoughts and feedback.

In terms of suggestions for future contests, ...

(1) add a "captcha" to the entry submission form.

As Markus already suggested, this will slow the pace of tweakers
filling up the queue. Most importantly, it will prevent
the automated submission (by software) of dozens of entries per
second.

I don't think we want to go any further than that, since tweakers
do seem to play an important role to the optimizations that emerge
over the course of the contest. It would also be difficult to
police
any limits on submissions per hour, since people can use aliases.

(2) keep the "Best Result by 4pm Challenge" (as a way to create
"dusk")

I agree with Alan Chalker, the "Best Result ..." prize
was a brillant move. When the queue filled up with these
3-minute programs, it allowed people to see code, but not the
results
and encouraged most people to think more about algorithm development
instead of simple tweaks as we got closer to the end of the contest.
It also encouraged people to think about how to program
the optimal tradeoff between: better results and better times
to get the best overall score near the 2 critical execution times
(60 and 180 seconds).

(As far as I can tell, a good understanding of this "tradeoff"
is how Yi Cao score the impressive victory.)

I don't think there is any need to create an official "dusk" period,
since it worked out so well in this contest.

(3) add more "high level" algorithm description to the mid-contest
analysis

Everyone appreciated Alan Chalker commenting the code,
which also improved upon my "dreamland" series to take the lead,
so he gets double credit for that.

In addition to his line-by-line comments, I think it would be
particularly educational for participants who have less expertise
if there was also more of a high-level roadmap of the leading entry.
To many programmers, I think the comments still remain rather
cryptic
because they don't know how each step fits into the big picture.

Perhaps Lucio Cetto could take on the role of high-level algorithm
description.

For example, Alan's comments indicated the board was being padded
by rows and columns of -1's, but didn't really explain why this was
beneficial, or why that number of rows and columns were chosen.
Of course, experts realized this saved time by eliminating the need
to check boundary conditions when considering possible moves.

Also, some Matlab novices would appreciate an explicit explanation
about how 2 different algorithms could be combined in one
submission,
since "solveri()" gave better results, but was only fast enough on
smaller boards.
Again, this was obvious to many participants, but it would be nice
to make the contest accessible to more Matlab programmers.

And finally, I bet many students would appreciate some comments
or links to resources about the overall algorithm and concepts
like "branch-and-bound" and "lookahead" ...

(4) keep the cyclomatic complexity in the scoring

Including the "cyclomatic complexity" added an interesting dimension
to the scoring.

(5) ignore whitespace in the 1K challenge, or reformat 1K submissions

It would be nice if there was a way to avoid the obfuscation
that seems to come with the 1K challenge.
One possibility would be an automatic pre-processor
strips out whitespace, comments, and long variable names.
Another possibility would be to keep the current submission style
but automatically display the submitted code
in a standardized format with added whitespace.
Are there existing reformatting tools that could be used?


- - - - -


And now some personal comments on the contest, ...

Despite the fact that I didn't win any of the prizes in this contest,
it was still one of the most enjoyable for me.
The "Peg Jumping" puzzle was a great choice.
I realize the organizers put a lot of careful thought into
preparing for the contest and I hope the next puzzle will be
a similar combination of "easy to understand, but difficult to
solve".

The overall contest organization is brilliant, since there are
many opportunities for lots of different participants (25+)
to be "in the lead" in one category or another at various stages
of the competition.

Coming in a respectable 6th and 11th in Darkness and Twilight
I felt I had a good understanding of this particular contest problem
(though clearly others had a more insightful understanding!).
I anxiously sat in 1st place for the 1K challenge
until "SY" skillfully took my place with 2 minutes before the 9pm
deadline.

If there was a "Tweaker" prize for the most incremental improvements
over the course of the contest, I would have won it
with a total of 78.2770 on the "Statistics" page.
(hint, hint, to the contest organizers ... I would love a Matlab
T-shirt :-)

(By the way, I wonder if "tgs" should also get a prize, or at least
honorable mention for the "Best Result" (38544.27), although
it occurred after the 4pm deadline.)

Even though it's clear I'm a hard core tweaker, and I know some
people
must find this infuriating, I do favour the addition of a "captcha"
on the entry submission page to limit (but not eliminate)
the flow of tweaks into the queue. Fortunately, the queue never
really
got out of hand for this contest.

I think I also take some of the blame for launching us all
into the realm of randomization. In past contests there has often
been someone who had an algorithmic insight that finally cut through
all the randomization nonsense and brought us back into a more
predictable deterministic algorithm. I was fully expecting
this to happen again, but it never did. In fact, others
pushed randomization in new directions. Perhaps we should challenge
the organizers to dream up a future contest puzzle that does not
lend itself to a randomized solution.

As many participants must have realized from the names on my
submissions,
I was in the Sarasota Airport using their free wireless access
during the final day of the contest. I was later amused to see
that my submission "Boarding Flight 905" had briefly taked the lead
at 10:43am. I had to board my plane and I was in the air during the
final hour of the contest, but it wouldn't have mattered anyay,
since Yi Cao's submission took the victory so decisively.

I only mention being in the airport since I noticed
that "srach" titled one of his submissions:
"I'm leaving for my son's birthday party - good luck to all of you!"

Congratulations once again to all the contest organizers and winners.

Warmest Regards,
  David Jones

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: David Jones

Date: 17 May, 2007 21:47:30

Message: 125 of 221

I wonder if the Contest organizers might be willing to release the
actual test suite used in the contest so people who are curious to
continue analyzing the problem would be able to benchmark their new
programs in comparison with the program(s) that won in various
categories.

-- David Jones

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: Hannes Naudé

Date: 18 May, 2007 01:36:35

Message: 126 of 221

Nathan wrote:
>
>
> Hi Hannes
>
>> Some other circumstantial evidence for the theory that fewer
and
>> fewer people are focussing on algorithms is the fact that the
>> leading solvers were optimising an objective function that was
> WRONG
>> and can be shown to be wrong with a fairly elementary argument.
>
> Are you referring to the objective function C0+CV*d? Score of first
> move + weight*(score of second move), as I understand it. It seems
> weird that this works with weight values far from 1, but the
> fundamental flaw with the function itself is not obvious to me.
> Could
> you elaborate on your comment?
>
> thanks
>
> Nathan
  
Sure

Like I am sure most people do, I kept the information overload
manageable by scanning the leading entry from time to time to
maintain an overview, but only really focussing on and staying up to
date with one particular solver. In my case that was solveri the
deterministic recursive solver, so I dont know too much about what
weights were used for C0+CV*d. The recursive solver searched for the
chain had the highest score of the function F=(total weight
removed)-(lifting penalty). This seems to be the obvious choice, but
it is wrong, because it neglects the fact that you can have as many
moves as you want.

If you think about it, the final result will be made up of two
components:
Total weight left on the board + Total lifting penalties paid during
run.
The critical insight is to realise that none of our current solvers
could actually significantly affect the value of the first term. Even
the recursive solver that finds tremendously high scoring hopchains
is just as likely to get stuck relatively early in the endgame as a
simple greedy approach. This is not obvious, but it is true right up
to two moves from the end where the recursive can sometimes under
special circumstances see that one high scoring move will result in a
dead end whereas another possibly lower scoring move will set up
another chain to follow.

So, the way in which our objective function was derived, is to assume
at the outset that the amount of weight that will be removed from a
given board IN TOTAL is essentially fixed (it is not, but it is
outside the control of a reasonable objective function). Therefore we
should focus on minimizing the lifting penalty. This leads naturally
to the objective function F=(weight removed in this move)/(lifting
penalty for this move). switching to this metric has a dramatic
impact. This is the ratio metric that was introduced in our "All
frayed out" series (which were crippled so as not to attract undue
attention). Unfortunately for us Yi picked up on this and utilised it
to power him to an impressive win.

Not sure if that explanation was clear so will conclude with an
example. Lets assume we have two moves to choose between:
Move 1 : Removes 10 weights for a lifting penalty of 5.
Move 2 : Removes 5 weights for a lifting penalty of 1.
Move 1 results in a larger net gain in score (5 points) and so will
be chosen by the greedy objective function. Move 2 removes less but
does so more efficiently and will be chosen by the ratio metric. So
if we removed a total of 100 units of weight from a board, using
moves like move 1, we would end up paying a 50 unit lifting penalty.
If we removed the same amount using moves like move 2, we would only
pay a 20 unit lifting penalty.

This should obviously affect subsol and subsoltweak as well but the
implementation is not obvious (because the amount of weight that will
be lifted by a given hopchain is not known at decision time). A
simple start would be to weigh the lifting penalty heavier. We didn't
have time to investigate this.

Sorry to everyone that understood immediately and have had the pants
bored off them by the long dissection, but more often than not I
don't understand explanations offered here by others, so I try to be
as clear as possible.

If anyone feels this is wrong, I'd really like to hear why.

Cheer

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: Yi Cao

Date: 18 May, 2007 05:07:36

Message: 127 of 221

David Jones wrote:
>
> I have equal respect for a Tuesday Leap winner
> who dreams up a new algorithm that suddenly takes the lead
> by a wide margin and another contest winner who recognizes
> a major speedup of the same algorithm that further advances
> the lead by a wide margin. Which is more insightful?
> the algorithm change or the program tweak? I'd say, ...
> the one that makes the larger leap.
>
It was me dreamed the new algorithm, (see CollobrationSolver). But
unfortunately, it did not get to the top due to new tweak parameter
was found just before the new algorithm was submitted. Fortunately,
the algorithm was quickly picked up by Jin then the Leap winner SY to
win the Leap price. I respect both of them. Without their tweaking,
this algorithm would be buried by random tweakers like many other
algorithms developed dring the week. But my point is that this is by
lucky. Many novel ideas might have been killed because the style of
contest during daylight phase does not encourage those ideas to be
developed further. I do respect all tweakers' contributions. But we
need to give some rooms for novel ideas to be developed. For example,
the owner of a code would get the result through email one hour
earlier than it shows on the queue. This may also avoid submissions
with fake addresses.

By the way, tgs is my alias. I used it to test a bug-fix in subsol.

Finally, I wish to thank you for your magic number rand(57,1) which
helped me win the contest.

Yi

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: Yi Cao

Date: 18 May, 2007 06:47:42

Message: 128 of 221

Hannes Naudé wrote:
>
>
> Nathan wrote:
>>
>>
>> Hi Hannes
>>
>>> Some other circumstantial evidence for the theory that
fewer
> and
>>> fewer people are focussing on algorithms is the fact that
the
>>> leading solvers were optimising an objective function that
> was
>> WRONG
>>> and can be shown to be wrong with a fairly elementary
> argument.
>>
>> Are you referring to the objective function C0+CV*d? Score of
> first
>> move + weight*(score of second move), as I understand it. It
> seems
>> weird that this works with weight values far from 1, but the
>> fundamental flaw with the function itself is not obvious to me.
>> Could
>> you elaborate on your comment?
>>
>> thanks
>>
>> Nathan
>
> Sure
>
> Like I am sure most people do, I kept the information overload
> manageable by scanning the leading entry from time to time to
> maintain an overview, but only really focussing on and staying up
> to
> date with one particular solver. In my case that was solveri the
> deterministic recursive solver, so I dont know too much about what
> weights were used for C0+CV*d. The recursive solver searched for
> the
> chain had the highest score of the function F=(total weight
> removed)-(lifting penalty). This seems to be the obvious choice,
> but
> it is wrong, because it neglects the fact that you can have as many
> moves as you want.
>
> If you think about it, the final result will be made up of two
> components:
> Total weight left on the board + Total lifting penalties paid
> during
> run.
> The critical insight is to realise that none of our current solvers
> could actually significantly affect the value of the first term.
> Even
> the recursive solver that finds tremendously high scoring hopchains
> is just as likely to get stuck relatively early in the endgame as a
> simple greedy approach. This is not obvious, but it is true right
> up
> to two moves from the end where the recursive can sometimes under
> special circumstances see that one high scoring move will result in
> a
> dead end whereas another possibly lower scoring move will set up
> another chain to follow.
>
> So, the way in which our objective function was derived, is to
> assume
> at the outset that the amount of weight that will be removed from a
> given board IN TOTAL is essentially fixed (it is not, but it is
> outside the control of a reasonable objective function). Therefore
> we
> should focus on minimizing the lifting penalty. This leads
> naturally
> to the objective function F=(weight removed in this move)/(lifting
> penalty for this move). switching to this metric has a dramatic
> impact. This is the ratio metric that was introduced in our "All
> frayed out" series (which were crippled so as not to attract undue
> attention). Unfortunately for us Yi picked up on this and utilised
> it
> to power him to an impressive win.
>
> Not sure if that explanation was clear so will conclude with an
> example. Lets assume we have two moves to choose between:
> Move 1 : Removes 10 weights for a lifting penalty of 5.
> Move 2 : Removes 5 weights for a lifting penalty of 1.
> Move 1 results in a larger net gain in score (5 points) and so will
> be chosen by the greedy objective function. Move 2 removes less but
> does so more efficiently and will be chosen by the ratio metric. So
> if we removed a total of 100 units of weight from a board, using
> moves like move 1, we would end up paying a 50 unit lifting
> penalty.
> If we removed the same amount using moves like move 2, we would
> only
> pay a 20 unit lifting penalty.
>
> This should obviously affect subsol and subsoltweak as well but the
> implementation is not obvious (because the amount of weight that
> will
> be lifted by a given hopchain is not known at decision time). A
> simple start would be to weigh the lifting penalty heavier. We
> didn't
> have time to investigate this.
>
> Sorry to everyone that understood immediately and have had the
> pants
> bored off them by the long dissection, but more often than not I
> don't understand explanations offered here by others, so I try to
> be
> as clear as possible.
>
> If anyone feels this is wrong, I'd really like to hear why.
>
> Cheer

This is innovative thinking. I wish I could get this idea earlier. I
tested this idea with subsol and want to confirm it also works with
subsol. What I did is introducing another score vector C1 =
C0-0.5board(F(h)); to be used for optimization (only for the
isempty(c) case), but keep C0 to record actual score of the move. It
reduces overall results from 42725.167 to 42451.5929 for the testsuit
(based on my "Buy a ticket" code). Tweaking the weight can reduce the
results even further.

Yi

Yi

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: srach

Date: 18 May, 2007 07:20:15

Message: 129 of 221

David Jones wrote:
[...]
> I only mention being in the airport since I noticed
> that "srach" titled one of his submissions:
> "I'm leaving for my son's birthday party - good luck to all of
> you!"

Yes, this was actually my last submission for this Spring contest,
because I spend the last 5 hours of the contest with a bunch of
five-year-olds.

One thing I would like to add to the "timezone vs. deadline"
discussion. Yes, living in a different timezone collides with some
deadlines, but, compared to previous contests, this has improved a
lot. (However, I still had to get up at 2 a.m. (local time) for the
1000-character contest. ;) ). However, although being one of the top
submitters (or SPAMers, if you prefer...), I never had to wait more
than 2 minutes for my entries to be processed (only exeption was, of
course, the "best result by 4pm contest"), because the contest
machine was nearly idle during my working hours (8pm to 4pm local
time, which is EDT+6). Thus, I felt free to optimize some parameters
online, because offline parameter optimization was rather useless.

Best,
srach

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: Hannes Naudé

Date: 18 May, 2007 07:57:08

Message: 130 of 221

srach wrote:
> "timezone vs. deadline" discussion.

Yes, this has turned into a bit of a timezone vs. Deadline
discussion. To be honest, I feel that the times for the latest
contest has suited me better as well (alltough Cobus feels it is
worse, so its a matter of taste I suppose). However, that was hardly
the main driver for requesting a scheduling feature, if we need to
stay up until 3AM we will. The main thing is that we find it very
hard to submit our submissions at the exact right time due to
significant latency between ourselves and the contest machine. The
submission confirmation takes ~15s to come up and the queue and top
20 has taken as long as a minute.

The net result is that we either submit too early and get tweaked out
of top spot (this happened to us in blockbuster) or too late and miss
the deadline (this happened to Cobus in blackbox). Maybe it is like
this for everyone, but looking at how prolific cyc is during the last
few minutes I seriously doubt it. In addition our power and internet
connections are not as reliable as they should be (this is Africa
afterall ;-) ). In the ants contest our power went down 30 minutes
before the end and we had to get in a car and race to work where we
have UPS. Our submissions were ready well before this, so scheduling
would have helped a lot.

Of course the one day twilight concept achieves the same thing, as
does the suggestion of "final" tagged submissions. In effect we
currently have 1 minute darkness at the end of the contest (entries
that are submitted after 11:59 won't be seen before the deadline has
passed) so we are not really asking for a rule change, just for an
extension of the existing 1 minute darkness to accomodate those with
iffy connectivity, even 5 minutes would be great, allthough 1 day
would be way better.

I would really like to know what the contest team thinks of this
proposal, and would like to make clear my willingness to implement
it, if that would be required. Of course integration and testing on
your side will still require some of your time, but do you at least
agree with the idea in principle?

Regards
Hannes

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: Nathan

Date: 18 May, 2007 09:02:07

Message: 131 of 221

Hannes

thanks for the explanation. Simple in hindsight, like most good
ideas.

I've tried your ratio metric in subsol, crudely (based only on the
known first two hops of a chain). It does not improve "buy a ticket"
(too finely tuned for the difference metric?) but in a mid-contest
code, it makes a significant improvement.

Nathan

Hannes Naudé wrote:

> So, the way in which our objective function was derived, is to
> assume
> at the outset that the amount of weight that will be removed from a
> given board IN TOTAL is essentially fixed (it is not, but it is
> outside the control of a reasonable objective function). Therefore
> we
> should focus on minimizing the lifting penalty. This leads
> naturally
> to the objective function F=(weight removed in this move)/(lifting
> penalty for this move). switching to this metric has a dramatic
> impact. This is the ratio metric that was introduced in our "All
> frayed out" series (which were crippled so as not to attract undue
> attention). Unfortunately for us Yi picked up on this and utilised
> it
> to power him to an impressive win.

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: Yi Cao

Date: 18 May, 2007 10:59:01

Message: 132 of 221

Nathan wrote:
>
>
> Hannes
>
> thanks for the explanation. Simple in hindsight, like most good
> ideas.
>
> I've tried your ratio metric in subsol, crudely (based only on the
> known first two hops of a chain). It does not improve "buy a
> ticket"
> (too finely tuned for the difference metric?) but in a mid-contest
> code, it makes a significant improvement.
>
> Nathan
>
> Hannes Naudé wrote:
>
>> So, the way in which our objective function was derived, is to
>> assume
>> at the outset that the amount of weight that will be removed
from
> a
>> given board IN TOTAL is essentially fixed (it is not, but it is
>> outside the control of a reasonable objective function).
> Therefore
>> we
>> should focus on minimizing the lifting penalty. This leads
>> naturally
>> to the objective function F=(weight removed in this
> move)/(lifting
>> penalty for this move). switching to this metric has a dramatic
>> impact. This is the ratio metric that was introduced in our
"All
>> frayed out" series (which were crippled so as not to attract
> undue
>> attention). Unfortunately for us Yi picked up on this and
> utilised
>> it
>> to power him to an impressive win.

But my test shows that the ratio index works very well with subsol
based on "Buy a ticket" code. What I did is to replat C0+CV*d to
(C0+Cv*d)./board(F(h)). It reduces overall results from 42725.1617 to
41913.0357. Yes, more than 800 scores!

Yi

But it does not work with subsoltweak.

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: Nick Howe

Date: 18 May, 2007 11:20:16

Message: 133 of 221

David Jones wrote:
> Perhaps Darkness or Twilight winners deserve greater respect
> for their own algorithmic insights, ... but through the rest
> of the contest the actual algorithmic insights that arise
> are remarkably few and far between. We rarely see wholesale
> shifts from one high-level algorithm to another.
> Instead, we see incremental changes at various levels.
> Yes, realizing an advantage by "padding" the board
> is more "algorithmic" than realizing that "nnz(B(:)>0)"
> is faster than "sum(B(:)>0)", but in the end they are
> both incremental and the main algorithm remains the same.
>
> In previous contests, winners have *sometimes* been rewarded
> for ignoring the ongoing tweakfest and focusing on their
> own independent algorithm development ... which then needs
> to be kept secret and submitted at the last strategic moment.

> In addition to his line-by-line comments, I think it would be
> particularly educational for participants who have less expertise
> if there was also more of a high-level roadmap of the leading
entry.
> To many programmers, I think the comments still remain rather
> cryptic
> because they don't know how each step fits into the big picture.

> Perhaps Lucio Cetto could take on the role of high-level algorithm
> description.

I think David has some nice points here. I would certainly welcome a
high-level overview of the code, as it would make it easier to
spectate, and (who knows?) maybe jump in again if I had a bright
idea.

In some sense the collaborative code development that emerges is a
greedy process: we follow and develop the code that is in the lead
at the end of twilight, and this leads us down one particular path.
It is fully possible that an algorithm designed some other way would
develop more successfully in the end. For example, someone may have
a great algorithmic idea that runs too slowly, but others might be
able to speed it up significantly to the point where it would
overtake the leader. It is very hard (not to mention daunting) for
one person to compete with the collective efforts of the group. The
early bird contest does encourage exploration of alternate paths a
little bit, but not in a very comprehensive way. Most algorithms
developed in Darkness and Twilight never get another look.

I don't have a real solution here, but it would be great if we could
somehow encourage parallel development on a number of different
approaches. Speaking selfishly, I would love to see what people
could have done with the approach I started with in Darkness. And in
the end, we might reach a more satisfying conclusion if we explore
more paths in the beginning.

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: Nick Howe

Date: 18 May, 2007 11:28:28

Message: 134 of 221

To follow up a bit on my last post, it would be nice if we could
somehow separate categories by their high-level approach -- "Best
Recursive Solver," "Best Heuristic Solver," "best Combined Solver,"
etc., to encourage development on each separate front. Of course, I
don't really know how you would define the categories or implement
this in the contest framework. But it would be nice.

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: Yi Cao

Date: 18 May, 2007 11:40:31

Message: 135 of 221

Nick Howe wrote:
>
>
> To follow up a bit on my last post, it would be nice if we could
> somehow separate categories by their high-level approach -- "Best
> Recursive Solver," "Best Heuristic Solver," "best Combined Solver,"
> etc., to encourage development on each separate front. Of course,
> I
> don't really know how you would define the categories or implement
> this in the contest framework. But it would be nice.

How about a parallel twilight queue, where we can see the result but
cannot read the code. Of cause, entries of this queue will not claim
any prize. It just provides a platform for code developers to develop
their own ideas.

Yi

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: Steve Hoelzer

Date: 18 May, 2007 11:44:16

Message: 136 of 221

Nick Howe wrote:
> It is fully possible that an algorithm designed some other way
> would
> develop more successfully in the end. For example, someone may
> have
> a great algorithmic idea that runs too slowly, but others might be
> able to speed it up significantly to the point where it would
> overtake the leader. It is very hard (not to mention daunting) for
> one person to compete with the collective efforts of the group.
> The
> early bird contest does encourage exploration of alternate paths a
> little bit, but not in a very comprehensive way. Most algorithms
> developed in Darkness and Twilight never get another look.

I agree. Maybe one way to draw attention to a variety of algorithms
is to display a second set of "top 20" entries for darkness and
twilight with ranking based purely on score (ignore time). The best
scoring entries may have better algorithms and some speed
optimization could lead to a better solution in the end.

Steve

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: Nick Howe

Date: 18 May, 2007 13:02:15

Message: 137 of 221

Helen Chen wrote:
>
>
> Hello Community!
>
> This is just a quick message to let everyone know that the MATLAB
> Contest Masters have been hard at work! They have been crafting a
> really exciting new challenge for our Spring event with some very
> cool prizes waiting for our champions.
>
> It's time to clear your calendars so that you can come join the
> fun!
> The contest will start at noon Eastern time on May 9, ending at
> noon
> on Mary 16th.
>
> We will be announcing more details about the contest as we get
> closer, so if you want a refresher about MATLAB Central contests,
> check out the contest overview page at <http://www.mathworks.com/contest/overview.html>.
> ou can checkout past contests using links on that page.
>
> Stay tuned for more information...
>
> Best wishes,
> Helen Chen
> MATLAB Central Team

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: Nick Howe

Date: 18 May, 2007 13:03:15

Message: 138 of 221

Steve Hoelzer wrote:
>
> I agree. Maybe one way to draw attention to a variety of algorithms
> is to display a second set of "top 20" entries for darkness and
> twilight with ranking based purely on score (ignore time). The best
> scoring entries may have better algorithms and some speed
> optimization could lead to a better solution in the end.
>
> Steve

There's already a notion of 'code clans' in the statistics Maybe a
start would be to group all entries connected by syntactic
similarities, and somewhere have a listing of the top entry for each
of the top 5-10 clans.

Subject: highlighting other algorithms

From: Matthew Simoneau

Date: 18 May, 2007 15:39:02

Message: 139 of 221

I updated the File Exchange submission to include the actual test
suite we used to score the entries.

The quality of commentary on this thread is blowing us away. It's
great to see the participants sharing stories, crediting sources, and
discussing algorithms. The level of gamesmanship from the top
players is impressive. We're also paying close attention to your
suggestions for improving the contest. I'm particularly interested
in finding ways to encourage innovation from participants and ways to
make the action easier to follow for spectators. Thanks for the
thoughtful suggestions on these and many other topics.

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: srach

Date: 19 May, 2007 07:12:43

Message: 140 of 221

Hannes Naudé wrote:
[...]
> Not sure if that explanation was clear so will conclude with an
> example. Lets assume we have two moves to choose between:
> Move 1 : Removes 10 weights for a lifting penalty of 5.
> Move 2 : Removes 5 weights for a lifting penalty of 1.
> Move 1 results in a larger net gain in score (5 points) and so will
> be chosen by the greedy objective function. Move 2 removes less but
> does so more efficiently and will be chosen by the ratio metric. So
> if we removed a total of 100 units of weight from a board, using
> moves like move 1, we would end up paying a 50 unit lifting
> penalty.
> If we removed the same amount using moves like move 2, we would
> only
> pay a 20 unit lifting penalty.

How does this approach pay respect the fact, that the second kind of
moves needs a higher number of moves to reach the same amount of
weight removed from the board? Since the number of moves is limited,
I would think that the number of moves a strategy needs to reach a
certain amount of weight needs to be considered in the objective
function, too.

Best,
srach

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: Yi Cao

Date: 19 May, 2007 08:12:51

Message: 141 of 221

srach wrote:
>
>
> Hannes Naudé wrote:
> [...]
>> Not sure if that explanation was clear so will conclude with an
>> example. Lets assume we have two moves to choose between:
>> Move 1 : Removes 10 weights for a lifting penalty of 5.
>> Move 2 : Removes 5 weights for a lifting penalty of 1.
>> Move 1 results in a larger net gain in score (5 points) and so
> will
>> be chosen by the greedy objective function. Move 2 removes less
> but
>> does so more efficiently and will be chosen by the ratio
metric.
> So
>> if we removed a total of 100 units of weight from a board,
using
>> moves like move 1, we would end up paying a 50 unit lifting
>> penalty.
>> If we removed the same amount using moves like move 2, we would
>> only
>> pay a 20 unit lifting penalty.
>
> How does this approach pay respect the fact, that the second kind
> of
> moves needs a higher number of moves to reach the same amount of
> weight removed from the board? Since the number of moves is
> limited,
> I would think that the number of moves a strategy needs to reach a
> certain amount of weight needs to be considered in the objective
> function, too.
>
> Best,
> srach

We may also consider potential moves desdroyed and creadted by a
move. We have found a vector of indices of triples (F M T) which
will be affected by conducting a move. Use this vector we can evalue
potential score increment and add this increment to the optimization
criterion. But time may increase significantly.

Yi

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: Hannes Naudé

Date: 19 May, 2007 08:23:21

Message: 142 of 221

srach wrote:
>
>
> Hannes Naudé wrote:
> [...]
>> Not sure if that explanation was clear so will conclude with an
>> example. Lets assume we have two moves to choose between:
>> Move 1 : Removes 10 weights for a lifting penalty of 5.
>> Move 2 : Removes 5 weights for a lifting penalty of 1.
>> Move 1 results in a larger net gain in score (5 points) and so
> will
>> be chosen by the greedy objective function. Move 2 removes less
> but
>> does so more efficiently and will be chosen by the ratio
metric.
> So
>> if we removed a total of 100 units of weight from a board,
using
>> moves like move 1, we would end up paying a 50 unit lifting
>> penalty.
>> If we removed the same amount using moves like move 2, we would
>> only
>> pay a 20 unit lifting penalty.
>
> How does this approach pay respect the fact, that the second kind
> of
> moves needs a higher number of moves to reach the same amount of
> weight removed from the board? Since the number of moves is
> limited,
> I would think that the number of moves a strategy needs to reach a
> certain amount of weight needs to be considered in the objective
> function, too.
>
> Best,
> srach

But the number of moves is NOT limited as such and this is why the
first metric is wrong. The only sense in which the number of moves
are limited is that at some point you will reach a board
configuration that does not allow any further legal moves and you
will be stuck. But there is no reason to believe that the second
approach will get stuck any earlier (on average) than the first. How
early you get stuck is largely determined by the number of moves your
solver can lookahead.

On a slightly different topic, I have not had a chance to investigate
this, but I am reasonably certain that you will find that running the
improved subsol metric against the actual contest suite will NOT
result in an improvement. This is because any modification to the
non-deterministic solver will cause you to drop out of the local
minimum into which the leading code has been tweaked, and chances are
very high that the increased performance of the algorithm will be
outweighed by the absence of a "magic number". Many algorithmic
improvements and bugfixes have bitten the dust in this manner. This
is why we focussed our efforts on the deterministic part of the code.

Maybe Yi can test this conjecture and let us know?

Regards
Hannes

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: Yi Cao

Date: 19 May, 2007 08:49:05

Message: 143 of 221

Hannes Naudé wrote:
>
> On a slightly different topic, I have not had a chance to
> investigate
> this, but I am reasonably certain that you will find that running
> the
> improved subsol metric against the actual contest suite will NOT
> result in an improvement. This is because any modification to the
> non-deterministic solver will cause you to drop out of the local
> minimum into which the leading code has been tweaked, and chances
> are
> very high that the increased performance of the algorithm will be
> outweighed by the absence of a "magic number". Many algorithmic
> improvements and bugfixes have bitten the dust in this manner. This
> is why we focussed our efforts on the deterministic part of the
> code.
>
> Maybe Yi can test this conjecture and let us know?
>
I have tested this improvement with actual suit. You are partially
right, the improvement is not as large as that achhieved on the
sample suit. But still there is a significant improvement: for "but a
ticket" code, the overal results reduced from 39072.4778 to
38866.2520, more than 200 points.

Yi

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: Sergey Yurgenson

Date: 19 May, 2007 10:43:50

Message: 144 of 221

I agree with srach, the number of moves is limited (It is limited by
number of pegs).
My explanation of new metric is simpler:
New metric gives preferences to moves when medium weighted pegs are
tacking out by light pegs (medium-light) comparing to old metric
heavier pegs being tacking out by medium pegs (moves heavy-light will
be selected up by both metrics). As a result at the end of game we
will have more moves heavy-light.
In other words, light pegs first remove competing medium pegs and
then heavy pegs making lifting penalty smaller.
Actually, slightly weaker metric is better.
I played with “buy two tickets”:
Competition result 38976.72
Result with (C0+CV*d)./board(F(h)) 38792.95
Result with (C0+CV*d)./(board(F(h)).^0.6) 38580.22
Result with (C0+CV*d)./(board(F(h))+1) 38536.85

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: Yi Cao

Date: 19 May, 2007 13:01:34

Message: 145 of 221

Sergey Yurgenson wrote:
>
>
> I agree with srach, the number of moves is limited (It is limited
> by
> number of pegs).
> My explanation of new metric is simpler:
> New metric gives preferences to moves when medium weighted pegs are
> tacking out by light pegs (medium-light) comparing to old metric
> heavier pegs being tacking out by medium pegs (moves heavy-light
> will
> be selected up by both metrics). As a result at the end of game we
> will have more moves heavy-light.
> In other words, light pegs first remove competing medium pegs and
> then heavy pegs making lifting penalty smaller.
> Actually, slightly weaker metric is better.
> I played with “buy two tickets”:
> Competition result 38976.72
> Result with (C0+CV*d)./board(F(h)) 38792.95
> Result with (C0+CV*d)./(board(F(h)).^0.6) 38580.22
> Result with (C0+CV*d)./(board(F(h))+1) 38536.85

Interesting. The weaker metric is also better for solveri. For "Buy a
ticket" I got the following results:
Original result: 39072.4778
with (C0+CV*d)./board(F(h)) 38866.2520
with (C0+CV*d)./(board(F(h))+1) 38567.5729
plus solveri metric hop_value/(liftPenalty+0.4)+1 38322.2292

It is an amazing improvement without increase computing time!

Yi

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: Sergey Yurgenson

Date: 19 May, 2007 14:51:35

Message: 146 of 221

Yi Cao wrote:
> Interesting. The weaker metric is also better for solveri. For "Buy
> a
> ticket" I got the following results:
> Original result: 39072.4778
> with (C0+CV*d)./board(F(h)) 38866.2520
> with (C0+CV*d)./(board(F(h))+1) 38567.5729
> plus solveri metric hop_value/(liftPenalty+0.4)+1 38322.2292
>
> It is an amazing improvement without increase computing time!
>
> Yi
  
I agree. We already lower than 3min competition (“Best Result”).
Unfortunately current contest format does not encourage open exchange
of ideas during competition.

Sergey (SY)

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: srach

Date: 19 May, 2007 15:09:54

Message: 147 of 221

Hannes Naudé wrote:
[...]
> But the number of moves is NOT limited as such and this is why the
> first metric is wrong. The only sense in which the number of moves
> are limited is that at some point you will reach a board
> configuration that does not allow any further legal moves and you
> will be stuck. But there is no reason to believe that the second
> approach will get stuck any earlier (on average) than the first.
> How
> early you get stuck is largely determined by the number of moves
> your
> solver can lookahead.

Like SY already mentioned, I would think that the number of moves is
indeed limited by the number of pegs on the board. Anyway, my comment
was not in favor for the first metric or against the second one
proposed by you. I was just curious.

Best,
srach

Subject: Weighted English Board

From: Yi Cao

Date: 20 May, 2007 04:55:51

Message: 148 of 221

Nick Howe wrote:
>
>
> Incidentally, here is a solution to the Weighted English Board with
> a
> score of 359. It is not as satisfying since it leaves 4 pegs
> behind,
> but the score is lower.
>
> 4 2 4 4
> 6 3 4 3
> 5 5 5 3
> 7 5 5 5
> 4 4 4 2
> 2 3 4 3
> 4 3 6 3
> 6 3 6 5
> 3 5 3 3
> 3 7 3 5
> 5 7 3 7
> 5 5 5 7
> 3 2 3 4
> 3 4 3 6
> 3 6 5 6
> 7 3 7 5
> 7 5 5 5
> 5 5 3 5
> 1 4 3 4
> 3 4 3 6
> 4 1 4 3
> 1 5 3 5
> 5 1 5 3
> 5 3 3 3
> 3 6 3 4
> 3 4 3 2
> 5 7 5 5

Well done! I would say this is a near optimal solution. It does not
matter it leaves 4 pegs because the final score will be sum of pegs
left + sum of lifting pegs. Hence, it is equivalent: a peg is used
for lifting then removed later or the same peg is left in the board
without touch. A trick of this solution which makes the score is so
low is that it repeatly uses pegs with scores 1 and 2 as lifting
pegs. In Lucio's solution, each lifting peg has been used only once.
This is an example which supports the principle of the ratio metric.

Yi

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: Hannes Naudé

Date: 20 May, 2007 14:52:13

Message: 149 of 221

srach wrote:
 Anyway, my
> comment
> was not in favor for the first metric or against the second one
> proposed by you. I was just curious.
>
> Best,
> srach

No worries mate. I understood your comment the way it was intended.
Besides, criticism of the approach is exactly what I was after. By no
means do I believe that the ratio metric is the final solution. This
process of feeding off of each other's ideas is what I enjoy most
about these contests.

I still do not quite understand the "we are limited by the number of
pegs on the board" argument. (An example of what I mentioned earlier:
I tend not to follow many discussions on here, I'm a bit slow that
way ;-)) Will sleep on it and get back to you.

Cheers
H

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: srach

Date: 20 May, 2007 15:27:40

Message: 150 of 221

Hannes Naudé wrote:
[...]
> I still do not quite understand the "we are limited by the number
> of
> pegs on the board" argument.

For each move you complete, you have to remove one peg (the one you
jumped across). Thus, if you have N pegs on your board, you can
perform a maximum of N-1 jumps before you run out off pegs to jump
across. The N-th peg will always stay on the board.

Best,
srach

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: Yi Cao

Date: 20 May, 2007 15:28:33

Message: 151 of 221

Hannes Naudé wrote:
>
>
> srach wrote:
> Anyway, my
>> comment
>> was not in favor for the first metric or against the second one
>> proposed by you. I was just curious.
>>
>> Best,
>> srach
>
> No worries mate. I understood your comment the way it was intended.
> Besides, criticism of the approach is exactly what I was after. By
> no
> means do I believe that the ratio metric is the final solution.
> This
> process of feeding off of each other's ideas is what I enjoy most
> about these contests.
>
> I still do not quite understand the "we are limited by the number
> of
> pegs on the board" argument. (An example of what I mentioned
> earlier:
> I tend not to follow many discussions on here, I'm a bit slow that
> way ;-)) Will sleep on it and get back to you.
>
> Cheers
> H

In terms of the limitation of number of moves, I think both of you
are right, just different view point. Natually, the number of moves
of a game has a top limit, which is the number of pegs -1. However,
this actually is not a real limitation to an algorithm because
because one never requires more than this number of moves.

In terms of ratio metric, my explanation is that it actually a way
to trade off a multi-objective optimization problem. If we can
perform a brute force search, the metric is uniquely determined.
However, we can only have limited numbers of searchs locally in a
stage. That means the local optimal solution may not lead to the
global optimal. Therefore, we have many different way to "guess" what
metric would lead to the global optimal. Here, we end up with two
ideas, maximum I1=board(M0)-board(F0) or I2=minimize board(F). The
ratio metric I1/(I2+alpha) is a way to trade off these two goals.
Another way is I1 + alpha*I2.

Yi

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: Nick Howe

Date: 20 May, 2007 15:44:46

Message: 152 of 221

Yi Cao wrote:
> In terms of ratio metric, my explanation is that it actually a way
> to trade off a multi-objective optimization problem. If we can
> perform a brute force search, the metric is uniquely determined.
> However, we can only have limited numbers of searchs locally in a
> stage. That means the local optimal solution may not lead to the
> global optimal. Therefore, we have many different way to "guess"
> what
> metric would lead to the global optimal. Here, we end up with two
> ideas, maximum I1=board(M0)-board(F0) or I2=minimize board(F). The
> ratio metric I1/(I2+alpha) is a way to trade off these two goals.
> Another way is I1 + alpha*I2.
>
> Yi

I suspect that the ratio metric is best used towards the start of the
search, since it tries to set up high-scoring moves later in the
game. The original metric will probably be best towards the end,
since it prioritizes the actual measured score. Perhaps a smooth
tradeoff that shifts the parameters from one to the other would work
best.

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: Yi Cao

Date: 20 May, 2007 17:01:32

Message: 153 of 221

Nick Howe wrote:
>
> I suspect that the ratio metric is best used towards the start of
> the
> search, since it tries to set up high-scoring moves later in the
> game. The original metric will probably be best towards the end,
> since it prioritizes the actual measured score. Perhaps a smooth
> tradeoff that shifts the parameters from one to the other would
> work
> best.

I have the similar feeling and tried to include the current step
index t into the metric, for example,
(C0+CV*d)./(board(F(h))+alpha*log(t)) and
(C0+CV*d)./(board(F(h))).^((pegCound-t)/pegCound) but none was
successful.

Yi

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: Sergey Yurgenson

Date: 20 May, 2007 17:27:55

Message: 154 of 221

Yi Cao wrote:
>
>
> Nick Howe wrote:
>>
>> I suspect that the ratio metric is best used towards the start
of
>> the
>> search, since it tries to set up high-scoring moves later in
the
>> game. The original metric will probably be best towards the
end,
>> since it prioritizes the actual measured score. Perhaps a
smooth
>> tradeoff that shifts the parameters from one to the other would
>> work
>> best.
>
> I have the similar feeling and tried to include the current step
> index t into the metric, for example,
> (C0+CV*d)./(board(F(h))+alpha*log(t)) and
> (C0+CV*d)./(board(F(h))).^((pegCound-t)/pegCound) but none was
> successful.
>
> Yi

I was trying to switch from one metric to another if number of pegs
on board is less than N, but without success too.

Another unsuccessful idea – “punish” for removing lightest pegs from
board (or maybe my implementation was incorrect). The idea was to
prevent removing light pegs during multijump sequences.

Just minor additional comment:
New metric has to be applied to “negative moves” in different way.
When I changed code accordingly:

If v<0 …… (C0+CV*d).*board(F(h))

final result went down by
additional 70 points (result of “buy two tickets” with all discussed
modifications
now is 38240.9693)

Sergey

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: Nathan

Date: 20 May, 2007 17:48:28

Message: 155 of 221

Another way of looking at it is this: early in the game, we can
afford to lift relatively heavy weights because there is a high
probability we'll have a chance to remove them later. As the board
clears, it is more important to avoid lifting heavy pegs.

This metric gives an improvement:

(C0+CV*d) ./ ( board(F(h)) + 0.2* avgPeg*(1-fracClear^2))

where avgPeg is the mean value of remaining pegs (to give a
meaningful scale to the added term) and fracClear is the fraction of
all positions that don't have pegs in them. This gives a result of
38498.9517 with Buy a ticket, compared with 38624.5902 for (C0+CV*d)
./ ( board(F(h))+1) ). There is a time penalty (about 5%) for keeping
these board statistics up to date.

Nathan

On May 20, 10:01 pm, "Yi Cao" <y...@cranfield.ac.uk> wrote:
> Nick Howe wrote:
>
> > I suspect that the ratio metric is best used towards the start
of
> > the
> > search, since it tries to set up high-scoring moves later in
the
> > game. The original metric will probably be best towards the
end,
> > since it prioritizes the actual measured score. Perhaps a
smooth
> > tradeoff that shifts the parameters from one to the other
would
> > work
> > best.
>
> I have the similar feeling and tried to include the current step
> index t into the metric, for example,
> (C0+CV*d)./(board(F(h))+alpha*log(t)) and
> (C0+CV*d)./(board(F(h))).^((pegCound-t)/pegCound) but none was
> successful.
>
> Yi

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: Hannes Naudé

Date: 21 May, 2007 02:30:38

Message: 156 of 221

srach wrote:
>
>
> Hannes Naudé wrote:
> [...]
>> I still do not quite understand the "we are limited by the
number
>> of
>> pegs on the board" argument.
>
> For each move you complete, you have to remove one peg (the one you
> jumped across). Thus, if you have N pegs on your board, you can
> perform a maximum of N-1 jumps before you run out off pegs to jump
> across. The N-th peg will always stay on the board.
>
> Best,
> srach

Yes, I understand THAT. What I don't get is how this is any more
applicable to the ratio than to the greedy metric. As mentioned
before, both approaches will kepp going until they are stuck. A what
point you get stuck is determined by the number of moves your solver
can look ahead, not by the objective function your solver uses to
make choices.

I think part of the confusion stems from inconsistent use of
terminology. From your explanation above it is clear that by "move"
you mean an atomic move (i.e. one single line in the moves matrix).
In my original example I used the term move where I actually meant a
sequence of moves using the same jumping peg (let's call it a
hopchain).

Making this distinction, you will see that while the ratio metric
will typically use more hopchains on a given board (since it selects
hopchains with lower net values), there is no reason to believe that
it will use more moves. In fact if we assume for simplicity's sake
that both approaches will get within N pegs of clearing an M peg
board, then by you own explanation both metrics will use exactly M-N
moves. So unless you argue that the ratio metric will get stuck
earlier, both metrics will use the same amount of moves.

As for switching metrics, Yes this is a thought that occurred to me
as well and I agree that the greedy metric should kick in towards the
endgame. I suspect a part of the reason why many of these attempts
have failed is that the transition should be highly non-linear, with
the ratio metric applying for 95% of the game and the greedy metric
only kicking in very suddenly at the death (that is, if there is a
significant probability that the next move may be the last, there is
a good motivation for using the greedy metric.

A related (and possibly much more effective) improvement would be to
suddenly increase the lookahead depth of the solver when only a few
pieces are left. Since few moves are available the impact of extra
lookahead is not as severe as it would normally be. Another
possiblity is using endgame libraries (like checkers and chess
programs do). However, I believe that the scores of the leading
solvers are dominated by the lifting penalty component, so any
reduction in weight left on the board will probably not have a
significant impact.

Regards

Hannes

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: srach

Date: 21 May, 2007 03:17:10

Message: 157 of 221

Hannes Naudé wrote:
[...]
> Yes, I understand THAT. What I don't get is how this is any more
> applicable to the ratio than to the greedy metric. As mentioned
> before, both approaches will kepp going until they are stuck. A
> what
> point you get stuck is determined by the number of moves your
> solver
> can look ahead, not by the objective function your solver uses to
> make choices.
>
> I think part of the confusion stems from inconsistent use of
> terminology. From your explanation above it is clear that by "move"
> you mean an atomic move (i.e. one single line in the moves matrix).
> In my original example I used the term move where I actually meant
> a
> sequence of moves using the same jumping peg (let's call it a
> hopchain).
>
> Making this distinction, you will see that while the ratio metric
> will typically use more hopchains on a given board (since it
> selects
> hopchains with lower net values), there is no reason to believe
> that
> it will use more moves. In fact if we assume for simplicity's sake
> that both approaches will get within N pegs of clearing an M peg
> board, then by you own explanation both metrics will use exactly
> M-N
> moves. So unless you argue that the ratio metric will get stuck
> earlier, both metrics will use the same amount of moves.
[...]
> Regards
>
> Hannes

Yes, you are right. I've read some of the earlier messages once again
and now I think I know where my confusion came from. In your example
(Message 138 in thread) you wrote:

> Not sure if that explanation was clear so will conclude with an
> example. Lets assume we have two moves to choose between:
> Move 1 : Removes 10 weights for a lifting penalty of 5.
> Move 2 : Removes 5 weights for a lifting penalty of 1.
> Move 1 results in a larger net gain in score (5 points) and so will
> be chosen by the greedy objective function. Move 2 removes less but
> does so more efficiently and will be chosen by the ratio metric. So
> if we removed a total of 100 units of weight from a board, using
> moves like move 1, we would end up paying a 50 unit lifting
> penalty.
> If we removed the same amount using moves like move 2, we would
> only
> pay a 20 unit lifting penalty.

Since the first kind of moves removesdd 10 pts per move and the
second kind only 5 pts per move, I concluded that, in order to remove
a total of 100 pts, the first kind needs 10 moves and the second
would need 20. Of course, this was complete nonsense in the context
of this problem. Thanks for your explanations and your patience! :-)

Best,
srach

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: Hannes Naudé

Date: 21 May, 2007 04:58:46

Message: 158 of 221

srach wrote:
> Since the first kind of moves removesdd 10 pts per move and the
> second kind only 5 pts per move, I concluded that, in order to
> remove
> a total of 100 pts, the first kind needs 10 moves and the second
> would need 20. Of course, this was complete nonsense in the context
> of this problem. Thanks for your explanations and your patience!
> :-)
>
> Best,
> srach

No problem man. As mentioned, I believe the root cause of the
misunderstanding was my shoddy use of terminology.

However, as so often happens, having this conversation forced me to
rethink the problem some more and I came up with another adjustment
of the metric. This has to do with the distinction between a move and
a hopchain.

When re-evaluating my central premise because of your question,
namely that two solvers with identical lookahead but differing
objective functions will proceed equally far before getting stuck on
average, I realised that it was true, but with a caveat. Two solvers
will proceed equally far in terms of NUMBER of pegs left on the board
at the end but not neccesarily in terms of WEIGHT of these pegs.

So what? might be your first reaction since both proposed metrics
prioritise removing heavy pegs we should be left with light pegs at
the end anyway. Well consider the following choice:
Hopchain 1 : Use a peg of weight 1 to jump 2 pegs of weights 5 and 6
respectively.
Hopchain 2 : Use a peg of weight 1 to jump another peg of weight 11.

Since the recursive solver works at the hopchain level all it gets to
compare is
1. Remove 11 for lifting penalty of 1.
2. Remove 11 for lifting penalty of 1.

So it is a tie, irrespective of the metric used. But considering the
earlier discussion, hopchain 2 really should be preferred. One
possible fix would be to change the summing of the removed weight
from
Removed weight= removed so far + weight of next peg in hopchain.
To
Removed weight= removed so far + (weight of next peg in hopchain)^n.
where n is some empirically determined number greater than 1 but most
likely less than 2.

Comments?

H

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: Yi Cao

Date: 21 May, 2007 07:01:52

Message: 159 of 221

Hannes Naudé wrote:
>
>
> srach wrote:
>> Since the first kind of moves removesdd 10 pts per move and the
>> second kind only 5 pts per move, I concluded that, in order to
>> remove
>> a total of 100 pts, the first kind needs 10 moves and the
second
>> would need 20. Of course, this was complete nonsense in the
> context
>> of this problem. Thanks for your explanations and your
patience!
>> :-)
>>
>> Best,
>> srach
>
> No problem man. As mentioned, I believe the root cause of the
> misunderstanding was my shoddy use of terminology.
>
> However, as so often happens, having this conversation forced me to
> rethink the problem some more and I came up with another adjustment
> of the metric. This has to do with the distinction between a move
> and
> a hopchain.
>
> When re-evaluating my central premise because of your question,
> namely that two solvers with identical lookahead but differing
> objective functions will proceed equally far before getting stuck
> on
> average, I realised that it was true, but with a caveat. Two
> solvers
> will proceed equally far in terms of NUMBER of pegs left on the
> board
> at the end but not neccesarily in terms of WEIGHT of these pegs.
>
> So what? might be your first reaction since both proposed metrics
> prioritise removing heavy pegs we should be left with light pegs at
> the end anyway. Well consider the following choice:
> Hopchain 1 : Use a peg of weight 1 to jump 2 pegs of weights 5 and
> 6
> respectively.
> Hopchain 2 : Use a peg of weight 1 to jump another peg of weight
> 11.
>
> Since the recursive solver works at the hopchain level all it gets
> to
> compare is
> 1. Remove 11 for lifting penalty of 1.
> 2. Remove 11 for lifting penalty of 1.
>
> So it is a tie, irrespective of the metric used. But considering
> the
> earlier discussion, hopchain 2 really should be preferred. One
> possible fix would be to change the summing of the removed weight
> from
> Removed weight= removed so far + weight of next peg in hopchain.
> To
> Removed weight= removed so far + (weight of next peg in
> hopchain)^n.
> where n is some empirically determined number greater than 1 but
> most
> likely less than 2.
>
> Comments?
>
> H

In theory, there is no definite conclusion on which metric is
absolutely better than another one, even statistically (at least for
the sample and actual suits) the ratio metric is better than
"greedy". For example, for the subsoltweak code, seems greedy metric
is statistically better than the ratio metric.

Another thinking is based on the factor that the final score =
remaining pegs + lifting pegs. Therefore, it is equivalent using a
pegs for lifting and leaving it on the final board. If a pegs is used
for lifting then later to be removed by another peg, then the effect
of this peg is cancled, the score will be the same as using the
second lifting peg to remove the first peg. Based on this
observation, to minimize the overall score, what we could do is
avoiding to use large weight pegs for lifting (min board(F(h))) and
removing pegs with weight as large as possible (max
board(M(h))+chain). Therefore, this is a multiobjective optimization
problem. The greedy metric uses a fixed equal weight to combine these
tow objectives: board(M(h))-board(F(h)) linearly, while the ratio
metric combines them nonlinearly. Both can be improved by introducing
different weight: linear (greedy) metric: board(M(h)) -
(1+alpha)*board(F(h)) and nonlinear (ratio) metric:
board(M(h))./(board(F(h)+alpha). I have tested both, all work fine
with appropriately tuned weights.

However, the above explanation motivates me to think another
improvement. Currently, all three solvers (subsoltweak, subsol and
solveri) works independently. This makes us wast a lot of time to
repeat some searchs without knowing if new search has opportunity to
improve. If we can use some information obtained from previous
solver, then we may more likely get improved scores. Here is the
rough idea how this can be done:

1. run subsoltweak to get initial moves. Record all lifting pegs and
remaining pegs in a peg pool. sum of the pool is the score of this
run.
2. pass the peg pool to subsol. In subsol, we limit the max weight of
lifting pegs to be less than the max weight of the pool and give
havey weight to a possible move, which removes a peg with weight
larger than the maximum weight of the pool and uses a lifting peg
with weight less than the maximum pool weight. The pool should be
updated, i.e. when a new move selected, the lifting weight should be
removed from the pool, hence the maximum weight of the pool will
dynamically change.
3. similar idea may also apply to solveri.

In this way, we can ensure every time runing subsol or solveri we
more likely will get some improvement.

Any comments?

Yi

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: Hannes Naudé

Date: 21 May, 2007 07:54:48

Message: 160 of 221

Yi Cao wrote:
> Another thinking is based on the factor that the final score =
> remaining pegs + lifting pegs. Therefore, it is equivalent using a
> pegs for lifting and leaving it on the final board. If a pegs is
> used
> for lifting then later to be removed by another peg, then the
> effect
> of this peg is cancled, the score will be the same as using the
> second lifting peg to remove the first peg. Based on this
> observation, to minimize the overall score, what we could do is
> avoiding to use large weight pegs for lifting (min board(F(h))) and
> removing pegs with weight as large as possible (max
> board(M(h))+chain). Therefore, this is a multiobjective
> optimization
> problem. The greedy metric uses a fixed equal weight to combine
> these
> tow objectives: board(M(h))-board(F(h)) linearly, while the ratio
> metric combines them nonlinearly.

Now that I have given it more thought, I disagree with this
explanation. Firstly, it will make the upcoming argument simpler if
we can agree to disregard the effect of the postprocessing step that
removes net negative moves tacked on to the end of the movelist.

Now, the core of my disagreement with your explanation is the fact
that neither of these metrics are truly multi-objective. The one
"objective" that you have mentioned, namely leaving the minimum
weight on the board at the end is actually built into the structure
of the solver and not dependent on the objective function at all.

To see that this is the truth, consider what would happen if you
changed the greedy metric to :
-board(M(h))-board(F(h))
According to your explanation this is then a multiobjective
optimization that seeks to leave as much weight as possible on the
board and minimise the lifting penalty. The obvious solution is to
return an empty movelist. But (if you neglect the postprocessing)
this is not what happens, the board is still almost cleared, at an
immense lifting cost.

If we accept that a fixed amount of weight will be removed, then the
metrics do the following.
Greedy Metric : Remove the fixed amount of weight using as few
hopchains as possible.
Ratio Metric : Remove the fixed amount of weight as efficiently as
possible.

Hope this makes sense.

Regards
H

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: Yi Cao

Date: 21 May, 2007 13:15:21

Message: 161 of 221

Hannes Naudé wrote:
>
> Now, the core of my disagreement with your explanation is the fact
> that neither of these metrics are truly multi-objective. The one
> "objective" that you have mentioned, namely leaving the minimum
> weight on the board at the end is actually built into the structure
> of the solver and not dependent on the objective function at all.
>
If that is true, then we only need to minimize board(F(h)) at each
step. Have you tested this? I doubt this would lead to an optimal
solution. We still need some information in the metric to ensure the
remaining weights are reasonable small, such as the ratio metric and
greedy metric. I did test with a modified linear metric, i.e.
board(M(h)) - (1+alpha)*board(F(h)) with 0 < alpha < 1. It does
have the similar effect of the ratio metric although it is not as
efficient as the the ratio metric, because the ratio metric is
nonlinear (interms of lifting weights).

Yi

Subject: MATLAB Programming Contest: May 9 - May 16, 2007

From: Ken Eaton

Date: 21 May, 2007 16:14:30

Message: 162 of 221

Hannes Naudé wrote:

> Another
> possiblity is using endgame libraries (like checkers and chess
> programs do). However, I believe that the scores of the leading
> solvers are dominated by the lifting penalty component, so any
> reduction in weight left on the board will probably not have a
> significant impact.

I would tend to agree with this. Early on in the contest I had the
idea to try and match libraries of standard patterns to the current
board and pick the pattern with the best pay-off ("predator/prey
tactics" series). I also had the idea of finding ways to string these
patterns together so that they could quickly clear large swaths of
the board ("predator/prey chain reaction" series). The focus was on
clearing as many pegs as possible. However, the results weren't as
good as other methods I tried, and it could take a while to run with
even just a small number of patterns to check. I didn't really do
much with the pattern matching algorithm after that.

Ken

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: Hannes Naudé

Date: 22 May, 2007 01:39:48

Message: 163 of 221

Yi Cao wrote:
>
>
> Hannes Naudé wrote:
>>
>> Now, the core of my disagreement with your explanation is the
> fact
>> that neither of these metrics are truly multi-objective. The
one
>> "objective" that you have mentioned, namely leaving the minimum
>> weight on the board at the end is actually built into the
> structure
>> of the solver and not dependent on the objective function at
all.
>>
> If that is true, then we only need to minimize board(F(h)) at each
> step. Have you tested this? I doubt this would lead to an optimal
> solution.

No, it would not, but the reason is subtle. We cannot minimize the
sum of board(F(h)) over all steps by minimizing board(F(h)) at each
step, because the number of steps (hopchains) is itself variable.
Therefore we need to take this into acount.

Part of the reason, why this is tricky to grasp is the fact that the
units for cost and reward are the same. To make this clearer,
consider the following analogy. You need to travel 200km to your
destination and want to do so for the minimum cost, but you can only
plan one leg of the journey ahead. Three options open to you.
Bus: Takes you 100km towards your destination. Cost $70.
Train: Takes you 50km towards your destination. Cost $25.
Tram: Takes you 2km towards your destination. Cost $4.

The obvious way to handle the situation is to compute which option
costs the least per kilometer. At $0.50/km the Train is the most cost
effective option. This is analogous to using the ratio metric.

The greedy metric would point to using the Bus, while simply
minimizng the cost of each step, as you proposed, would select the
tram since it is the cheapest leg. However selecting transport in
this way will end up expensive, not because of any particular leg of
the journey but because the journey will end up having many legs.

Note that this is NOT the same as maximising the distance travelled.
We assumed at the outset that we will travel a fixed distance of
200km. We are not maximising the distance travelled, we are merely
factoring it in to determine whether a "cheap" mode of transport is
truly a good deal. Similarly we are not maximising the weight removed
from the board at a particular step, we are merely factoring it in to
determine whether a "light" hopchain is truly a good deal.

Regards
Hannes

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: Yi Cao

Date: 22 May, 2007 03:30:19

Message: 164 of 221

Hannes Naudé wrote:
>
> To see that this is the truth, consider what would happen if you
> changed the greedy metric to :
> -board(M(h))-board(F(h))
> According to your explanation this is then a multiobjective
> optimization that seeks to leave as much weight as possible on the
> board and minimise the lifting penalty. The obvious solution is to
> return an empty movelist. But (if you neglect the postprocessing)
> this is not what happens, the board is still almost cleared, at an
> immense lifting cost.
>
But we cannot neglect the postprocessing. If so, ratio metric may
also not lead to a good solution. The postprocessing will reject all
moves and does return an empty movelist. This example seems support
my multiobjective view.

Regards,
Yi

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: Yi Cao

Date: 22 May, 2007 04:30:15

Message: 165 of 221

Hannes Naudé wrote:
>
> No, it would not, but the reason is subtle. We cannot minimize the
> sum of board(F(h)) over all steps by minimizing board(F(h)) at each
> step, because the number of steps (hopchains) is itself variable.
> Therefore we need to take this into acount.
>
> Part of the reason, why this is tricky to grasp is the fact that
> the
> units for cost and reward are the same. To make this clearer,
> consider the following analogy. You need to travel 200km to your
> destination and want to do so for the minimum cost, but you can
> only
> plan one leg of the journey ahead. Three options open to you.
> Bus: Takes you 100km towards your destination. Cost $70.
> Train: Takes you 50km towards your destination. Cost $25.
> Tram: Takes you 2km towards your destination. Cost $4.
>
> The obvious way to handle the situation is to compute which option
> costs the least per kilometer. At $0.50/km the Train is the most
> cost
> effective option. This is analogous to using the ratio metric.
>
> The greedy metric would point to using the Bus, while simply
> minimizng the cost of each step, as you proposed, would select the
> tram since it is the cheapest leg. However selecting transport in
> this way will end up expensive, not because of any particular leg
> of
> the journey but because the journey will end up having many legs.
>
> Note that this is NOT the same as maximising the distance
> travelled.
> We assumed at the outset that we will travel a fixed distance of
> 200km. We are not maximising the distance travelled, we are merely
> factoring it in to determine whether a "cheap" mode of transport is
> truly a good deal. Similarly we are not maximising the weight
> removed
> from the board at a particular step, we are merely factoring it in
> to
> determine whether a "light" hopchain is truly a good deal.
>
> Regards
> Hannes
Thanks for the explanation. I can see where your reasonning comes
from. Everything is based on the assumption that the final total
remaining weight is a constant. If this assumption is true, the ratio
metric is perfect. We have the optimal solution here. No any further
discussion is necessary. However, it is not. Maybe it is almost true
in statistical sense. That is why for a few caases, the greedy metric
will still overperform the ratio metric and it is also the reason why
a weaker ratio metric is better in most cases.

Using your example, if we consider the situation a little bit more
complex and more practice, the exact distances for different travel
means are different. For some areas, from A to B, the bus route might
be much shorter than the train route. In this case, taking bus may
become the best option.

Variation of the distance is eqivalent to variation of total
remaining weights in the contest problem. Unfortunately, this is very
likely simply because current algorithm cannot guarantee what will be
left.

Regards,
Yi

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: Hannes Naudé

Date: 22 May, 2007 04:37:32

Message: 166 of 221

Yi Cao wrote:
>
>
> Hannes Naudé wrote:
>>
>> To see that this is the truth, consider what would happen if
you
>> changed the greedy metric to :
>> -board(M(h))-board(F(h))
>> According to your explanation this is then a multiobjective
>> optimization that seeks to leave as much weight as possible on
> the
>> board and minimise the lifting penalty. The obvious solution is
> to
>> return an empty movelist. But (if you neglect the
postprocessing)
>> this is not what happens, the board is still almost cleared, at
> an
>> immense lifting cost.
>>
> But we cannot neglect the postprocessing. If so, ratio metric may
> also not lead to a good solution. The postprocessing will reject
> all
> moves and does return an empty movelist. This example seems support
> my multiobjective view.
>
> Regards,
> Yi

Well that depends on what you mean by "a good result".

Neglecting postprocessing will have a minimal effect on the result of
the leading solvers. Yes it may be a few 1000 points and yes, that
might seem like a lot considering the size of the advances we have
been making, but remember that we are close (relatively speaking) to
the optimal result, so any advances will neccesarily be small. When
seen in the context of all possible solvers and their results, the
difference between the leading solver with or without postprocessing
is negligible.

To show why postprocessing confuses the issue, consider yet ANOTHER
example. Change the greedy metric to:
+board(M(h))+board(F(h)). Do not neglect postprocessing. According to
the multiobjective view this is now a solver that seeks to maximise
both lifting penalty and weight removed. Obviously such a solver
should never stop if a legal move is still available, since any move
will increas both wigh removed and lifting penalty. However, you can
see that postprocessing will remove large chunks of your movelist,
leaving you with a "worse" result in terms of your objectives than
would otherwise be the case.

In summary, when optimising objectives that are significantly
different from the original contest goals, postprocessing should
eiher be updated to reflect the new goals or neglected alltogether.
Since the update is more often than not non-trivial and in some cases
impossible, and the difference between a good solver with or without
post-processing will be negligible in the bigger picture anyway,
neglecting post-processing is the obvious answer. This allows us to
focus on the underlying behaviour of the solver itself instead of
being distracted by postprocessing behaviour which may be spurious in
the new context.

Regards
Hannes

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: Yi Cao

Date: 22 May, 2007 05:40:52

Message: 167 of 221

Hannes Naudé wrote:
>
> To show why postprocessing confuses the issue, consider yet ANOTHER
> example. Change the greedy metric to:
> +board(M(h))+board(F(h)). Do not neglect postprocessing. According
> to
> the multiobjective view this is now a solver that seeks to maximise
> both lifting penalty and weight removed. Obviously such a solver
> should never stop if a legal move is still available, since any
> move
> will increas both wigh removed and lifting penalty. However, you
> can
> see that postprocessing will remove large chunks of your movelist,
> leaving you with a "worse" result in terms of your objectives than
> would otherwise be the case.
>
That makes me confused. Why should a postprocess remove any part of
the movelist? Postprocessing should only remove those part which
makes the overall score worse, i.e. after cumsum, the score becomes
negative. Here, under your assumption, all moves have positive
contribution, hence at the end none of them should be removed. Then
again, this example supports the multiobjective concept.

Regards,
Yi

Subject: MATLAB Programming Contest: May 9 - May 16, 2007

From: Hannes Naudé

Date: 22 May, 2007 08:20:10

Message: 168 of 221

Yi Cao wrote:
> Thanks for the explanation. I can see where your reasonning comes
> from. Everything is based on the assumption that the final total
> remaining weight is a constant. If this assumption is true, the
> ratio
> metric is perfect. We have the optimal solution here. No any
> further
> discussion is necessary. However, it is not. Maybe it is almost
> true
> in statistical sense. That is why for a few caases, the greedy
> metric
> will still overperform the ratio metric and it is also the reason
> why
> a weaker ratio metric is better in most cases.

No, the ratio metric is far from perfect. But the imperfection has
more to do with our limited lookahead that with the validity or
therwise of the "pseudo-constant weight remaining" assumption.

Returning to the transport analogy. We may agree that FOR THE
INFORMATION GIVEN the train is the best option. However it may turn
out that the end of the train is a desolate little town with few or
no outgoing public transport. Then we may have to pay an extortionate
amount to complete our 200km journey or we may not be able to
complete it at all. This is equivalent to reaching a board
configuration with few or no legal moves. In this situation the bus
or tram route may have been the better option.

HOWEVER we must emphasize that there is NO way to know this with the
information given. Therefore changing our choice to bus or tram is
just as likely to worsen the situation as to improve it. This is the
reason why the ratio metric does not and cannot find the global
minimum. Given that we have not reached the global minimum it is no
surprising that the greedy metric may outperform us from time to
time, as will a random approach.

The core of our disagreement is the fact that I believe that
(unlikely as this may seem) we cannot influence the amount of weight
left on the board when the run completes by adjusting only the
objective function and I derived the ratio metric based on this
axiom. You on the other hand believe that the objective function is
multiobjective and controls:
-The lifting penalty
-The amount of weight left on the board.

To settle this matter, I propose the following acid test:
First adjust grade to neglect the lifting penalty (or even better, to
report it separately) so that the reported score is just the amount
of weight left on the board at the end.

Now apparently you have allready modified the greedy metric to the
following:
> board(M(h)) - (1+alpha)*board(F(h))

In your interpretation, adjusting alpha from 0 toward -1 will place
more and more emphasis on the remaining weight and less and less
emphasis on the lifting penalty. According to this if you set alpha =
0 then -0.1 then
-0.2, -0.3 ... and finally -1 a trend should emerge so less weight is
left on the board (ie. the modified score improves) for lower values
of alpha. This will prove your multiobjective view conclusively, I
will eat my hat, and the discussion will be over.

My conjecture however is that any effect of alpha on the amount of
weight remaining on the board will probably be too small to be
measurable.

Regards
Hannes

Subject: MATLAB Programming Contest: May 9 - May 16, 2007

From: Yi Cao

Date: 22 May, 2007 09:28:31

Message: 169 of 221

Hannes Naudé wrote:

> axiom. You on the other hand believe that the objective function is
> multiobjective and controls:
> -The lifting penalty
> -The amount of weight left on the board.
>
No, this is a misunderstanding. My multiobjective concept is purely
local not global, i.e. locally at each step, we have two objectives:
1. maximize the total weights to be removed in a single or a chain of
move, i.e. board(M(h))+CV
2. minimize the lifting weight, board(F(h))

We cannot guarantee local maximizations of removed weights will lead
to minimization of the final total remaining weights, just like
locally minimizing the lifting weight would not necessary lead to
total lifting wieght minimized, or locally maximizating the ratio
metric will not necessarily result in a global minimization of the
ratio. Therefore, the test you proposed is also not relevant.

I think the multiobjective concept just a different view to
understand the ratio metrc and greedy metric. From this point view,
the weaker metric becomes more understandable.

Regards,
Yi

Subject: MATLAB Programming Contest: May 9 - May 16, 2007

From: Hannes Naudé

Date: 22 May, 2007 09:40:57

Message: 170 of 221

Yi Cao wrote:
>
>
> Hannes Naudé wrote:
>
>> axiom. You on the other hand believe that the objective
function
> is
>> multiobjective and controls:
>> -The lifting penalty
>> -The amount of weight left on the board.
>>
> No, this is a misunderstanding. My multiobjective concept is purely
> local not global, i.e. locally at each step, we have two
> objectives:
> 1. maximize the total weights to be removed in a single or a chain
> of
> move, i.e. board(M(h))+CV
> 2. minimize the lifting weight, board(F(h))

Well, this is the point "Objective" 1 is a waste of time because it
will have NO effect on the corresponding global version of this
objective. And ultimately it is only the global version that counts.
 
> We cannot guarantee local maximizations of removed weights will
> lead
> to minimization of the final total remaining weights, just like
> locally minimizing the lifting weight would not necessary lead to
> total lifting wieght minimized, or locally maximizating the ratio
> metric will not necessarily result in a global minimization of the
> ratio. Therefore, the test you proposed is also not relevant.
>
> I think the multiobjective concept just a different view to
> understand the ratio metrc and greedy metric. From this point view,
> the weaker metric becomes more understandable.
>
> Regards,
> Yi

No, ofcourse no guarantees can be made. So I was not asking that the
sequence of modified scores as alpha is reduced from 0 to -1 be
monotonically decreasing. I was merely asking if a trend (even a weak
one) is visible.

Surely you cannot claim that you are doing multi-objective
optimization and not be able to show ANY effect of your relative
objective weighting on the outcome of one of your objectives??

If the knob is labeled volume, then a link between the turning of the
knob and the resulting AVERAGE volume of the music must be
demonstrable, even though this might be ocasionally overwhelmed by
volume differences in the music itself.

Otherwise the label is wrong.

Regards
Hannes

Subject: MATLAB Programming Contest: May 9 - May 16, 2007

From: Yi Cao

Date: 22 May, 2007 13:21:33

Message: 171 of 221

Hannes Naudé wrote:
>
> No, ofcourse no guarantees can be made. So I was not asking that
> the
> sequence of modified scores as alpha is reduced from 0 to -1 be
> monotonically decreasing. I was merely asking if a trend (even a
> weak
> one) is visible.
>
> Surely you cannot claim that you are doing multi-objective
> optimization and not be able to show ANY effect of your relative
> objective weighting on the outcome of one of your objectives??
>
> If the knob is labeled volume, then a link between the turning of
> the
> knob and the resulting AVERAGE volume of the music must be
> demonstrable, even though this might be ocasionally overwhelmed by
> volume differences in the music itself.
>
> Otherwise the label is wrong.
>
Ok, I take the challenge. Here is the report of what I found. I used
one of my simple version of subsol submitted on thrusday and modified
the metric with C0+CV-alpha*board(F(h)). Also assigned a second
output argument as the total weight remained on the board. Then just
load the testsuit, use a for loop to sum all remain weight for all
122 cases. Here are findings:

alpha weights remaining
-1 12651
-0.8 12588
-0.6 12715
-0.4 12997
-0.2 13381
0 13651
0.2 13836
0.4 14055
0.6 14829
0.8 15396
1.0 15820

Here, the trend is clear: increase alpha for lifting weight of pegs,
remaining weight will consistently increase, except in the alpha = -1
case, where the lifting weight is completely removed from the metric.
These results are better than I expected. But they do support my
multiobjective concept. The conclusion is that remaining weight is
not a constant, and also is controllable.

Regards,
Yi

Subject: MATLAB Programming Contest: May 9 - May 16, 2007

From: Sergey Yurgenson

Date: 22 May, 2007 15:10:45

Message: 172 of 221

Yi Cao wrote:
>
>
> Hannes Naudé wrote:
>>
>> No, ofcourse no guarantees can be made. So I was not asking
that
>> the
>> sequence of modified scores as alpha is reduced from 0 to -1 be
>> monotonically decreasing. I was merely asking if a trend (even
a
>> weak
>> one) is visible.
>>
>> Surely you cannot claim that you are doing multi-objective
>> optimization and not be able to show ANY effect of your
relative
>> objective weighting on the outcome of one of your objectives??
>>
>> If the knob is labeled volume, then a link between the turning
of
>> the
>> knob and the resulting AVERAGE volume of the music must be
>> demonstrable, even though this might be ocasionally overwhelmed
> by
>> volume differences in the music itself.
>>
>> Otherwise the label is wrong.
>>
> Ok, I take the challenge. Here is the report of what I found. I
> used
> one of my simple version of subsol submitted on thrusday and
> modified
> the metric with C0+CV-alpha*board(F(h)). Also assigned a second
> output argument as the total weight remained on the board. Then
> just
> load the testsuit, use a for loop to sum all remain weight for all
> 122 cases. Here are findings:
>
> alpha weights remaining
> -1 12651
> -0.8 12588
> -0.6 12715
> -0.4 12997
> -0.2 13381
> 0 13651
> 0.2 13836
> 0.4 14055
> 0.6 14829
> 0.8 15396
> 1.0 15820
>
> Here, the trend is clear: increase alpha for lifting weight of
> pegs,
> remaining weight will consistently increase, except in the alpha =
> -1
> case, where the lifting weight is completely removed from the
> metric.
> These results are better than I expected. But they do support my
> multiobjective concept. The conclusion is that remaining weight is
> not a constant, and also is controllable.
>
> Regards,
> Yi

Very clear dependence.
Did you check for –1.2 . . .-2 ?
And how did it affect the result (score)?

Sergey

Subject: MATLAB Programming Contest: May 9 - May 16, 2007

From: Yi Cao

Date: 22 May, 2007 17:24:14

Message: 173 of 221

Sergey Yurgenson wrote:
>
>
> Yi Cao wrote:
>>
>>
>> Hannes Naudé wrote:
>>>
>>> No, ofcourse no guarantees can be made. So I was not asking
> that
>>> the
>>> sequence of modified scores as alpha is reduced from 0 to
-1
> be
>>> monotonically decreasing. I was merely asking if a trend
> (even
> a
>>> weak
>>> one) is visible.
>>>
>>> Surely you cannot claim that you are doing multi-objective
>>> optimization and not be able to show ANY effect of your
> relative
>>> objective weighting on the outcome of one of your
> objectives??
>>>
>>> If the knob is labeled volume, then a link between the
> turning
> of
>>> the
>>> knob and the resulting AVERAGE volume of the music must be
>>> demonstrable, even though this might be ocasionally
> overwhelmed
>> by
>>> volume differences in the music itself.
>>>
>>> Otherwise the label is wrong.
>>>
>> Ok, I take the challenge. Here is the report of what I found. I
>> used
>> one of my simple version of subsol submitted on thrusday and
>> modified
>> the metric with C0+CV-alpha*board(F(h)). Also assigned a second
>> output argument as the total weight remained on the board. Then
>> just
>> load the testsuit, use a for loop to sum all remain weight for
> all
>> 122 cases. Here are findings:
>>
>> alpha weights remaining
>> -1 12651
>> -0.8 12588
>> -0.6 12715
>> -0.4 12997
>> -0.2 13381
>> 0 13651
>> 0.2 13836
>> 0.4 14055
>> 0.6 14829
>> 0.8 15396
>> 1.0 15820
>>
>> Here, the trend is clear: increase alpha for lifting weight of
>> pegs,
>> remaining weight will consistently increase, except in the
alpha
> =
>> -1
>> case, where the lifting weight is completely removed from the
>> metric.
>> These results are better than I expected. But they do support
my
>> multiobjective concept. The conclusion is that remaining weight
> is
>> not a constant, and also is controllable.
>>
>> Regards,
>> Yi
>
> Very clear dependence.
> Did you check for –1.2 . . .-2 ?
> And how did it affect the result (score)?
>
> Sergey
Here are the results for alpha=-2:0.1:2,

         alpha remain lifting score
           -2 13087 64538 77626
         -1.9 12940 62704 75644
         -1.8 12787 61127 73914
         -1.7 13055 59298 72352
         -1.6 13227 57056 70282
         -1.5 13103 55266 68369
         -1.4 13203 54177 67380
         -1.3 14061 51599 65661
         -1.2 13048 49832 62881
         -1.1 14117 47427 61544
           -1 13791 43778 57569
         -0.9 13534 40549 54083
         -0.8 13486 39092 52577
         -0.7 13774 38055 51829
         -0.6 13599 36927 50527
         -0.5 13898 35302 49199
         -0.4 13987 34844 48831
         -0.3 14007 33436 47443
         -0.2 14606 32712 47318
         -0.1 14506 31879 46385
            0 14866 31538 46404
          0.1 14538 31179 45717
          0.2 14996 30727 45723
          0.3 14839 30781 45621
          0.4 15038 30521 45559
          0.5 15163 30535 45698
          0.6 15721 30348 46069
          0.7 15791 30368 46160
          0.8 16303 30214 46517
          0.9 16723 30033 46756
            1 16843 30078 46921
          1.1 16997 30491 47487
          1.2 17346 30396 47742
          1.3 17541 30229 47769
          1.4 17632 30377 48009
          1.5 17759 30467 48226
          1.6 17941 30491 48432
          1.7 17826 30843 48669
          1.8 17984 30613 48597
          1.9 17845 30819 48665
            2 17991 30700 48691

As I expected, best alpha should be within [0 1]. In this case,
alpha=0.4 is the best. Overall, the trend is clear although there are
some local fluctuations. Within [-2 -1] range, the remain weight
becomes uncertain. This is understandable because in this case, the
metric becomes board(M(h))+beta*board(F(h)) with beta=-alpha-1>0,
which will not necessarily make remains minimized.

Regards,
Yi

Subject: MATLAB Programming Contest: May 9 - May 16, 2007

From: Hannes Naudé

Date: 23 May, 2007 01:47:08

Message: 174 of 221

Yi Cao wrote:
> These results are better than I expected. But they do support my
> multiobjective concept. The conclusion is that remaining weight is
> not a constant, and also is controllable.
>
> Regards,
> Yi

Extremely clear depedency!! I am eating my hat as I type. Ahh, the
taste of cotton & cardboard in the morning!

Anyway, I am totally baffled by this, but clearly I am the only one.
I have very little knowledge of subsol, so I have to ask:
-Does this work for the recursive solver as well?
-Is there any postprocessing, and if so did you modify that as well?
-Lastly, I would like to play with this a bit, as it has become clear
that my understanding of the problem and ts solution is built on
shaky axioms. Could you please send me the modified code?

Regards
Hannes

Subject: MATLAB Programming Contest: May 9 - May 16, 2007

From: Yi Cao

Date: 23 May, 2007 03:09:12

Message: 175 of 221

Hannes Naudé wrote:
>
> Extremely clear depedency!! I am eating my hat as I type. Ahh, the
> taste of cotton & cardboard in the morning!
>
> Anyway, I am totally baffled by this, but clearly I am the only
> one.
> I have very little knowledge of subsol, so I have to ask:
> -Does this work for the recursive solver as well?

I have not tried yet.

> -Is there any postprocessing, and if so did you modify that as
> well?

The first result I posted was without postprocessing, the second
result (for alpha = -2:0.1:2) was obtained after postprocessing.

> -Lastly, I would like to play with this a bit, as it has become
> clear
> that my understanding of the problem and ts solution is built on
> shaky axioms. Could you please send me the modified code?
>
Yes, no problem. I will email you the code.

Regards,
Yi

Subject: MATLAB Programming Contest: May 9 - May 16, 2007

From: Yi Cao

Date: 23 May, 2007 06:22:00

Message: 176 of 221

Hannes Naudé wrote:
> -Does this work for the recursive solver as well?
Now, I got results for a recursive solver, Cat54, the winning entry
of character 1000. Here are results:

         alpha remaining lifting
           -1 12923 29389
         -0.8 13202 29004
         -0.6 13301 28112
         -0.4 14350 27760
         -0.2 14325 27934
            0 14775 27885
          0.2 15099 27724
          0.4 15530 27728
          0.6 15353 27995
          0.8 16041 27900
            1 16024 27872

The dependency is still clear.

For solveri, it is a little bit complicated for me to figure out
where to put alpha. Maybe Hannes can tell us?

Regards,
Yi

Subject: MATLAB Programming Contest: May 9 - May 16, 2007

From: Hannes Naudé

Date: 23 May, 2007 07:11:29

Message: 177 of 221

Yi Cao wrote:
> For solveri, it is a little bit complicated for me to figure out
> where to put alpha. Maybe Hannes can tell us?
>
> Regards,
> Yi

I had a quick look, and you're right: it's quite complicated. It
looks like the mod should go inside the function CalculateHole and
CalculateBall where valbuf is computed, but I am not sure how to
modify nor even that these are the only places where the mod needs to
be made. Am at work now, so can't spend too much time figuring it
out, will take a more detailed look tonight, unless someone else can
tell us before then.

I've given your results some thought, and have come to the conclusion
that the dependency must be due to an effect that I described earlier
in this thread, but then forgot all about. Namely, adjustment of the
objective function will have zero effect on the NUMBER of pegs left
on the board at the end but not neccesarily on the total WEIGHT of
these pegs. Therefore a more greedy solver may (and according to your
results does) end up with less weight on the board, not because it
reached a better end configuration, but because all the really heavy
pegs were removed early in the run. So if we could add another column
to your results representing the number of pegs left at the end, we
would expect this column to show no dependency on the weighting
parameters. Agree?

I will be doing my own experiments tonight to confirm or disprove
this hypothesis, but would also be very interested to see your
results should you decide to to investigate. If this is truly the
case it means that we can get the best of both worlds (least weight
on the board at the end as well as minimal lifting penalty) by using
a ratio metric on weights that have been raised to a power as
mentioned earlier in this thread. I proposed this improvemen but did
not investigate because I thought the gains would be minimal, but
your results seem to indicate otherwise.

Regards
Hannes

Subject: MATLAB Programming Contest: May 9 - May 16, 2007

From: Sergey Yurgenson

Date: 23 May, 2007 07:26:33

Message: 178 of 221

Yi Cao wrote:
>
>
> Hannes Naudé wrote:
>> -Does this work for the recursive solver as well?
> Now, I got results for a recursive solver, Cat54, the winning entry
> of character 1000. Here are results:
>
> alpha remaining lifting
> -1 12923 29389
> -0.8 13202 29004
> -0.6 13301 28112
> -0.4 14350 27760
> -0.2 14325 27934
> 0 14775 27885
> 0.2 15099 27724
> 0.4 15530 27728
> 0.6 15353 27995
> 0.8 16041 27900
> 1 16024 27872
>
> The dependency is still clear.
>
> For solveri, it is a little bit complicated for me to figure out
> where to put alpha. Maybe Hannes can tell us?
>
> Regards,
> Yi
  

Could you please tell where did you put alpha in Cat54.
One weighting coefficient is already there (it was the reason of
winning)
Best wishes,
Sergey

Subject: MATLAB Programming Contest: May 9 - May 16, 2007

From: Yi Cao

Date: 23 May, 2007 09:42:55

Message: 179 of 221

Sergey Yurgenson wrote:
>
> Could you please tell where did you put alpha in Cat54.
> One weighting coefficient is already there (it was the reason of
> winning)
> Best wishes,
> Sergey

I slightly modified the code to move the weight to outside of the
recursive function because within the recursive function, jumps are
in a chain, hence all use the same lifting peg. In the main loop,
after call the recursive function, I put an extra line:
B=B-(1+alpha)*b(f(k)); before the if line.

I can send you the code through email, if you wish.

Regards,
Yi

Subject: MATLAB Programming Contest: May 9 - May 16, 2007

From: Hannes Naudé

Date: 23 May, 2007 09:58:34

Message: 180 of 221

Hannes Naudé wrote:
> I've given your results some thought, and have come to the
> conclusion
> that the dependency must be due to an effect that I described
> earlier
> in this thread, but then forgot all about. Namely, adjustment of
> the
> objective function will have zero effect on the NUMBER of pegs left
> on the board at the end but not neccesarily on the total WEIGHT of
> these pegs. Therefore a more greedy solver may (and according to
> your
> results does) end up with less weight on the board, not because it
> reached a better end configuration, but because all the really
> heavy
> pegs were removed early in the run. So if we could add another
> column
> to your results representing the number of pegs left at the end, we
> would expect this column to show no dependency on the weighting
> parameters. Agree?

OK, utilised Yi's code to do a quick test on how the relative
weighting affects the number of pegs left at the end and got some
extremely interesting results.

Here are the results, for alpha from -1 to 1 in 0.2 increments.

         alpha remain lifting score pegs
           -1 13791 43778 57569 8276
         -0.8 13486 39092 52577 8006
         -0.6 13599 36927 50527 7843
         -0.4 13987 34844 48831 7867
         -0.2 14606 32712 47318 8023
            0 14866 31538 46404 7966
          0.2 14996 30727 45723 7787
          0.4 15038 30521 45559 7685
          0.6 15721 30348 46069 7681
          0.8 16303 30214 46517 7751
            1 16843 30078 46921 7720

These are Yi's exact results, but with a pegs column added. This
column just shows the total number of pegs left on the board at the
end. At first glance I thought I could see a weak trend, but then
realised that the supposed "trend" is going in the wrong direction.
So the hypothesis that differences in weight left on the board at the
end is caused by differences in the average weight on the board at
the end rather than by more or less efficient clearing of the board
seems to be confirmed.

Now for the interesting part. If you plot this relationship
explicitly:

         alpha remain/pegs
           -1 1.6664
         -0.8 1.6844
         -0.6 1.7340
         -0.4 1.7779
         -0.2 1.8206
            0 1.8662
          0.2 1.9258
          0.4 1.9568
          0.6 2.0467
          0.8 2.1039
            1 2.1818
  
the relationship forms a perfectly monotonic and almost perfectly
linear trend. If we change our axiom to be : the NUMBER of pegs
remaining on the board at game end is pseudo constant( cannot be
affected by the objective function) then we can derive the ideal
metric to be

Maximise (W(t-1)-W(t))*(N-M)-L/H

where:
N=number of pegs at start
M=estimated number of moves before we get stuck.
W(t-1) = Average weight of all pieces on the board before this
hopchain.
W(t) = Average weight of all pieces on the board after this hopchain.
H = Number of hops in this hopchain.
L = lifting penalty for this hopchain.

This is extremely satisfying because it has several properties that
were predicted by others in this discussion, based on intuition.
- At the beginning of the game it is very similar to the ratio metric
(since the difference in average weight caused by a move will
neccesarily be small when the board is full.
- Close to the end of the game it tends to the greedy metric.

One tricky thing about this metric is that we need to estimate the
number of moves before getting stuck. We can most likely get quite a
good estimate by just taking this to be some fraction of the
pegcount. Or in cases where we do more than 1 attempt at a given
problem, we can use the results from the previous run to calibrate
the metric for the next run.

Comments?

Once again, I have no idea how to implement this for subsol, or even
whether it can be done. But will take a look at working it into
solveri tonight.

Regards
Hannes

Subject: MATLAB Programming Contest: May 9 - May 16, 2007

From: Yi Cao

Date: 23 May, 2007 10:06:27

Message: 181 of 221

Hannes Naudé wrote:
>
> I've given your results some thought, and have come to the
> conclusion
> that the dependency must be due to an effect that I described
> earlier
> in this thread, but then forgot all about. Namely, adjustment of
> the
> objective function will have zero effect on the NUMBER of pegs left
> on the board at the end but not neccesarily on the total WEIGHT of
> these pegs. Therefore a more greedy solver may (and according to
> your
> results does) end up with less weight on the board, not because it
> reached a better end configuration, but because all the really
> heavy
> pegs were removed early in the run. So if we could add another
> column
> to your results representing the number of pegs left at the end, we
> would expect this column to show no dependency on the weighting
> parameters. Agree?
>
Agree. For completeness, I post the 4th column here for number of
pegs left:

         alpha remaining lifting No. left
          -1 13791 43778 8276
         -0.8 13486 39092 8006
         -0.6 13599 36927 7843
         -0.4 13987 34844 7867
         -0.2 14606 32712 8023
            0 14866 31538 7966
          0.2 14996 30727 7787
          0.4 15038 30521 7685
          0.6 15721 30348 7681
          0.8 16307 30211 7751
            1 16843 30078 7720

Dependency is very weak.

Actually, number of pegs left on the board is totally irrelevant for
the contest problem. Just look at Nick Howe's solution to the
Weighted English Board problem, where the new solution leaves 4 pegs
behind, but the score obtained (359) is much less than Lucio's
solution (407), which has cleaned the board completely (only one peg
left).

Another example, assume we havea board, which has n pegs with weight:
w1 > w2 > w3 > ... >wn.

Solution 1 (n-1 moves): jump w2 over w1, jump w3 over w2, ..., jump
wn over w(n-1).

Solution 2 (1 move): jump wn over w1.

So, solution 1 has cleaned the board with the minimum weight left,
whilst solution 2 only removes one peg and leaves n-1 pegs behind.
Intuitively, we may think solution 1 is better than solution 2.
However, both scores are the same!

These two examples tell us, it is not necessary to consider number of
pegs left. It is the weight no number left makes things different.


Regards,
Yi

Subject: MATLAB Programming Contest: May 9 - May 16, 2007

From: Yi Cao

Date: 23 May, 2007 10:19:44

Message: 182 of 221

Hannes Naudé wrote:
>
> One tricky thing about this metric is that we need to estimate the
> number of moves before getting stuck. We can most likely get quite
> a
> good estimate by just taking this to be some fraction of the
> pegcount. Or in cases where we do more than 1 attempt at a given
> problem, we can use the results from the previous run to calibrate
> the metric for the next run.
>
> Comments?
>
> Once again, I have no idea how to implement this for subsol, or
> even
> whether it can be done. But will take a look at working it into
> solveri tonight.
>
In current structure of solver, three different sub-solvers are
called in sequence. Therefore, we can call the first solver,
subsoltweak to get an estimation of N, if the hypothesis is true.

I look forward to seeing your results.

Regards,
Yi

Subject: MATLAB Programming Contest: May 9 - May 16, 2007

From: Sergey Yurgenson

Date: 23 May, 2007 12:16:49

Message: 183 of 221

Yi Cao wrote:
>
>
> Sergey Yurgenson wrote:
>>
>> Could you please tell where did you put alpha in Cat54.
>> One weighting coefficient is already there (it was the reason
of
>> winning)
>> Best wishes,
>> Sergey
>
> I slightly modified the code to move the weight to outside of the
> recursive function because within the recursive function, jumps are
> in a chain, hence all use the same lifting peg. In the main loop,
> after call the recursive function, I put an extra line:
> B=B-(1+alpha)*b(f(k)); before the if line.
>
> I can send you the code through email, if you wish.
>
> Regards,
> Yi
  

Thank you.
As you mentioned, moving weight out of recursive function (like this:
 p(ii)=-b(f(k))*(1+alpha);
 does not change anything .For some reason on my computer it runs
slightly faster when coefficient is inside.

What baffled me is that (p(ii)=-b(f(k))*(1+0.3);)is NOT absolutely
the same as
B=B-(1-0.7)*b(f(k)); after recursive function.

I have run some tests and find that B in version
“p(ii)=-b(f(k))*1.3;”
and version “B=B-(1-0.7)*b(f(k));” are different by arithmetic
rounding
(less than 2.2737e-013) which sometimes affects if B>G. By
accident that makes “B=B-(1-0.7)*b(f(k));” better than
“p(ii)=-b(f(k))*1.3;”

Subject: MATLAB Programming Contest: May 9 - May 16, 2007

From: Sergey Yurgenson

Date: 23 May, 2007 12:19:26

Message: 184 of 221

Yi Cao wrote:
>
>
> Hannes Naudé wrote:
>>
>> One tricky thing about this metric is that we need to estimate
> the
>> number of moves before getting stuck. We can most likely get
> quite
>> a
>> good estimate by just taking this to be some fraction of the
>> pegcount. Or in cases where we do more than 1 attempt at a
given
>> problem, we can use the results from the previous run to
> calibrate
>> the metric for the next run.
>>
>> Comments?
>>
>> Once again, I have no idea how to implement this for subsol, or
>> even
>> whether it can be done. But will take a look at working it into
>> solveri tonight.
>>
> In current structure of solver, three different sub-solvers are
> called in sequence. Therefore, we can call the first solver,
> subsoltweak to get an estimation of N, if the hypothesis is true.
>
> I look forward to seeing your results.
>
> Regards,
> Yi
  

If I understand idea correctly then the recursive solver is perfect
target for modification

Sergey

Subject: MATLAB Programming Contest: May 9 - May 16, 2007

From: Yi Cao

Date: 23 May, 2007 12:29:05

Message: 185 of 221

Sergey Yurgenson wrote:
>
> Thank you.
> As you mentioned, moving weight out of recursive function (like
> this:
> p(ii)=-b(f(k))*(1+alpha);
> does not change anything .For some reason on my computer it runs
> slightly faster when coefficient is inside.
>
> What baffled me is that (p(ii)=-b(f(k))*(1+0.3);)is NOT absolutely
> the same as
> B=B-(1-0.7)*b(f(k)); after recursive function.
>
> I have run some tests and find that B in version
> “p(ii)=-b(f(k))*1.3;”
> and version “B=B-(1-0.7)*b(f(k));” are different by arithmetic
> rounding
> (less than 2.2737e-013) which sometimes affects if B>G. By
> accident that makes “B=B-(1-0.7)*b(f(k));” better than
> “p(ii)=-b(f(k))*1.3;”

Actually, in the original version of Cat54, line with 1.3 inside is a
bug, because we just want to use 1.3 for selection but not to use it
as actual score. In the original version, 1.3 factor is recorded in p
and then later, the same p is used to select cuting point. Hence, it
is a bug. You can put 1.3 inside, but should not record it for later
peak selection. By correlcting this, you will get slightly higher
score.

Regards,
Yi

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: MikeR

Date: 23 May, 2007 12:38:33

Message: 186 of 221

Hello,

I've been catching a little bit of what Hannes and Yi are discussing
which is based upon the winning entry in the contest. Since I never
had enough time to completely digest all of the solvers that make up
the final solution I am having a little difficulty following the
trend analysis.

Although I never submitted it during the Darkness phase (was to slow
and buggy), I also created a recursive solver. I have begun to look
at it again and have fixed the bugs and speed issues. Now it is
running quickly and efficiently, scoring things in the 43000-45000
range in 20sec-5min.

I am wondering based on the trends you are identifying if you can
explain how if at all they relate to the depth and breadth of the
recursive search?

My recursive solver takes advantage of free jumps and branch re-use.
When calculating branch scores each branches moves are saved so no
recalculation is required if it is decided to be the lowest scoring
path.

Currently I use a simple relationship between the number of pegs and
a fraction to account for the depth and breadth per puzzle. I've
started to collect information regarding the trade off between score
and time with various fraction. I would ideally like to get my solver
to at least the level of the winning entry, but due to the size and
diversity of the winning entry it is a little tedious understanding
its advantages.

Thanks,

MikeR

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: Yi Cao

Date: 23 May, 2007 13:06:19

Message: 187 of 221

MikeR wrote:
>
>
> Hello,
>
> I've been catching a little bit of what Hannes and Yi are
> discussing
> which is based upon the winning entry in the contest. Since I never
> had enough time to completely digest all of the solvers that make
> up
> the final solution I am having a little difficulty following the
> trend analysis.
>
> Although I never submitted it during the Darkness phase (was to
> slow
> and buggy), I also created a recursive solver begun to look
> at it again and have fixed the bugs and speed issues. Now it is
> running quickly and efficiently, scoring things in the 43000-45000
> range in 20sec-5min.
>
> I am wondering based on the trends you are identifying if you can
> explain how if at all they relate to the depth and breadth of the
> recursive search?
>
> My recursive solver takes advantage of free jumps and branch
> re-use.
> When calculating branch scores each branches moves are saved so no
> recalculation is required if it is decided to be the lowest scoring
> path.
>
> Currently I use a simple relationship between the number of pegs
> and
> a fraction to account for the depth and breadth per puzzle. I've
> started to collect information regarding the trade off between
> score
> and time with various fraction. I would ideally like to get my
> solver
> to at least the level of the winning entry, but due to the size and
> diversity of the winning entry it is a little tedious understanding
> its advantages.
>
> Thanks,
>
> MikeR

The weaker ratio metric gain/(lifting+alpha) or linear metric gain -
alpha * lifting can be applied to a recursive solver, which may bring
score down to 40k to 41k (actual suite) or 43-44k (sample suite). If
your solver is fast enough, you may run it twice to get lower score.
To bring score down further, I think you have to combine different
kinds of solvers together. I am still baffled by why a recursive
algorithm cannot beat subsol. One reason could be within a long chain
of jumps, a few small weight pegs have been removed so that overall
lifting cost becomes higher. If this is true, then we need to find a
way to judge if a small weight peg is worth to be removed or not. For
example, we may introduce eaverage lifting penalty to judge the
effect of the length of chain and the weight of pegs to be removed.
Any ideas?

Regards,

Yi Cao
Regards,
Yi

Subject: MATLAB Programming Contest: May 9 - May 16, 2007

From: Sergey Yurgenson

Date: 23 May, 2007 13:07:35

Message: 188 of 221

Yi Cao wrote:
>
> You can put 1.3 inside, but should not record it for
> later
> peak selection. By correlcting this, you will get slightly higher
> score.
>
> Regards,
> Yi
  
Thank you,
Now I see it . The difference is in [v,ii]=max(cumsum(p));

Sergey

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: Nick Howe

Date: 23 May, 2007 13:31:50

Message: 189 of 221

Hannes Naudé wrote:
>
> Maximise (W(t-1)-W(t))*(N-M)-L/H
>
> where:
> N=number of pegs at start
> M=estimated number of moves before we get stuck.
> W(t-1) = Average weight of all pieces on the board before this
> hopchain.
> W(t) = Average weight of all pieces on the board after this
> hopchain.
> H = Number of hops in this hopchain.
> L = lifting penalty for this hopchain.
>

I've been following this discussion with interest, although my lack
of familiarity with the winning code has held me back from actual
involvement. I'm going to see if I can adapt this formula for use
with my beam search solution, which selects individual moves without
grouping into hopchains. When I tried the ratio metric, it didn't
improve things.

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: MikeR

Date: 23 May, 2007 14:09:08

Message: 190 of 221

I missed that post, thanks for pointing it out Nick. I implemented
this in my solver without much trouble. Initially I see no
performance gain but I do not have time to examine how it is working
with the boards.

As Hannes suggested I used different fractions of the number of
remaining pegs of the board after a hop set to determine the number
of pieces before we get stuck.

I might get time to examine this further tonight. This is fun stuff!

- MikeR

 Nick Howe wrote:
>
>
> Hannes Naudé wrote:
>>
>> Maximise (W(t-1)-W(t))*(N-M)-L/H
>>
>> where:
>> N=number of pegs at start
>> M=estimated number of moves before we get stuck.
>> W(t-1) = Average weight of all pieces on the board before this
>> hopchain.
>> W(t) = Average weight of all pieces on the board after this
>> hopchain.
>> H = Number of hops in this hopchain.
>> L = lifting penalty for this hopchain.
>>
>
> I've been following this discussion with interest, although my lack
> of familiarity with the winning code has held me back from actual
> involvement. I'm going to see if I can adapt this formula for use
> with my beam search solution, which selects individual moves
> without
> grouping into hopchains. When I tried the ratio metric, it didn't
> improve things.

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: Sergey Yurgenson

Date: 23 May, 2007 15:37:33

Message: 191 of 221

Yi Cao wrote:
> The weaker ratio metric gain/(lifting+alpha) or linear metric gain
> -
> alpha * lifting can be applied to a recursive solver, which may
> bring
> score down to 40k to 41k (actual suite) or 43-44k (sample suite).
> If
> your solver is fast enough, you may run it twice to get lower
> score.
> To bring score down further, I think you have to combine different
> kinds of solvers together. I am still baffled by why a recursive
> algorithm cannot beat subsol. One reason could be within a long
> chain
> of jumps, a few small weight pegs have been removed so that overall
> lifting cost becomes higher. If this is true, then we need to find
> a
> way to judge if a small weight peg is worth to be removed or not.
> For
> example, we may introduce eaverage lifting penalty to judge the
> effect of the length of chain and the weight of pegs to be removed.
> Any ideas?
>
> Regards,
>
> Yi Cao
> Regards,
> Yi
  

I have tried recursive algorithm (based on Cat45) with following
modifications:
B=B-(1+alpha)*b(f(k)); with alpha=-0.7;
And
O=O+p(ii)-min(b(b>0))*gamma; (inside recursive function) to
introdice some lifting penalty

Results:

Gamma score
0 41670
0.2 41631
0.4 41479
0.5 41398
0.6 41484
0.8 41613

Sergey

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: Yi Cao

Date: 23 May, 2007 17:25:03

Message: 192 of 221

Sergey Yurgenson wrote:
>
> I have tried recursive algorithm (based on Cat45) with following
> modifications:
> B=B-(1+alpha)*b(f(k)); with alpha=-0.7;
> And
> O=O+p(ii)-min(b(b>0))*gamma; (inside recursive function) to
> introdice some lifting penalty
>
> Results:
>
> Gamma score
> 0 41670
> 0.2 41631
> 0.4 41479
> 0.5 41398
> 0.6 41484
> 0.8 41613
>
> Sergey
That is interesting. somehow, min(b(b>0)) can punish jumping over
a small weigh peg. But calculating min(b(b>0)) inside the
recursive function must be expensive. Does it take a long time to
run?

Regards,
Yi

Subject: MATLAB Programming Contest: May 9 - May 16, 2007

From: Ken Eaton

Date: 23 May, 2007 17:49:53

Message: 193 of 221

As much as I have been able to follow along so far, the discussion
here has been pretty interesting albeit voluminous. Kudos for the
collaboration! Now my 2 cents...

I've noticed references here and there to "the number of pegs/weight
remaining on the board". I was wondering if and how people were
calculating this. I noticed that for some boards there are large
areas that can never be reached (i.e. no free spaces to move and -1s
disconnecting them from the rest of the board). For measurements of
the remaining pegs/weights, I imagine these areas should be ignored.

I had some code to do this in my final entries, removing
"untouchable" areas before I computed the remaining ratio of "even"
and "odd" (or "black" and "white") pegs. It seemed to help some of
the algorithms I was working with. Has anyone accounted for this in
the current algorithms?

Ken

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: Sergey Yurgenson

Date: 23 May, 2007 18:01:46

Message: 194 of 221

Yi Cao wrote:
>
>
> Sergey Yurgenson wrote:
> That is interesting. somehow, min(b(b>0)) can punish jumping
> over
> a small weigh peg. But calculating min(b(b>0)) inside the
> recursive function must be expensive. Does it take a long time to
> run?
>
> Regards,
> Yi
  
It took 72.5 sec vs. 51.4 sec without min(b(b>0))*gamma on my
laptop. However it can be easily optimized time-vise by passing total
number of pegs and total weight to the recursive function.

Subject: MATLAB Programming Contest: May 9 - May 16, 2007

From: Sergey Yurgenson

Date: 23 May, 2007 18:32:48

Message: 195 of 221

Ken Eaton wrote:
>
>
> I had some code to do this in my final entries, removing
> "untouchable" areas before I computed the remaining ratio of "even"
> and "odd" (or "black" and "white") pegs. It seemed to help some of
> the algorithms I was working with. Has anyone accounted for this in
> the current algorithms?
>
> Ken
  
Not as I know. I was trying to do the same. But I decided to use
bwlabel function which is part of Image Processing toolbox. Obviously
it did not work for competition. Then I abandoned this idea.

Subject: MATLAB Programming Contest: May 9 - May 16, 2007

From: Yi Cao

Date: 23 May, 2007 18:50:27

Message: 196 of 221

Sergey Yurgenson wrote:
>
>
> Ken Eaton wrote:
>>
>>
>> I had some code to do this in my final entries, removing
>> "untouchable" areas before I computed the remaining ratio of
> "even"
>> and "odd" (or "black" and "white") pegs. It seemed to help some
> of
>> the algorithms I was working with. Has anyone accounted for
this
> in
>> the current algorithms?
>>
>> Ken
>

> Not as I know. I was trying to do the same. But I decided to use
> bwlabel function which is part of Image Processing toolbox.
> Obviously
> it did not work for competition. Then I abandoned this idea.

In Nick Howe's Early Saturday Special winning entry, there were a few
line doing the similar thing. Later, for some reason, this was
abandoned. It found untouchable areas, then set all pegs in those
areas to -1. This has not been used for metrc, but for reducing
search space.

Regards,
Yi

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: srach

Date: 24 May, 2007 03:28:01

Message: 197 of 221

Ken Eaton wrote:
>
>
> As much as I have been able to follow along so far, the discussion
> here has been pretty interesting albeit voluminous. Kudos for the
> collaboration! Now my 2 cents...
>
> I've noticed references here and there to "the number of
> pegs/weight
> remaining on the board". I was wondering if and how people were
> calculating this. I noticed that for some boards there are large
> areas that can never be reached (i.e. no free spaces to move and
> -1s
> disconnecting them from the rest of the board). For measurements of
> the remaining pegs/weights, I imagine these areas should be
> ignored.
>
> I had some code to do this in my final entries, removing
> "untouchable" areas before I computed the remaining ratio of "even"
> and "odd" (or "black" and "white") pegs. It seemed to help some of
> the algorithms I was working with. Has anyone accounted for this in
> the current algorithms?
>
> Ken

I tested some entries that identified untouchable areas and resized
the board accordingly ("pslct *"-entries). However, there was only a
small gain in processing time due to resizing and that was eaten up
by my algorithm. Thus, I abandoned the idea.

Subject: MATLAB Programming Contest: May 9 - May 16, 2007

From: Hannes Naudé

Date: 24 May, 2007 04:32:28

Message: 198 of 221

Hi all.

Some interesting ideas floating around. I had ADSL installed
yesterday so didn't get round to testing the proposed new metric. But
I also developed my own recursive solver in the early stages of the
contest, and I think I will follow the examples of Mike and Nick and
rather modify my own code, since this will be a lot easier.

My recursive solver is quite interesting in that it takes the concept
of minimising recomputation to an extreme. It is actually built
around the concept of a jumptable. Each potential jump maintains
pointers to all (3 or less) jumps that may follow it as well as all
(3 or less) jumps that may precede it. Each jump also maintains the
best (in the greedy sense) hopchain that starts with that specific
jump currently known and the greedy score of this hopchain. When a
jump is chosen and executed, only the affected jumps need to be
updated. It lends itself to extensive use of early termination
criteria. It also potentially allows for easy identification of moves
that allow two previously separate hopchains to be strung together.

Unfortunately this solver took a bit long to implement and by the
time it was ready, I was having to compete with a highly speed tuned
hybrid solver. At the time I decided that the extra overhead of my
algorithm was clearly outweighing the scaling benefits, and gave up
on it. Better understanding of what the hybrid solver was doing (e.g.
not all boards were being solved recursively, so the speed difference
between my recursive implementation and solveri was not actually as
overwhelming as I thought) as well as some of the speed tips divulged
here (specifically | and & being faster than || and && which I used
extensively) has led me to believe that that may have been the wrong
decision.

Hopefully I will get some time over the weekend to determine whether
my jumptable approach could have been competitive. Curious to hear
whether anyone else worked along these lines and what your results
were.

Regards
Hannes

P.S. Now that my connectivity issues have been somewhat alleviated, I
think I will try my hand at tweaking in the next contest. If you
can't beat them join them ;-)

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: Nick Howe

Date: 24 May, 2007 09:31:54

Message: 199 of 221

Hannes Naudé wrote:
> My recursive solver is quite interesting in that it takes the
> concept
> of minimising recomputation to an extreme. It is actually built
> around the concept of a jumptable. Each potential jump maintains
> pointers to all (3 or less) jumps that may follow it as well as all
> (3 or less) jumps that may precede it. Each jump also maintains the
> best (in the greedy sense) hopchain that starts with that specific
> jump currently known and the greedy score of this hopchain. When a
> jump is chosen and executed, only the affected jumps need to be
> updated. It lends itself to extensive use of early termination
> criteria. It also potentially allows for easy identification of
> moves
> that allow two previously separate hopchains to be strung together.

This sounds clever! Even if it proves impractical, it gets points in
my book for innovation. I'd like to hear how it goes, if you try it.

I think recursion may be underused at times in these contests. In
the Gerrymander contest (my first), I had partly implemented a
snake-based solver that would recursively divide the map into
rectangular blocks and find the best solution independently on each
sub-block. It would therefore have been able utilise much more
complex snake patterns than any of the non-recursive solutions.
Unfortunately, I ran out of time to develop it -- but I still think
about going back and completing it, just to see how it would have
done.

Subject: MATLAB Programming Contest: May 9 - May 16, 2007

From: Ken Eaton

Date: 24 May, 2007 12:11:28

Message: 200 of 221

Hannes Naudé wrote:

> Hopefully I will get some time over the weekend to determine
> whether
> my jumptable approach could have been competitive. Curious to hear
> whether anyone else worked along these lines and what your results
> were.

I think there is some similarity between your jumptable approach and
some of the algorithms I tried towards the end. Here is the outline
of what I was doing:

1) Find all pegs that have at least one jump that they can make
(results in nMovable pegs).

2) Use a recursive algorithm to find for each of these pegs the
hopchain that gives the greatest payoff (this probably falls under
the "greedy" category of metrics).

3) Now there is a set of optimum jumps for each peg. Some will
interfere with each other (i.e. try to jump the same peg, etc.),
while some can be made independently of one another. I made a rather
complex algorithm that constructed what I called an interference
matrix (nMovable-by-nMovable) that used the score of each move. For
example, if nMovable=5 and the hopchain for peg 2 (score of 10)
interferes in any way with the hopchain for peg 3 (score of 5), then
row 2 of the interference matrix looks like:

intMatrix(2,:)=[0 10 -5 0 0];

and row 3 would be:

intMatrix(3,:)=[0 -10 5 0 0];

4) Once the interference matrix is constructed, I brute-force solve
for the subset of moves that maximize the score without interfering
with one another. I then simultaneously apply all these moves. I
figured applying them all at once might save time as opposed to
applying the one best move and then finding the other moves again in
a later iteration.

This algorithm was a fun experiment, but didn't do very well. The
score wasn't very good, and for certain cases could be very slow. For
instance, sometimes there could be 20 or more interfering moves and
my brute-force solver would either take a while or have to simply
discard some moves so my variables wouldn't exceed the maximum
allowed in MATLAB.

I never got a chance during the contest to refine this algorithm too
much. At the last minute I tried capping the recursion depth and the
number of simultaneous moves allowed. Some combinations performed
better than others, but still not great.

Ken

Subject: MATLAB Programming Contest: May 9 - May 16, 2007

From: Yi Cao

Date: 24 May, 2007 12:37:07

Message: 201 of 221

Anyone is able to see all messages of this thread? I can only see 50
most recent + the first messages.

Regards,
Yi

Subject: MATLAB Programming Contest: May 9 - May 16, 2007

From: us

Date: 24 May, 2007 12:45:46

Message: 202 of 221

Yi Cao:
<SNIP missing a few pegs...

all can be seen here at

 <http://groups.google.com/group/comp.soft-sys.matlab/browse_frm/thread/e6c7484702530330/b65f05aaec2df69d?hl=en#b65f05aaec2df69d>

us

Subject: MATLAB Programming Contest: May 9 - May 16, 2007

From: Yi Cao

Date: 24 May, 2007 13:07:19

Message: 203 of 221

us wrote:
>
>
> Yi Cao:
> <SNIP missing a few pegs...
>
> all can be seen here at
>
> <http://groups.google.com/group/comp.soft-sys.matlab/browse_frm/thread/e6c7484702530330/b65f05aaec2df69d?hl=en#b65f05aaec2df69d>
>
> us

Great! Thank you very much.

Yi

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: Yi Cao

Date: 25 May, 2007 11:06:30

Message: 204 of 221

srach wrote:
>
> I tested some entries that identified untouchable areas and resized
> the board accordingly ("pslct *"-entries). However, there was only
> a
> small gain in processing time due to resizing and that was eaten up
> by my algorithm. Thus, I abandoned the idea.

I have worked out the total untouchable weights for the sample suite
are about 3550 whilst for the actual suite they are 3500. That means
for best solutions, we still have about 8000 ~ 10000 of weights left
on the board and used more than 25000 of weights for the lifting
penalty. Indead, we are far from optimal.

I used subsoltweak to find those untochable areas. For those, who are
working on metric and need number of pegs information, I can send the
modified subsoltweak over via email.

Regards,
Yi

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: Steve Amphlett

Date: 25 May, 2007 12:03:41

Message: 205 of 221

I have never entered one of these contests and probably never will,
but...

1) Why not have a contest for the shortest (vectorised?) solution
that can get the right answer in a fixed time limit. It would need
rules to prevent massively obfuscated code (??).

2) Given that these threads generally outlive the contests by many
months, why not add another phase to the contests? For example, for
the week leading up to a new contest, contestants can submit their
much thought over attempts from the previous one.

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: Yi Cao

Date: 26 May, 2007 11:51:47

Message: 206 of 221

Hi, I got some new result about "optimally" cut of a hopchain. Here
is the idea:

Assume we have a hopchain removes weights: w1, w2, ..., wm using a
lifting weight w0. The value of the chain is s1 = w1 + w2 + ... + wm
- w0. If we stop the last jump (keep wm), then we can use wm to
remove w0 at next or a future move. Therefore, the total value of the
second option is s2 = (w1 + w2 + ... + wm-1 - w0) + (w0 - wm). The
difference of these two options: s1-s2=2*wm-w0; If we use a liearly
weighted multiobjective metric, s1'=s1 - R*w0 and s2' = s2 -R*w0 -
R*wm. In this case, s1' - s2' = s1 - s2 - R*wm = (2+R)*wm - w0. In
theory, if we cut a chain not at the last step but in the middle, we
have to count the tail contribution as well. But if we assume this
tail of chain more likely will be removed in a future hopchain, then
we can have the following algorithm:

At a stage of a hopchain (some point of a recursive function) check
if s1-s2<0 or s1'-s2'<0 then the chain will stop, i.e. the
recursive function returns without searching further.

I have tested this idea with subsol, subsoltweak, and Cat54. All work
extremely well. It can reduce score by 500 - 1000. But I could not
implement this idea with solveri.

Regards,
Yi

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: Sergey Yurgenson

Date: 26 May, 2007 20:13:05

Message: 207 of 221

Yi Cao wrote:
>
>
> Hi, I got some new result about "optimally" cut of a hopchain. Here
> is the idea:
>
> Assume we have a hopchain removes weights: w1, w2, ..., wm using a
> lifting weight w0. The value of the chain is s1 = w1 + w2 + ... +
> wm
> - w0. If we stop the last jump (keep wm), then we can use wm to
> remove w0 at next or a future move. Therefore, the total value of
> the
> second option is s2 = (w1 + w2 + ... + wm-1 - w0) + (w0 - wm). The
> difference of these two options: s1-s2=2*wm-w0; If we use a liearly
> weighted multiobjective metric, s1'=s1 - R*w0 and s2' = s2 -R*w0 -
> R*wm. In this case, s1' - s2' = s1 - s2 - R*wm = (2+R)*wm - w0. In
> theory, if we cut a chain not at the last step but in the middle,
> we
> have to count the tail contribution as well. But if we assume this
> tail of chain more likely will be removed in a future hopchain,
> then
> we can have the following algorithm:
>
> At a stage of a hopchain (some point of a recursive function) check
> if s1-s2<0 or s1'-s2'<0 then the chain will stop, i.e. the
> recursive function returns without searching further.
>
> I have tested this idea with subsol, subsoltweak, and Cat54. All
> work
> extremely well. It can reduce score by 500 - 1000. But I could not
> implement this idea with solveri.
>
> Regards,
> Yi
  

This is brilliant!!!
It is very elegant and undisputable.

I run some modifications of recursive solver.

In first version I replaced h=find(b(t)==0&b(jj)>0); by
h=find(b(t)==0&b(jj)>0&b(jj)*(2+0.7)>w0);
score went down from 41670 to 41163

then instead of modifying that line I have modified
inside recursive function
if B>G && (B-O)>(w0-b(jj(k))*1.7)

That way it took into account tail of chain

Score now is 40929.

Best wishes,
Sergey

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: Sergey Yurgenson

Date: 27 May, 2007 07:51:33

Message: 208 of 221

Sergey Yurgenson wrote:
>
>
> Yi Cao wrote:
>>
>>
>> Hi, I got some new result about "optimally" cut of a hopchain.
> Here
>> is the idea:
>>
>> Assume we have a hopchain removes weights: w1, w2, ..., wm
using
> a
>> lifting weight w0. The value of the chain is s1 = w1 + w2 + ...
+
>> wm
>> - w0. If we stop the last jump (keep wm), then we can use wm to
>> remove w0 at next or a future move. Therefore, the total value
of
>> the
>> second option is s2 = (w1 + w2 + ... + wm-1 - w0) + (w0 - wm).
> The
>> difference of these two options: s1-s2=2*wm-w0; If we use a
> liearly
>> weighted multiobjective metric, s1'=s1 - R*w0 and s2' = s2
-R*w0
> -
>> R*wm. In this case, s1' - s2' = s1 - s2 - R*wm = (2+R)*wm - w0.
> In
>> theory, if we cut a chain not at the last step but in the
middle,
>> we
>> have to count the tail contribution as well. But if we assume
> this
>> tail of chain more likely will be removed in a future hopchain,
>> then
>> we can have the following algorithm:
>>
>> At a stage of a hopchain (some point of a recursive function)
> check
>> if s1-s2<0 or s1'-s2'<0 then the chain will stop, i.e.
the
>> recursive function returns without searching further.
>>
>> I have tested this idea with subsol, subsoltweak, and Cat54.
All
>> work
>> extremely well. It can reduce score by 500 - 1000. But I could
> not
>> implement this idea with solveri.
>>
>> Regards,
>> Yi
>
>
> This is brilliant!!!
> It is very elegant and undisputable.
>
> I run some modifications of recursive solver.
>
> In first version I replaced h=find(b(t)==0&b(jj)>0); by
> h=find(b(t)==0&b(jj)>0&b(jj)*(2+0.7)>w0);
> score went down from 41670 to 41163
>
> then instead of modifying that line I have modified
> inside recursive function
> if B>G && (B-O)>(w0-b(jj(k))*1.7)
>
> That way it took into account tail of chain
>
> Score now is 40929.
>
> Best wishes,
> Sergey
  

I said it is “undisputable”. Now I am going to dispute it :)
Logic works if current hop (last before cut) and next one are
collinear. If hop direction changes then we may not be able to use
peg wn to remove w0.

Sergey

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: Yi Cao

Date: 27 May, 2007 10:11:45

Message: 209 of 221

Sergey Yurgenson wrote:
>
> I said it is “undisputable”. Now I am going to dispute it :)
> Logic works if current hop (last before cut) and next one are
> collinear. If hop direction changes then we may not be able to use
> peg wn to remove w0.
>
> Sergey

Yes, you are right! Therefore, we have to check if using wn to remove
w0 is valid. In Cat54, it can be checked with ~b(s-jj) condition.

Another thing, at a check point, if there are multiple chain options
(length(h)>1), the best tail value is s0=(B-O). But if chain is
cut here, the best jump to remove w0 will be the minimum weight,
w_min of all valid moves to remove w0. The condition to cut te chain
then recomes (1+R)*w_min + s0 < w0.

Regards,
Yi

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: Sergey Yurgenson

Date: 27 May, 2007 16:01:58

Message: 210 of 221

Yi Cao wrote:
>
>
>
> Yes, you are right! Therefore, we have to check if using wn to
> remove
> w0 is valid. In Cat54, it can be checked with ~b(s-jj) condition.
>
> Another thing, at a check point, if there are multiple chain
> options
> (length(h)>1), the best tail value is s0=(B-O). But if chain is
> cut here, the best jump to remove w0 will be the minimum weight,
> w_min of all valid moves to remove w0. The condition to cut te
> chain
> then recomes (1+R)*w_min + s0 < w0.
>
> Regards,
> Yi
  
Yes. I agree.
 Unfortunately all my attempts to implement (1+R)*w_min + s0 < w0
result in final score worst than for simple if B>G &&
(B-O)>(w0-b(jj(k))*1.7)

Sergey

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: Yi Cao

Date: 27 May, 2007 17:57:55

Message: 211 of 221

Sergey Yurgenson wrote:
>
> Yes. I agree.
> Unfortunately all my attempts to implement (1+R)*w_min + s0 <
> w0
> result in final score worst than for simple if B>G &&
> (B-O)>(w0-b(jj(k))*1.7)
>
> Sergey
It could be just because a local optimum not necessary to be the
global optimum. Even in a case using wn to remove w0 may not be
valid, but more likely it would become valid in future. Hence if wn
is too small, it is still btter to cut it from the chain.

Regards,
Yi

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: Sergey Yurgenson

Date: 27 May, 2007 18:33:14

Message: 212 of 221

Yi Cao wrote:
>
>
> Sergey Yurgenson wrote:
>>
>> Yes. I agree.
>> Unfortunately all my attempts to implement (1+R)*w_min + s0
<
>> w0
>> result in final score worst than for simple if B>G &&
>> (B-O)>(w0-b(jj(k))*1.7)
>>
>> Sergey
> It could be just because a local optimum not necessary to be the
> global optimum. Even in a case using wn to remove w0 may not be
> valid, but more likely it would become valid in future. Hence if wn
> is too small, it is still btter to cut it from the chain.
>
> Regards,
> Yi
  

Of course I do understand that our metrics are local. It is just
little bit frustrating that clearly more accurate local metric
produces worse global result. (For the same reason winning strategy
during competition was to repeat the same solution several times with
“random” modification of parameters. And some “random” were better
than other)
In any case, the discussion was very interesting and fruitful.

Best wishes,
Sergey

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: Yi Cao

Date: 29 May, 2007 19:05:34

Message: 213 of 221

Sergey Yurgenson wrote:
> In any case, the discussion was very interesting and fruitful.
>

Based on discussion in the newsgroup, I coded a new solver based on
the winning code. It covers most ideas discussed in the newgroup:
ratio and linear multiobjective metrics, forward prediction, early
cut of a chain, etc. It is faster (30sec on my PC) and also drives
the results down t0 36600 without help from solveri. All random stuff
have been removed. With this solver, we should be able to get results
below 36000 within 3 min. The new function, depsol is able to become
recursive, hence gives more room to play with. This solver can be
download from File Exchange:
 <http://www.mathworks.com/matlabcentral/fileexchange/loadFile.do?objectId=15144&objectType=file>

Are we able to reduce results below 35000?

Regards,
Yi

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: Markus

Date: 30 May, 2007 03:03:05

Message: 214 of 221

Hi Yi!

I have taken your function and put it into my optimizer to search for
some better parameters. I'll let you know if there is something
coming out.

Regards
Markus

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: Yi Cao

Date: 31 May, 2007 03:09:32

Message: 215 of 221

Markus wrote:
>
>
> Hi Yi!
>
> I have taken your function and put it into my optimizer to search
> for
> some better parameters. I'll let you know if there is something
> coming out.
>
> Regards
> Markus

Hi Markus,

Just curious, what is your optimizer?

Regards
Yi

Subject: Optimizer

From: Markus

Date: 31 May, 2007 05:15:41

Message: 216 of 221

> Just curious, what is your optimizer?

Well, it is a Differential Evolution algorithm. I don't use this
algorithm for a special reason, except that it is easy to implement
and does not require too many parameters. However, as the possible
parameter space is very large and the function evaluations take quite
long, it is more or less only a random search in the parameter space.
I guess the power of the Differential Evolution algorithm will show
up only after a large number of iterations, which will never be
finished before the next contest is online...

Markus

Subject: Optimization

From: Markus

Date: 4 Jun, 2007 03:42:39

Message: 217 of 221

Just for the case that someone is interested in my optimization
result: Currently I am at a score of 36085.10607.

Regards
Markus

Subject: Optimization

From: Yi Cao

Date: 5 Jun, 2007 04:05:56

Message: 218 of 221

Markus wrote:
>
>
> Just for the case that someone is interested in my optimization
> result: Currently I am at a score of 36085.10607.
>
> Regards
> Markus

What parameters have you got? Do you increase depth so that CPU time
increases? I have a recursive version to look ahead for more than one
levels, which results 401 for the weighted english board problem. It
is the first computer code which is able to beat Lucio's solution
(407). With this code, I can get a score at 35500 within 3 minutes.
If anyone is interested in this code, I can send through email or
post to File Exchange.

Regards,
Yi

Subject: Optimization

From: Markus

Date: 5 Jun, 2007 04:23:04

Message: 219 of 221

Well, here are the parameters and the modified code. But it seems to
be far away from your new solution.

function [moves,score,v0] = fastsol(board)

param.n1 = 3;
param.n2 = 4;
param.R11 = 0.115;
param.R12 = 0.185;
param.R13 = 0.245;
param.R21 = 0.81;
param.R22 = 0.815;
param.R23 = 0.69;
param.R24 = 0.42;
param.dd1 = 1.32;
param.dd2 = 1.45;
param.dd3 = 1.67;
param.dd4 = 2.48;
param.dep12 = 16;
param.dep13 = 12;
param.dep22 = 6;
param.dep23 = 10;
param.dep24 = 19;

...

R = [param.R11 param.R12 param.R13];
dep = [0 param.dep12 param.dep13];
score=-Inf;
for k=1:param.n1,

...

R = [param.R21 param.R22 param.R23 param.R24];
dd = [param.dd1 param.dd2 param.dd3 param.dd4];
dep = [0 param.dep22 param.dep23 param.dep24];
for k=1:param.n2

...

Markus

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: MikeR

Date: 5 Jun, 2007 14:02:37

Message: 220 of 221

I've taken some time to review Yi's improvements on the final code.

Through some minor parameter variation I have a few results, and
observations:

Variables which I modified:
R=[0.95 .93 0.91 0.88 .78 .76];
dd=1:.3:5;
dep=round(pegCount*.15)-1:1:2*pegCount;

The actual number of iterations that SubSol was called and resulting
score:
% for k=1:4 % Number of Iterations Here
% [newMoves,newScore,newV0] = subsol( ...

1: 37011.6347 @ 54 Seconds
2: 36451.5374 @ 89 Seconds
3: 36114.4936 @ 120 Seconds
4: 35972.9701 @ 150 Seconds

I have been looking at scores per boards and playing with a variable
depth per board, and/or a variable number of subSol iterations per
board.

The above variables get a score of 391.2962 for the first board of
the sample test-suite, which I believe is the english Peg Solitaire.

I will probably continue to play with this, while I slowly forget
about my own tree solver which can't compete with the speed of this
code.

- MikeR

Subject: MATLAB Programming Contest: May 9 - May 16, 20

From: Yi Cao

Date: 7 Jun, 2007 11:13:35

Message: 221 of 221

Since this group still keeps interest in playing the game, I submit
my recursive code to File Exchange:
 <http://www.mathworks.com/matlabcentral/fileexchange/loadFile.do?objectId=15213&objectType=file>
Curretly, it takes about 143 seconds to get results at 35466.1408

Hopefully, someone can tune parameters to get it down below 35000
within 3 minutes.

Regards,
Yi

Tags for this Thread

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us