The Nineteenth Byte

trichoplax

12:00 AM

You could play it with humans but it would take months or years for a tournament

feersum

like Risk?

Martin Büttner

lol

trichoplax

yeah lol Risk is the perfect counterexample - it takes months to play and humans still play it (although most not more than once...)

kuroi neko

I don't use any history yet. It's just there to keep contenders guessing :)

feersum

I tried to play it sometimes but never finished

Martin Büttner

12:01 AM

Risk is amazing :)

trichoplax

My idea is much much simpler than Risk but will take much longer due to being played on a large grid

@MartinBüttner Does this opinion mean you have played Risk on a computer and not had to count up the number of pieces in different regions every single move...?

Martin Büttner

no, I've only played it on a board

trichoplax

You clearly have a lot of patience

Martin Büttner

:D

feersum

It also doesn't work if there are any living beings in your house...someone will step on it eventually

Martin Büttner

12:04 AM

it's not like you can't remember how many units you got last round and just check what changed.

@feersum we have a table.

trichoplax

@MartinBüttner lol yeah I may not have been playing it as efficiently as you

feersum

still doesn't work with cats ;)

or someone will bump into the table

trichoplax

Someone needs to invent magnetic wall Risk

(although people will still brush against it)

Sp3000

@Geobits Does confusion still make you punch yourself if you provide an invalid command? (i.e. I want my Codemon to not do anything that turn)

Martin Büttner

@trichoplax I've actually got this 2210 (or something) A.D. edition... you can just play classic risk with it, but it also has its own crazy ruleset... the rule are super interesting, but I haven't yet figured out a way to play that unless you're with really hardcore gamers, because there's so much strategy that the game is basically reduce to 5 reaaaally long rounds.

one thing that's really interesting is that you can bid for turn order (each round) with some resource you have

kuroi neko

12:07 AM

I was an avid Risk player when I was a kid. I don't remember counting anything though. Just strive to get connected regions and bunch armies at the frontiers. Or have Risk rules evolved since the last century?

trichoplax

There goes my argument that some games are too drawn out for humans...

I think Risk always had new troops allocated based on existing numbers

(The version I played certainly wasn't from this century)

Did anyone ever play a card&board game called S.P.I.Vs?

That took a long time...

Pyraminx

hi people

kuroi neko

@MartinBüttner turning Risk into a wargame sounds like a strange idea to me. There are plenty of dedicated such wargames, while the main appeal of Risk is its simplicity IMHO.

trichoplax

@Pyraminx hi

Pyraminx

what is up

no one ever chats on the sites I go to

Martin Büttner

12:15 AM

this chat is usually reasonably busy (at least at this time of day)

Sp3000

When you guys aren't here it's half-half between dead quiet and occasional chatting though

Pyraminx

the last message is always more than 2 hours ago on the sites i like

trichoplax

@Pyraminx Here it will depend on your time zone

Pyraminx

I'm in UTC -8:00

kuroi neko

Btw my rats are at 6000+ after 250 runs or so. Maybe it's just a fluke, but I keep my fingers crossed.

trichoplax

12:19 AM

daytime and late evening in the UK and US tend to have people around. There are people around at other times too but not so many

@kuroineko I don't know where you get your motivation when you're already at the top :)

Sp3000

"Because it's an awesome question"

kuroi neko

except Frenchmen with insomnia :). As for motivation, well it's just beating the problem. So much the better if I come on top, but that's secondary.

Pyraminx

It's funny because no one actually talks about anything related to the site of the chat room. Everyone gets sidetracked to somewhere else.

trichoplax

Here we're about 50/50 on topic and off topic, which I think is a good balance

kuroi neko

Freedom, freedom, freeedooom, yeah

Pyraminx

12:23 AM

bye guys i have to go

trichoplax

Bye for now :)

Pyraminx

soon, not now

ok, now.

kuroi neko

bye then

Pyraminx

BYE!

kuroi neko

