Link: Big Dog Robot by larvalsubjects

http://larvalsubjects.wordpress.com/2009/07/26/big-dog-robot/

…the advantage of legged robots such as this is that they can go just about anywhere. Where robots that use wheels and treads get bogged down in mud and rocky terrain, legged robots are able to tackle just about any terrain. Just think about the billy goat, for example. Even billy goats that are a few days old are able to climb mountainous terrain with little trouble. The remarkable thing about Big Dog is just how biological its movements look. You get a sense of this when you watch it slipping on the ice in the film above, but the footage I saw yesterday was even more remarkable. There researchers kicked the robot from the side as it was walking and the manner in which it recovered was eerily organic.

The interpretation of ‘biological’ traits as a sign of superior design or intelligence, is somewhat anthropocentric but completely natural. The robot in the video displays charateristics which we expect to see in animal quadrapeds, which is a big part of the ‘wow’ factor of the video.

More interesting to us as in the context of algorithms is the video in the same post describing machine learning. Any comments on that video?

July 29, 2009. General. Leave a comment.

Predicting Gambling behavior

“Using Neural Networks to Model the Behavior and Decisions of Gamblers, in Particular, Cyber-Gamblers.” by Victor K. Y. Chan.

A system is written that utilizes a back-propagation neural network to model Texas Holdem gamblers’ behavior, based on data collected from a cyber gambling website.

This article describes the use of neural networks and an empirical data sample of, inter alia, the amounts of bets laid and the winnings/losses made in successive games by a number of cyber-gamblers to longitudinally model gambler’s behavior and decisions as to such bet amounts and the temporal trajectory of winnings/losses. The data was collected by videoing Texas Holdem gamblers at a cyber-gambling website.

The full article is available on Scribd.

Gambler-ANNstructure-M1The above diagrams shows the structure utilized for one of the two neural networks developed for the paper. This one, dubbed “M1”, attempts to predict the bet amounts laid by each individual Texas Holdem gambler, based on winnings and losses in immediately preceding games, and the gambler’s current account balance.

M1: the model for successive bet amounts, which longitudinally models and thus
predicts the bet amounts in the successive game laid by each individual Texas Holdem
gambler based on his/her winnings/losses in a number of immediately preceding games
and his/her current gambling account balance.

Apparently, the ANN was generally speaking pretty successful, showing a mean magnitude of relative error on the order of 10^(-2). Two things caught my eye: 1) General betting trends were very well represented by the model, but short-lived (“high-frequency”, if you will) deviances in behavior were not.  The author notes that the same can be said of financial market models. 2) The same model was developed to predict six different gamblers — and achieved a high accuracy of prediction. What does this mean?  In the words of the author Victor Chan:

The influence of a gambler’s skills, strategies, and personality on his/her successive bet amounts is almost totally reflected by the pattern(s) of his/her winnings/losses in the several immediately preceding games and his/her gambling account balance.

Exclamation mark.

Article found on SciAm:  “Artificial Intelligence Predicts Gambling Behavior” via Mindhacks.

July 21, 2009. Tags: , , , , . General. 1 comment.

Queen Problems

Can you place three white queens and five black queens on a 5×5 chessboard so that no queen of one color attacks a queen of the other? The solution is unique, except rotations and reflections.

It took me longer than I first expected to solve this problem. The solution is: Puzzle-5BQ-3WQ

Since a queen attacks along rank, file, and diagonal, it leaving triangles between them unattacked, with a knight-move as the closest vertex of each triangle. While that is immediately obvious to anyone familiar with chess, I was able to solve the problem by thinking about placing white queens in such a way as to allow the largest triangles. Before searching for a solution in that manner, I tried other methods unsuccessfully: hit-and-miss attempts (having at first underestimated the problem); placing queens at knight-moves as one might do for the classic eight-queen problem (see below); utilizing symmetry by placing queens at, say, each corner and at the center; and so on.

How would a computer solve the problem? Well, a wikipedia article suggests, among other methods, a genetic algorithm, which struck my fancy.  So I started writing one.

After the skeleton of the algorithm was written and I started tinkering with parameters and the fitness function, I realized this problem would make a great introduction to genetic algorithms and also provide a simple platform for various discussions about the nuances of GAs.

July 17, 2009. Tags: , , , , . General. Leave a comment.

Excerpt from The Selfish Gene

The following passage caught my eye when I read Richard Dawkin’s “Selfish Genes and Selfish Memes” (1976).

Computers do not yet play chess as well as human grand masters, but they have reached the standard of a good amateur. More strictly, one should say programs have reached the standard of a good amateur, for a chess-playing program is not fussy which physical computer it uses to act out its skills. Now, what is the role of the human programmer? First, he is definitely not manipulating the computer from moment to moment, like a puppeteer pulling strings. That would be just cheating. He writes the program, puts it in the computer, and then the computer is on its own: there is no further human intervention, except for the opponent typing in his moves. Does the programmer perhaps anticipate all possible chess positions and provide the computer with a long list of good moves, one for each possible contingency? Most certainly not, because the number of possible positions in chess is so great that the world would come to an end before the list had been completed. For the same reason, the computer cannot possibly be programmed to try out ‘in its head’ all possible moves, and all possible follow-ups, until it finds a winning strategy. There are more possible games of chess than there are atoms in the galaxy. So much for the trivial nonsolutions to the problem of programming a computer to play chess. It is in fact an exceedingly difficult problem, and it is hardly surprising that the best programs have still not achieved grand master status.

The programmer’s actual role is rather more like that of a father teaching his son to play chess. He tells the computer the basic moves of the game, not separately for every possible starting position, but in terms of more economically expressed rules. He does not literally say in plain English ‘bishops move in a diagonal’, but he does say something mathematically equivalent, such as, though more briefly: ‘New coordinates of bishop are obtained from old coordinates, by adding the same constant, though not necessarily with the same sign, to both old x coordinate and old y coordinate’. Then he might program in some ‘advice’, written in the same sort of mathematical or logical language, but amounting in human terms to hints such as ‘don’t leave your king unguarded’, or useful tricks such as ‘forking’ with the knight. The details are intriguing, but they would take
us too far afield. The important point is this: When it is actually playing, the computer is on its own and can expect no help from its master. All the programmer can do is to set the computer up beforehand in the best way possible, with a proper balance between lists of specific knowledge and hints about strategies and techniques.

The genes too control the behavior of their survival machines, not directly with their fingers on puppet strings, but indirectly like the computer programmer. All they can do is to set it up beforehand; then the survival machine is on its own, and the genes can only sit passively inside.

In the last paragraph, Dawkins is closing out his analogy between genes and computer programs.

I read this in The Mind’s I (Hostadter, Dennett), but it was originally published in Dawkin’s The Selfish Gene. Read the entire essay online [PDF] or you can buy the book.

June 9, 2009. Tags: , , , . General. Leave a comment.

What is an Algorithm?

The term “Algorithm” is a broad one, but on this blog I will use it primarily to refer to a set of computer instructions for completing some task.

I will not in this introduction dive into a discussion of denotations, the etymology of the word, classifications and history of algorithms, and so forth — it is not my intention to reproduce encyclopedia pages here. Instead, I would like to use this space for personal musings and explorations, and as a means to learn with my readership about those things that make algorithms so damn interesting.

My first order of business on this blog is to pick some low hanging fruit: I’d like to share some unoriginal ideas about algorithms as a way of establishing some common foundation for our discussion. You may already be familiar with these ideas, but bear with me. Brushing upon them will help me justify the existence and discover the direction of this blog.

Welcome!

November 17, 2008. General. Leave a comment.