Archive for the ‘Game Theory’ Category

Writing a Halite Bot in Clojure [Incomplete Knowledge/Deception Bots?]

Tuesday, December 6th, 2016

Writing a Halite Bot in Clojure by Matt Adereth.

From the post:

Halite is a new AI programming competition that was recently released by Two Sigma and Cornell Tech. It was designed and implemented by two interns at Two Sigma and was run as the annual internal summer programming competition.

While the rules are relatively simple, it proved to be a surprisingly deep challenge. It’s played on a 2D grid and a typical game looks like this:


Each turn, all players simultaneously issue movement commands to each of their pieces:

  1. Move to an adjacent location and capture it if you are stronger than what’s currently there.
  2. Stay put and build strength based on the production value of your current location.

When two players’ pieces are adjacent to each other, they automatically fight. A much more detailed description is available on the Halite Game Rules page.

Looking at the rules page, it looks like:

  • Bots have accurate knowledge of all positions and values.
  • Deception of bots isn’t permitted.
  • Interesting from a bot programming perspective but lack of knowledge and the ever present danger of deception are integral parts of human games.

    Any bot games that feature both a lack of knowledge and/or deception?

The New Chess World Champion

Tuesday, December 30th, 2014

The New Chess World Champion by K W Regan.

From the post:

Larry Kaufman is a Grandmaster of chess, and has teamed in the development of two champion computer chess programs, Rybka and Komodo. I have known him from chess tournaments since the 1970s. He earned the title of International Master (IM) from the World Chess Federation in 1980, a year before I did. He earned his GM title in 2008 by dint of winning the World Senior Chess Championship, equal with GM Mihai Suba.

Today we salute Komodo for winning the 7th Thoresen Chess Engines Competition (TCEC), which some regard as the de-facto world computer chess championship.

Partially computer chess history and present with asides on Shogi, dots-and-boxes, Arimaa, and Go.

Regan forgets to mention that thus far, computers don’t compete at all in the game of thrones. No one has succeeded in teaching a computer to lie. That is knowing the correct answer and for motives of its own, concealing that answer and offering another.


Komodo (commercial, $59.96)

Stockfish (open source)

How to Win at Rock-Paper-Scissors

Friday, December 26th, 2014

How to Win at Rock-Paper-Scissors

From the post:

The first large-scale measurements of the way humans play Rock-Paper-Scissors reveal a hidden pattern of play that opponents can exploit to gain a vital edge.


If you’ve ever played Rock-Paper-Scissors, you’ll have wondered about the strategy that is most likely to beat your opponent. And you’re not alone. Game theorists have long puzzled over this and other similar games in the hope of finding the ultimate approach.

It turns out that the best strategy is to choose your weapon at random. Over the long run, that makes it equally likely that you will win, tie, or lose. This is known as the mixed strategy Nash equilibrium in which every player chooses the three actions with equal probability in each round.

And that’s how the game is usually played. Various small-scale experiments that record the way real people play Rock-Paper-Scissors show that this is indeed the strategy that eventually evolves.

Or so game theorists had thought… (emphasis added)

No, I’m not going to give away the answer!

I will only say the answer isn’t what has been previously thought.

Why the different answer? Well, the authors speculate (with some justification) that the smallness of prior experiments resulted in the non-exhibition of a data pattern that was quite obvious when done on a larger scale.

Given that N < 100 in so many sociology, psychology, and other social science experiments, the existing literature offers a vast number of opportunities where repeating small experiments on large scale could produce different results. If you have any friends in a local social science department, you might want to suggest this to them as a way to be on the front end of big data in social science. PS: If you have access to a social science index, please search and post a rough count of participants < 100 in some subset of social science journals. Say since 1970. Thanks!

Complex Adaptive Dynamical Systems, a Primer

Friday, August 9th, 2013

Complex Adaptive Dynamical Systems, a Primer by Claudius Gros. (PDF)

The high level table of contents should capture your interest:

  1. Graph Theory and Small-World Networks
  2. Chaos, Bifurcations and Diffusion
  3. Complexity and Information Theory
  4. Random Boolean Networks
  5. Cellular Automata and Self-Organized Criticality
  6. Darwinian Evolution, Hypercycles and Game Theory
  7. Synchronization Phenomena
  8. Elements of Cognitive Systems Theory