About the GA challenge, I dream of someone posting a new answer that would mop the floor with my rats, so that I could learn or understand something new.

trichoplax

12:30 AM

Nathan has a new GA challenge in the sandbox that I'm looking forward to seeing posted

PhiNotPi

@Geobits I'm running a mini Codemon tournament. How do I reduce the time limit?

kuroi neko

@trichoplax I was in the discussion that lead to this (sandboxed) challenge, but I'm not convinced it could work.

PhiNotPi

nevermind I found it.

trichoplax

12:47 AM

@kuroineko do you see a way of changing it to make it work?

kuroi neko

If I did, I would have posted something. I have thought about it a bit, but came up blank.

Hi

hi there

Hi

I have another tiny javaScript question.

I have an html5 canvas that's detecting mouseUp events; if I drag the cursor off the canvas and then release the mouse button, it doesn't trigger

so I gave the HTML tag an id, "parent", and put in a line: parent.onmouseup = XZmouseUp;

is that bad form?

trichoplax

12:51 AM

I have zero JS knowledge

kuroi neko

have you tried adding an event listener to your document body?

that would catch the mouse unless you move it outside the browser's display area

Eric Tressler

no. I only need to detect mouseUp events outside of the canvas. What I did works, I just want to know if it's bad style somehow

kuroi neko

lol @feersum

Doorknob

of course

Eric Tressler

prospective employers see my website, i'd rather not have it filled with horrible code any more than I need to

feersum

12:55 AM

if you can't take delight in bad style, you do not belong in codegolf!

trichoplax

Do prospective employers see that you use PPCG?

Eric Tressler

i guess they could, i use my real name on stackexchange

feersum

so you are already doomed, might as well :)

Eric Tressler

i don't see how being on here is in any way negative :|

trichoplax

I was just joking because some people frown on golf

Eric Tressler

12:57 AM

really?

kuroi neko

Well I'm unemployed, and my last job was case worker in child protection, so I can't help you with employer-seducing tips. Your concern comforts me in my decision to leave the silly world of software industry, though.

trichoplax

Would you recommend against working in programming?

Eric Tressler

anyway, not a big deal, i just felt weird putting <html id="parent">

Doorknob

Wait, why do you need to give the html tag an ID?

scrolls up

kuroi neko

@EricTressler I would certainly not name it "parent", regardless of what an employer might think of it

Doorknob

12:59 AM

Oh, couldn't you just do document.documentElement.onmouseup = XZmouseUp?

Eric Tressler

does that work? let me try

yep, thanks

Geobits

@Sp3000 Choosing a no-op does not preempt confusion. You still punch yourself :)

trichoplax

Does confusion have any affect on swapping?

PhiNotPi

Right now, I have a competition of about 20 completely random bots going on.

Geobits

No, you can still swap as normal.

kuroi neko

1:02 AM

@trichoplax I have no authority to do any kind of recomendation, really. I was a real-time embedded software programmer until the NASDAQ collapse turned French industrial software business into a quagmire, and then I quit. Something tells me things have not changed for the better since then, so I'd rather live off state charity than go back there.

PhiNotPi

(maybe a confused Codemon should accidentally swap with the other team)

trichoplax

@kuroineko I see. I'm in the UK so not the same but I'm interested in opinions as I'm wondering about whether to learn to be a programmer of some sort

Geobits

In my experience it beats working on an aircraft ramp. I don't know what you're comparing it to, though ;)

trichoplax

lol

kuroi neko

@trichoplax well after having been a project manager for 3 or 4 years and a consultant for a couple more, the only thing I can say is that it's not a job for me. Too many asses to kick or lick, too many lies to tell for my taste. Trouble with French software industry is, you can't stay a mere programmer after you turned 35 or so. And being a manager and/or well-paid liar err... I mean consultant is an entirely different job.

Eric Tressler

1:10 AM

I quit my job at a research lab when it turned into full-time programming of stuff I didn't care about

trichoplax

