Science and Technology Quiz 3

[Mise]

A* algorithm - funny you should mention that, was reading about it the other day. Didn't find it useful though, cos I don't understand how to make a "heuristic function"... To me, that's the hardest part (everything else seems trivial), and yet it's a given in the wiki article on it.

 

[ParadigmShifter]

You can use the distance to goal (any metric will do, usually taxicab metric on a NESW move only grid, max(|x1-x2|, |y1-y2|) for civ games, euclidean metric for non grid games).

You can also make the metric more game specific.

EDIT: Heh, had min instead of max for civ metric

It also doesn't need to be a proper metric either. You could penalise moves along open terrain in a FPS by factoring distance from walls into the heuristic, etc.

The better the heuristic is the quicker the search will end but evaluating the heuristic also has a computational time cost. There are pathological cases that always examine every possible path as well

 

[Mise]

Hmm, interesting... I'll have to mull this new information over...

 

[civ_king]

Heuristics to me means assigning a value to a partial solution to a problem so that more promising paths can be taken before less promising ones. The A* algorithm being a classic example although heuristics are used extensively in AI programming (was the AI players proposed golf shot any good? etc.).

The only invention machine I can think of that uses heuristics is that automated theorem prover program which does loads of trial and error deductions which are filtered by the user to get more interesting lines of deduction. Don't know who invented it though.

It isn't exactly "heuristics" but rather "genetic programming"

 

[ParadigmShifter]

Nah, genetic programming is combining instruction streams from programs which best achieved a specific goal in the current generation for several generations trying to evolve an optimal solution to a problem.

http://www.sambee.co.th/MazeSolver/mazega.htm

 

[civ_king]

okay, I'm thinking of genetic programming, because it does do it over generation weeding out the weaklings evolving to create the optimal solution

 

[GoodGame]

Civ_King, so really you're thinking of a genetic programming algorithm as a heuristics to teach an AI to play a game?

 

[civ_king]

Civ_King, so really you're thinking of a genetic programming algorithm as a heuristics to teach an AI to play a game?

um, I mean a machine that you feed specs, and it evolves a way to make it using genetic programming,

I don't remember mentioning a game (but it would be an awesome addition to civ IV)

 

[ParadigmShifter]

Civ_King, so really you're thinking of a genetic programming algorithm as a heuristics to teach an AI to play a game?

It's already been done with backgammon.

 

[civ_king]

I surrender, you have microwaved my brain, http://www.popsci.com/scitech/article/2006-04/john-koza-has-built-invention-machine there you move ParadigmShifter

 

[ParadigmShifter]

Annie and Bob are planting seeds.Every minute they plant 10 seeds in a straight line following on from the last seeds they planted.

They are being followed by 2 crows. Every minute, Annie's crow eats the seed at the beginning of her line of seeds. Bob's crow eats the first of the 10 seeds that Bob planted during each minute.

Annie and Bob continue doing this for an infinitely long time. Then they have a rest and look back at how many plants are growing.

How many plants do Annie and Bob see?

 

[Phlegmak]

Annie and Bob are planting seeds.Every minute they plant 10 seeds in a straight line following on from the last seeds they planted.

They are being followed by 2 crows. Every minute, Annie's crow eats the seed at the beginning of her line of seeds. Bob's crow eats the first of the 10 seeds that Bob planted during each minute.

Annie and Bob continue doing this for an infinitely long time. Then they have a rest and look back at how many plants are growing.

How many plants do Annie and Bob see?

Since Annie's crow and Bob's crow eat one per minute, each person has an equal number plants.

 

[ParadigmShifter]

That's... not correct!

 

[peter grimes]

They don't see any plants, since they plant for an infinitely long time, there is no point at which they stop...

 

[ParadigmShifter]

OK, let's say they speed up. They plant the first 10 in 1 second, the next 10 in 1/2 second, the next 10 in 1/4 second, etc., so they are done in 2 seconds. The crows speed up too. After the 2 seconds are up all the remaining seeds grow instantly

 

[Mise]

They'll see an infinite number of them?

 

[ParadigmShifter]

That's not correct either (note: Annie and Bob can't see each others plants).

 

[GoodGame]

That's not correct either (note: Annie and Bob can't see each others plants).

So Annie and Bob are planting separate rows of seeds, and not cooperating on the same row?

 

[ParadigmShifter]

So Annie and Bob are planting separate rows of seeds, and not cooperating on the same row?

Yes, separate rows, sorry if this wasn't clear.

 

[Mise]

Bob sees infinite seeds, Annie sees none, because Annie's crow is, in lim t->inf, eating just as many plants as Annie is placing, whereas Bob's crow is only eating 1/10th of what Bob is placing (in other words, Bob is planting 9 plants per turn, cos Bob's crow eats one of the ones he's just placed).