If not, you can always try the video lectures by the author.

While big data is a crude approximation of some part of the world as we experience it, it is less coarse than prior representations.

Curious how less coarse representations will need to become in order to exhibit the complex behavior of what they represent?

I first saw this at Complex Adaptive Dynamical Systems, a Primer (Claudius Gros) by Charles Iliya Krempeaux.

Game Theory, n.

Monday, July 8th, 2013

I happened across the index to the Economist, which sported this entry: game theory.

Some of the economists I have known were interested in game theory (Originated with John von Neumann.)

Back at the Economist, I was surprise that the first entry read:

Are international football tournaments curse or boon?

Then noticing a definition of game theory that reads:

Reporting and analysis on the politics, economics, science and statistics of the games we play and watch

Just having an index isn’t enough. 😉

Algorithmic Economics

Saturday, November 10th, 2012

Algorithmic Economics, August 6-10, 2012, Carnegie Mellon University.

You will find slides and videos for:

Another view of social dynamics. Which is everywhere when you think about it. Not just consumers but sellers, manufacturers, R&D.

There isn’t any human activity separate and apart from social dynamics or influenced by them.

That includes the design, authoring and marketing of topic maps.

I first saw this in a tweet from Stefano Bertolo, mentioning the general link and also the lecture on game theory.

Introduction to Game Theory – Course

Monday, October 29th, 2012

Introduction to Game Theory – Course by John Duffy.

From the description:

This course is an introduction to game theory, the study of strategic behavior among parties having opposed, mixed or similar interests. This course will sharpen your understanding of strategic behavior in encounters with other individuals–modeled as games–and as a participant in broader markets involving many individuals. You will learn how to recognize and model strategic situations, to predict when and how your actions will influence the decisions of others and to exploit strategic situations for your own benefit.

Slides, homework (with answers), pointers to texts.

The notion of “rational” actors in the marketplace took a real blow from Alan Greenspan confessing before Congress that market players had not acted rationally.

Still, a highly developed field that may give you some insight into the “games” you are likely to encounter in social situations.

I first saw this at Christophe Lalanne’s A bag of tweets / October 2012.

Catering to the long tail? (business opportunity)

Tuesday, August 7th, 2012

I was struck by a line in Lattice games and the Economics of aggregators, by P. Jordan, U. Nadav, K. Punera, A. Skrzypacz, and G. Varghese, that reads:

A vendor that can provide good tools for to reduce the cost of doing business F is likely to open the floodgates for new small aggregators to cater to the long tail of user interests — and reap a rich reward in doing so.

You see? Struggling through all the game theory parts of the paper were worth your time!

A topic map application that enables small aggregators select/re-purpose/re-brand content for their “long tail of user interests” could be such an application.

Each aggregator could have their “view/terminology/etc.” both as a filter for content delivered as well as how it appears to their users.

Not long tails but think of the recent shooting incident in Aurora.

A topic map application could deliver content to gun control aggregators, with facts about the story that support new gun control laws, petitions and other activities.

At the same time, the same topic map application could delivery to NRA aggregators, the closest gun stores and hours for people who take such incidents as a reason to more fully arm themselves.

Same content, just repurposed on demand for different aggregators.

True, any relatively sophisticated user can setup their own search/aggregation service, but that’s the trick isn’t it? Any “relatively sophisticated user.”

Thinking not so much as a “saved search” or “alert”, dumpster diving is only to productive and it is tiring, but curated and complex searches that users can select for inclusion. So they are getting the “best” searches composed by experts.

I am sure there are other options and possibilities for delivery of both services and content. Topic maps should score high for either one.

PS: Slides from Stanford RAIN Seminar

Stanford – Delayed Classes – Enroll Now!

Tuesday, March 6th, 2012

If you have been waiting for notices about the delayed Stanford courses for Spring 2012, your wait is over!

Even if you signed up for more information, you must register at the course webpage to take the course.

Details as I have them on 6 March 2012 (check course pages for official information):

Cryptography Starts March 12th.

Design and Analysis of Algorithms Part 1 Starts March 12th.