@kuroineko I've heard similar from others - "career progression" means moving away from what you enjoy. I'd be happy staying with programming for less money - I'm not looking for a lot

kuroi neko

well trouble is, when you gather experience people won't hire you as a mere programmer anymore. When I asked to remain a simple programmer/designer, people looked at me with a kind of pity, as if I was mildly retarded or something.

trichoplax

People already look at me like that so perhaps I can work around it :)

@EricTressler Are you still interested in working in programming? Did it just put you off that one job or programming as a job altogether?

kuroi neko

hahaha that would be nice. However, from my experience, you'll have to look hard for that kind of humor in software industry. The dominant ideology is rather a kind of machismo that leaves precious little room for dreamers or losers.

Eric Tressler

i'd like a job that has some design and analysis components as well

for 3 years, that job was pretty good, but the last year I was there, it was almost entirely coding, and it stressed me out too much

implementing poorly-described algorithms in literature

trichoplax

1:16 AM

Yes I like the idea of a range of different tasks

kuroi neko

my idea was to pick a domain where experience makes you valuable enough to force your hierarchy to give you some freedom.

The trouble in domains like web design is that originality is intrinsically bad. What makes money is to copy the last whim of fashion in the quickest and dirtiest way.

trichoplax

Thanks for the insight. I certainly want to be able to have originality, so I'll bear that in mind

I'm going to sleep now. Good night all

kuroi neko

good night, young padawan

trichoplax

lol :)

Geobits

2:53 AM

Meh. I found a good strategy that gets about 50/50 with Kids and Campers, only to have its scored tanked by those damned metapods.

PhiNotPi

I'm still running a random simulation.

10 rounds, 50 random bots.

To see what happens.

Geobits

Hmm. I don't know if 10 rounds is enough to overcome the inherent variance, but it'll be interesting to see what it comes up with.

PhiNotPi

The goal being to determine what move/type combinations are inherently better.

Each move/type combination could occur in multiple bots.

Geobits

How are you deciding which move to use when? Tossing dice?

PhiNotPi

Each single bot's score will be pretty random, I guess, but a trend such as "teams with poison score higher" should be possible to find.

Throwing dice as of right now.

Geobits

2:57 AM

Stats evened out or random?

PhiNotPi

even stats

The tournament just finished.

5 seconds ago

Geobits

Now take the winner and run 50 slight variances on him :D

Against the current field

PhiNotPi

16		4x12x1x5X2x12x13x14X2x0x7x1
16		4x9x13x3X0x12x8x1X1x8x6x7
15		0x12x7x6X2x4x12x7X2x4x7x5
14		3x4x7x6X1x10x9x6X2x4x7x6
14		1x5x9x6X1x9x5x3X1x14x7x4
14		1x8x13x7X1x5x3x10X4x3x0x10
14		3x0x1x8X3x7x6x11X2x13x4x14
13		0x1x6x13X0x13x6x2X0x10x2x13
13		4x10x3x1X1x7x10x4X1x3x10x7
13		3x5x9x3X3x8x5x3X2x13x14x12
13		4x1x2x14X4x1x9x12X4x5x13x4
13		2x7x12x5X2x7x13x14X0x11x1x10
12		3x3x11x1X1x7x4x12X3x2x1x0
12		2x13x7x14X4x3x0x9X0x1x2x0
12		2x0x14x2X1x9x5x12X0x12x2x7
12		4x2x13x5X1x8x9x13X2x2x6x8
12		3x3x8x6X4x12x0x10X2x8x7x5

Geobits

That's typeXmoveXmoveXmove*3, right?

PhiNotPi

yes

uppercase Xs split the numbers into three groups.

Geobits

3:01 AM

Right

I don't see much of a pattern, unfortunately. The most common among the top 3 looks like 12(Vine), for instance, and that doesn't make much sense at all :)

PhiNotPi

I'm worried that type differences play a large part.

If one type is more common, than any bot with move strong against that type will win more often.

Geobits

