# 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 . 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:   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: 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" 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 Date: 10 May, 2007 18:28:07 Message: 38 of 221 In article , B 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" wrote in message news:f1vo7n\$cph\$1@canopus.cc.umanitoba.ca... > In article , > B 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" wrote in message > news:f1vo7n\$cph\$1@canopus.cc.umanitoba.ca... >> In article , >> B 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 . > 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 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: 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: > > 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 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: 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: 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: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 . > 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" 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: 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: 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: 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: > > all can be seen here at > > > > 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:   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:   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

### Everyone's Tags:

contest(2)

Separated by commas
Ex.: root locus, bode

### 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.