Besiege (the game) + Genetic Algorithm would be so awesome

A place to discuss the science of computers and programs, from algorithms to computability.

Formal proofs preferred.

Moderators: phlip, Moderators General, Prelates

arjan
Posts: 67
Joined: Tue Feb 26, 2013 7:48 pm UTC
Location: The Netherlands

Besiege (the game) + Genetic Algorithm would be so awesome

Postby arjan » Sun Feb 08, 2015 3:35 am UTC

Besiege is a game where you put parts together to form a weapon (a tank, a helicopter, a sheep-smashing device, anything), then steer it in order to destroy the enemy. This has lead to a lot of minecraft-like creativity. See http://imgur.com/search?q=besiege or this video https://www.youtube.com/watch?v=EUnjxftU6r0 .

In 1994, Karl Sims used genetic algorithms to both design creatures (using simple blocks) and designing the program that made them move in order to do tasks like "reach a certain distance", "follow the light", "get hold of an item". https://www.youtube.com/watch?v=bBt0imn77Zg

The game is in alpha, and the player has to defeat the computer, not another player. I hope the official release will allow for two players to play against each other, too. And I really, really, really hope they'll make an API available to enable anyone to try genetic algorithms to design and steer things.

Because the player controls the machine now and looks at it in 3D, the machines don't have a need for sensors. I think they'll be needed for the AI-version, but they should be really simple. "Nearest object is 30ft", "Temperature is Y", "I feel a touch 20N", "I see color red", etc.

The 1994 video is already fun to watch because of the creativity of the algorithm. I can't wait to see what ingenuity computers would use today. It may take 50 generations to install a canon and shoot at random, 5,000 to find a way to actually aim, and 50,000 to learn to communicate and create an organized attack. Ants can do that. After that, it needs not 2 but 40 different players in each round. The object would be changed to not destroy everyone else but to not be destroyed by others. I think it would really be interesting to see what happens. After 5,000,000,000 generations, would there be partnerships, diplomats, etc?

EDIT: Adding https://www.youtube.com/watch?v=xcIBoPuNIiw to show the capabilities of GA.

User avatar
phillip1882
Posts: 145
Joined: Fri Jun 14, 2013 9:11 pm UTC
Location: geogia
Contact:

Re: Besiege (the game) + Genetic Algorithm would be so aweso

Postby phillip1882 » Thu Feb 19, 2015 4:10 pm UTC

genetic algorithms aren't really good at finding optimal solutions, just solutions in general.
in my understanding anyway.
good luck have fun

User avatar
Xanthir
My HERO!!!
Posts: 5412
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Besiege (the game) + Genetic Algorithm would be so aweso

Postby Xanthir » Thu Feb 19, 2015 6:37 pm UTC

They're a search algorithm that does tree-climbing from a bunch of points, with some randomness built-in to help each point jump out of local minima. They find near-optimal solutions just fine in lots of cases.

(You may be mixing this up with the common knowledge that biological evolution just finds "good enough" solutions, not optimal ones. This is because the selection process stops selecting once you've "solved" it - the search space is full of plateaus that it can't optimize over. The only way to get better is to have a stronger selection process, which you can do easily in software; in biology, this is typically accomplished via an arms-race, where the selection criteria is driven by another evolving organism which wants the opposite of what you want.)
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))


Return to “Computer Science”

Who is online

Users browsing this forum: Google [Bot] and 3 guests