True. The answer to that is 5000 bots instead :P

(with 50 rounds)

PhiNotPi

I'll set something up to run overnight.

Is there a detailed log file created?

That shows who beat whom?

Geobits

If you want just the match results, run java Tournament 2, and to pipe it to a file, try java Tournament 2 > results.txt

That'll get rid of the turn-by-turn but still show "A beat B" and the running scores for each round.

PhiNotPi

So, I'm going to start a second random tournament.

I've gotten the Tournament 2 to work.

Geobits

3:10 AM

Well, redirecting it to a file should work. I'm on Ubuntu, but I believe it works the same on Windows if you're running that.

PhiNotPi

What's the easiest way to check to see if a move has used all of its uses?

Geobits

Those are fields 8/9/10 (0-indexed) in each member's string.

It'll be 0 for "none left", positive for "x left", and negative for "unlimited".

If you pin one move to whatever their type's unlimited pure-attack move is, it might help mitigate your typing issues. With pure random, there's a high chance of not having any good attack (for that type).

Then the other two as random.

PhiNotPi

3:25 AM

okay, I'm giving each Codemon their type's primary attack and setting it to use that attack if the random move has no uses.

Geobits

Sounds a bit better than pure dice roll. Hopefully something clearer will emerge overnight ;)

PhiNotPi

how many bots and rounds?

Geobits

A billion and two thousand :P

No really, I don't know how long your 10/50 took.

PhiNotPi

1.5 hours.

I think.

way too long

Geobits

Damn, really?

PhiNotPi

3:28 AM

10*50 is 250 battles.

Geobits

Oh, that actually makes sense.... if they run out of moves they'll just sit staring at each other for 1000 turns :D

Instead of the more normal 20 or so turns a battle takes.

With your backup attack, it shouldn't take nearly as long.

I've been doing 100*6 (300 battles) in about 5-6 minutes.

Though they're more targeted.

PhiNotPi

I wonder if my IDE is the problem.

As part of AP CompSci, I use an IDE called BlueJ.

Geobits

I dunno. I'm more inclined to think you're hitting the turn limit with a few bots. No IDE should slow it down 20x like that.

Unless you're running it in some crazy debug mode, I guess.

PhiNotPi

I reduced the turn limit to 50, in that tournament.

It's not that.

It's just slow.

Geobits

Ah. Weird then.

Well, if you want it to run overnight assuming the same speed, you need about five times as many battles. 25 rounds *100 bots would do it.

If you suspect your IDE, you could try a short one on the command line to see if that helps. I'm out for now though, good luck!

PhiNotPi

3:38 AM

bye!

a little over 100 bots and 25 rounds has started

Nathan Merrill

4:47 AM

Hey, I just finished the controller, and I'm looking to post this question: meta.codegolf.stackexchange.com/a/2571/20198

Can I get any last minute feedback?

Sp3000

Just checking - if someone sticks to a deterministic strategy and moves a bot away, leaving an open spot below me

Then I get to name them and they have to move back to the same spot?

Nathan Merrill

yes

Sp3000

Interesting...

globby

@Sp3000 Do you know anything about machine learning?

Sp3000

Er... little bit? How come?

globby

5:08 AM

@Sp3000 From earlier today:

Question for anyone familiar with machine learning or this type of problem, if I was making a program that deals with natural language and the outcome is determined by what the user is asking (Siri-like), what would be the most effective and least resource intensive machine learning algorithm to implement to score the inputs probabilistically?

I was thinking something like Multinomial Logistic Regression, Naive Bayes Classifiers or Markov (possibly hidden) models

Sp3000

What do you mean by scoring the inputs?