Game Theory Starts March 19th.

Natural Language Processing Starts March 12th.

Probabilistic Graphical Models Starts March 19th.

You may be asking yourself, “Are all these courses useful for topic maps?”

I would answer by pointing out that librarians and indexers have rely on a broad knowledge of the world to make information more accessible to users.

By way of contrast, “big data” and Google, have made it less accessible.

Something to think about while you are registering for one or more of these courses!

Game Theory

Tuesday, December 6th, 2011

Game Theory by Matthew Jackson and Yoav Shoham.

Another Stanford course for the Spring of 2012!

From the description:

Popularized by movies such as “A Beautiful Mind”, game theory is the mathematical modeling of strategic interaction among rational (and irrational) agents. Beyond what we call ‘games’ in common language, such as chess, poker, soccer, etc., it includes the modeling of conflict among nations, political campaigns, competition among firms, and trading behavior in markets such as the NYSE. How could you begin to model eBay, Google keyword auctions, and peer to peer file-sharing networks, without accounting for the incentives of the people using them? The course will provide the basics: representing games and strategies, the extensive form (which computer scientists call game trees), Bayesian games (modeling things like auctions), repeated and stochastic games, and more. We’ll include a variety of examples including classic games and a few applications.

Just in time for an election year so you will be able to model what you think is rational or irrational behavior on the part of voters in the U.S. 😉

The requirements:

You must be comfortable with mathematical thinking and rigorous arguments. Relatively little specific math is required; you should be familiar with basic probability theory (for example, you should know what a conditional probability is) and with basic calculus (for instance, taking a derivative).

For those of you not familiar with game theory, I think the course will be useful in teaching you a different way to view the world. Not necessary more or less accurate than other ways, just different.

Being able to adopt a different world view and see its intersections with other world views is a primary skill in crossing domain borders for new insights or information. The more world views you learn, the better you may become at seeing intersections of world views.

META’2012 International Conference on Metaheuristics and Nature Inspired Computing

Saturday, November 5th, 2011

META’2012 International Conference on Metaheuristics and Nature Inspired Computing


  • Paper submission: May 15, 2012
  • Session/Tutorial submission: May 15, 2012
  • Paper notification: July 15, 2012
  • Session/Tutorial notification: June 15, 2012
  • Conference: October 27-31, 2012

From the website:

The 4th International Conference on Metaheuristics and Nature Inspired Computing, META’2012, will held in Port El-Kantaoiui (Sousse, Tunisia).

The Conference will be an exchange space thanks to the sessions of the research works presentations and also will integrate tutorials and a vocational training of metaheuristics and nature inspired computing.

The scope of the META’2012 conference includes, but is not limited to:

  • Local search, tabu search, simulated annealing, VNS, ILS, …
  • Evolutionary algorithms, swarm optimization, scatter search, …
  • Emergent nature inspired algorithms: quantum computing, artificial immune systems, bee colony, DNA computing, …
  • Parallel algorithms and hybrid methods with metaheuristics, machine learning, game theory, mathematical programming, constraint programming, co-evolutionary, …
  • Application to: logistics and transportation, telecommunications, scheduling, data mining, engineering design, bioinformatics, …
  • Theory of metaheuristics, landscape analysis, convergence, problem difficulty, very large neighbourhoods, …
  • Application to multi-objective optimization
  • Application in dynamic optimization, problems with uncertainty,bi-level optimization, …

The “proceedings” for Meta ’10 can be seen at: Meta ’10 papers. It would be more accurate to say “extended abstracts” because, for example,

Luis Filipe de Mello Santos, Daniel Madeira, Esteban Clua, Simone Martins and Alexandre Plastino. A parallel GRASP resolution for a GPU architecture

runs all of two (2) pages. As is about the average length of the other twenty (20) papers that I checked.

I like concise writing but two pages to describe a parallel GRASP setup on a GPU architecture? Just an enticement (there is an ugly word I could use) to get you to read the ISI journal with the article.

Conference and its content look very interesting. Can’t say I care for the marketing technique for the journals in question. Not objecting to the marketing of the journals, but don’t say proceedings when what is meant is ads for the journals.