(also when in doubt, pulling up a machine learning library and throwing everything at it to see what's best is an option)

globby

^ Did that in mathematica and it used "Markov" which I assume is a Markov chain

and say the input was "What's the time in Phoenix, Arizona?"

There would be some list of probabilities or scores

referring to how certain the algorithm is that it is asking for the function

like maybe it returns [1.8483 -> time, .235 -> date, .004 -> maps]

or something

I've got it working currently but it's using a VERY naive approach

Sp3000

Markov doesn't sound too bad, it'd be a bit like this

Do you have any training data? Like example inputs and correct responses

globby

Are you asking for a yes or no, or for me to send example data?

The answer is yes

Sp3000

Just a yes/no

globby

5:15 AM

Then yes

(Well, it would be yes either way XD )

Sp3000

Ahaha k :P

globby

In mathematica, I used the classify function and everything works well but I want to limit it to one programming language to reduce execution time and computational steps

and I don't want to re-make it in mathematica

Sp3000

Well in my limited machine learning knowledge I know there's tf-idf which can help you find which words are more significant than others

So something like "What" wouldn't score very well with that

globby

mm I see, but again that would just score the words

Sp3000

I thought you wanted to score the words? Or did you mean something else?

globby

5:21 AM

No like

Sorry, I didn't explain it well

Basically, it should return the correct function. Like, if it is inferred that the user is asking the time, we should execute the time function. If they are asking for directions, then the maps function, etc.

So the classes for the model would be those functions

but it has to take the string input, and from that, infer what function the user is trying to call from the natural language input

Sp3000

How did Naive Bayes go? Out of curiosity (I don't know much about the Multinomial one)

(if I remember right that one's not very resource intensive)

globby

Like how does it work or how did testing go? If you're talking about testing, then I haven't specifically tested it yet, just been looking around trying to find something suited before I spend the time implementing it

Otherwise, en.wikipedia.org/wiki/Naive_Bayes_classifier

Sp3000

I like how you automatically cover both cases of my ambiguous questions :P I meant how did testing go

But let's see, hm...

globby

I was just wondering if that was getting annoying or not x)

Sp3000

Nope, it's very useful :)

globby

5:31 AM

Alrighty

Sp3000

Well if it helps, the most machine learning-y thing I've done is an assignment which was a basic spam filter, in which we removed stop words (like "is", "a", etc.) from the documents, used tf-idf to score each word then applied Naive Bayes to that

globby

Which is a little more than I've done

Sp3000

I also tried some Porter stemming, but that one seems to be okay sometimes and not as good at other times

globby

I have a basic understanding of the concepts and an interest but almost no experience with it

I was thinking of creating my own function where each function has certain keyword:offset pairs associated with it, and then mapping the words in the input over that, modifying the score for each function by that offset each time

But I would think that machine learning would have a better success rate and be less of a pain to upkeep

Sp3000

Probably, if it's natural language like that

globby

5:44 AM

Why does NLP have to be so difficult XD

Sp3000

5:59 AM

I wanted to do it this semester but they cancelled it this year :(

globby

Aw damn :c It's a really fun topic

Optimizer

@MartinBüttner you will like this rednuht.org/genetic_walkers

2

Sp3000

That reminds me...

@MartinBüttner You will like this youtube.com/watch?v=8vzTCC-jbwM (and half of this guy's channel)

Optimizer

@MartinBüttner no, you will like my link better

Sp3000

I do like your link though :P Watching people fall

Optimizer

6:05 AM

@Sp3000 wait for your "Martin you will like <link>" day

@Sp3000 sooo negative. Its all about people trying to rise up as the generations go.

Sp3000

I'm watching the cars one now and they're all getting stuck in the same ditch

Peter Taylor

8:00 AM

@trichoplax My first job was creating a computer version of a play-by-mail strategy war game. When I joined the company, the rule book was about 200 pages long. By the time I left, the requests for clarifications from the developers had made it grow to 300 pages. I'm not sure how long the original mail version took, but I would guess that a game lasted several years.

Lembik

9:18 AM

@Sp3000 that's great!

although not a very good advert for genetic programming :)

but then nothing is...

Sp3000

Well that guy's vids were actually what got me into genetic programming, so...

whistles

Lembik

@Sp3000 oh! I thought it was established 15 years ago that GAs were basically pointless

@Sp3000 at best they implement stochastic hill climbing

Sp3000

Oh? For something that's useless there sure are a lot of papers still coming out on it...

Lembik

@Sp3000 right..like neural networks pre 1995 :)

@Sp3000 I mean stochastic hill climbing is useful but rarely the best thing to do

Sp3000

(I just like them cos they're fun)

(To watch)

Lembik

9:23 AM

@Sp3000 I love anything with graphics too :)

Sp3000

Not even that - I did a genetic Hello World once just for the sake of seeing the chars change

Lembik

:)

Martin Büttner

meh, I wish GolfScript didn't print the trailing newline

then I could do CH's challenge in 4

Sp3000

Ah :/

Funny how xnor took advantage of that in Python

Martin Büttner

at least I have beaten Optimizer for once :P

@Optimizer neat

Optimizer

9:32 AM

@MartinBüttner not like u have not before

but that is clever

Martin Büttner

if GolfScript didn't print the trailing newline (or CJam treated the empty stack as q), I'd have ..n+ (or __S+ in CJam)

Optimizer

I still do not understand the TECO logic

how it works. .

Sp3000

I wonder if you can use o somehow to take advantage of the fact that squares are the sum of two triangular numbers

Martin Büttner

@Sp3000 haha, that's pretty amazing too

@Optimizer it's basically the same thing as mine, except that L is implicit

Optimizer

or sum of n odd digits

@MartinBüttner isn't he doing n^2 + 1 + n^2 then ?

Martin Büttner

9:37 AM

no

Optimizer

V -> current buffer -> n^2

Martin Büttner

in JS you'd have an implicity s = "" and then his code would be console.log(s); s+= "1" ; console.log(s); (ignore the fact that log prints newlines)

Optimizer

1 -> 1 -> n^2 + 1

V -> current buffer = n^2 + 1

Martin Büttner

no, V only has N characters

Optimizer

how does V gets updated ?

Martin Büttner

9:39 AM

with 1\

actually V isn't updated at all... from what I understand it's just a command with an implicit source for printing

Optimizer

so if V\1V prints 1 , V\1VV prints 11 , V\1VV\1 prints 111 and V\1VV\1V prints 111111 no ?

Martin Büttner

no

wait

V1\VV1\ still prints 11 (because there's no additional V)

Sp3000

If only CJam had infinite zeroes at the bottom like Prelude...

Martin Büttner

and then V1\VV1\V prints 1111 (because now the buffer contains two 1s)

@Sp3000 well, there's an active feature request to implicitly perform q if you try to operate on an empty stack

that would have helped, too

Optimizer

@MartinBüttner because its VV instead of V ?

Martin Büttner

9:45 AM

I really don't understand where you're stuck on this :D ... if JavaScript didn't help here is the CJam translation: V -> Lo ... 1\ -> L'1+:L;

Optimizer

I am stuck because V prints the line content as is. I am not sure how you are interpreting it that its soo clear.

Martin Büttner

"the line in the text buffer". (i.e. L in my CJam translation) not the line of the source code

Optimizer

of course. let me again show you the text buffer after each step for N = 2

Martin Büttner

dude, just copy the CJam snippets together and put some eds in between

(that is, LoL'1+:L;Lo)

ohhhhhhhhhhhh

Optimizer

thats what you converted

Martin Büttner

9:50 AM

are you taking "the text buffer" to mean STDOUT?

Optimizer

by ur understanding

V prints to STDOUT, right ?

\1 does not add to STDOUT ?

Martin Büttner

I'm pretty sure "the text buffer" is some piece of memory and "printing" goes to STDOUT... so V doesn't modify "the text buffer" at all

@Optimizer I'm pretty sure it doesn't, because how would V read from its own STDOUT?

Optimizer

its not at all clear.

@MartinBüttner that is what I understood

feersum

Did you guys have a question about the TECO?

Martin Büttner

Optimizer does :D

Optimizer

9:52 AM

@feersum it can need some explanation

at least to me its totally unclear

feersum

the text buffer is basically a string

V prints it

\1 appends "1" to it

Optimizer

ok

@feersum so no extra newline as such ?

feersum

There are no auto-newlines anywhere

only the = command would put a newline if it is not in the string

Optimizer

@MartinBüttner just like in CJam. This is the equivalent I was thinking : _'1]s_ if _ worked with empty stack.

Martin Büttner

well that's not really reading STDOUT though

if _ worked with the empty stack you could do 4 bytes though

feersum

10:10 AM

I wonder who will be the first to try posting the 1-byte HQ9+ solution?

Martin Büttner

oh

well that would hopefully be downvoted into oblivion

also, it's arguable that Q reads the source code

feersum

Yes, I assumed it's invalid because of that

Peter Taylor

10:34 AM

@Lembik What general optimisation techniques don't implement stochastic hill climbing?

Optimizer

Lembik

@PeterTaylor I can only name simulated annealing and genetic programming

Sp3000

10:56 AM

And Great Deluge, which has a pretty cool name

Lembik

@Sp3000 true :)

Peter Taylor

@Lembik I can only name those and actual hill climbing. But simulated annealing is definitely stochastic hill climbing. Well, I suppose that if all of the known options are "rarely the best thing to do", that would explain why optimisation is so hard ;P

Lembik

@PeterTaylor yes.. :) I think my argument would be that stochastic hill climbing in its simplest form is easier to implement and understand than GA which introduces spurious vocab and hope that some magic might happen

basically it is stochastic hill climbing + hocus pocus

in fact there is more to the Metropolis Hastings algorithm and MCMC

which are much more interesting

Peter Taylor

One @ at a time is enough.

Lembik

argh.. I did that again .. sorry

I blame the muscle memory in my fingers :)

Peter Taylor

11:07 AM

I've skimmed the Wikipedia pages for Metropolis Hastings and MCMC and I don't see the connection.

They both talk about sampling from a probability distribution. Does that implicitly lead to an optimisation technique?

(Other than the "pick a random value and see whether it's better than the best found so far", which seems pretty sub-optimal)

Lembik

yes.. if you define the distribution to make high scoring instances have higher probability

then you get an optimisation algorithm

you can define the probability of an instance any way you like.. it's just a function from instances to probabilities

Peter Taylor

Ok. So it's another form of stochastic hill-climbing?

Lembik

@PeterTaylor well sort of. It has the very strong provable property that at convergence you sample from exactly the probability distribution you have specified

of course convergence may be a long way off :)

so it is related to stochastic hill climbing but not really the same thing

Peter Taylor

And if there's a large plateau of near-maximum values, it's not going to do very well.

Lembik

right.. so the whole magic is in the moves you specify. Which is of course like saying, you will have to solve the problem :)

which is always going to be the case

Peter Taylor

11:15 AM

The description in terms of random walks with rejection criteria sounds very hill-climbing-esque.

Lembik

it is certainly related... as I say the main difference is the provable outcome

in terms of the distribution you end up sampling from

the general rule of thumb is to have local moves which are common and global moves which are rare

look at the opening sentence of cs.princeton.edu/courses/archive/spr06/cos598C/papers/…

"A recent survey places the Metropolis algorithm among the ten algorithms that have had the
greatest influence on the development and practice of science and engineering in the 20th
century (Beichl & Sullivan, 2000). "

Peter Taylor

I'm impressed: although that citation is wrong, Google Scholar put the correct one before the cited one in its results for my search. computer.org/csdl/mags/cs/2000/01/c1022.pdf

Lembik

interesting

in other news.. It seems I have found some suffix array construction code that takes < 30 seconds for my kmer input

PhiNotPi

11:39 AM

@Geobits I would have wanted the random tournament results by now, but my computer auto-hibernated after only a few rounds.

I've timing it to be about 15 seconds per round.

Transcript for