When all mind games will be solved by computers we won't be able to play online anymore. Right?

*We* will be able to play online. It's just that we won't be able to play against the idiots who use machine help.

Replace “idiots” with “poor souls”.

Personally, I'd prefer to replace the idiots with people who don't cheat…

I've put out a modest price in 2002 that no program will be able to beat me even one out of ten till 1012 in a simple pencil and paper game like havannah. It's 2009 now and the very few programs still play like morons. Why can we program a complicated game like chess, but not a simple one like havannah? Think about it :)

Of course you can't cheat in havannah for precisely that reason. Rejoice in human superiority, even if humans themselves cannot explain it!

“I've put out a modest price in 2002 that no program will be able to beat me even one out of ten till 1012 in a simple pencil and paper game like havannah.”

Let me just clarify: I am sure that you mean “no computer will be able to beat me at havannah until 2012”, right? You don't mean “no computer will be able to beat me at an arbitrary simple pencil and paper game (for example, havannah), until 2012”, do you. [because that's how the sentence might be interpreted].

“Why can we program a complicated game like chess, but not a simple one like havannah? Think about it :) "

I hope I don't offend you when I offer you my answer! I think it's because Chess has a history going back (in some form) for over a thousand years, and hence far more people know about chess than havannah (because you are not a thousand years old), and hence far more people have tried hard to make a good chess program, and hence the theory is far more developed. For many of the “modern abstract board games” you can google and find one or two groups of people who have thought very hard about trying to solve it, typically during the course of their research, or even in their free time. But IBM were hiring people in the 1980s whose sole job was to produce a very good chess-playing program and IBM were presumably also investing in developing hardware specifically designed to implement the algorithms very effectively—although it would probably be hard to come up with a figure, it probably wouldn't be unreasonable to say that in some sense IBM invested millions of dollars into creating Deep Blue (adding up the salaries of the people who were working full-time on the project in the 8 or so years of its existence). And as well as the IBM team there were many many other people working on chess AI. That, in my opinion, is the reason chess AI is more advanced than Havannah AI. If IBM had invested millions of dollars into making a Havannah program that could beat you, starting in 1988 or so, would you still be making your claim? I am not so sure! But of course I could be wrong!

“I hope I don't offend you when I offer you my answer!“

Not at all, and you're absolutely right about the difference in scale of the efforts. Yet, at the same time, we do see Pente programs, Othello programs, checkers- and mancala programs, hex programs and even a game machine like Zillions that shows many games are programmable up to an 'acceptable' level.

But if your answer implies that 'all games are equally difficult to program', and that the scale of the effort is the only criterion, then I must in all politeness disagree.

And there have been serious efforts:

http://dfa.imn.htwk-leipzig.de/havannah/

Ironically, as in Hex, it is the absence of a lot of things that makes Havannah so easy to understand for humans and so hard for computers:

- no material imbalance

- no movement

- no general direction

- no capture

- no promotion

Finally, the challenge is still open :)

Games like Othello, checkers and mancala still “have history on their side” so perhaps that's one reason why AI is more developed. Perhaps Pente happens to be a game that, for some reason, happens to be playable well by a computer using only a few good ideas behind the AI. Connect 4 on a 'standard' board as sold in shops (6x7) was also computer-solved and again this is in some sense because after thinking about it for a while (and coming up with Victor Allis' “rules”) the amount of processing one has to do to completely solve the game becomes manageable.

“But if your answer implies that 'all games are equally difficult to program'”

I certainly didn't mean to imply that! I absolutely agree with you that properties of the game are crucial as well as “popularity”—'go' would be a fabulous example of this (incredibly popular in some parts of the world; computers play very poorly, probably not through lack of effort on the part of programmers, probably more to do with the nature of the game). And I also suspect that Havannah is “closer to go than it is to chess”, in some sense!

I'm glad you agree that the nature of the game is an issue here - it gives us something to think about :)

A few differences between Chess, Go, and Hex.

Chess and Go have been invented ages ago, so human should be not too bad at these games thanks to study of masters. Even though many strong Go players like to say they don't understand anything in the game of Go, I think strong Hex players have even less insights. If Hex had been discovered centuries earlier, the level of our current AI (designed with recent Hex discovery) wouldn't reach intermediate level, which it does now.

However the study of Chess developped an easy to express kind of knowledge: “this position is bad because there are many weak squares … a weak square is defined by: …“, whereas Go developped intuition-like knowledge (correct me if I'm wrong): “I like this position because the shapes are beautiful…“. It's probably one reason because in teaching games, chess teachers often agree to comment during the game and afterwards whereas Go teachers always want to wait for the game to finish before giving their insights.

Hence it has been much easier to design appropriate evaluation functions in chess than in Go. Hex hasn't been studied for such a long time and the only relevant evaluation functions come from graph flows or electrical resistance and hasn't a much to do with human play-style.

The game tree exploration and the propagation of evaluation function results through minmax-like procedure makes the evaluation of the root position even more accurate. The branching factor of chess is not as high as Go or Hex, and it is not so easy to prune moves in these games to reduce it. Therefor the game tree is much shallower in Go and Hex.

Computer chess is more successful because of these two reasons: good evaluation function, in depth exploration of the game tree. It takes full advantage of the classical (much studied) way to view computer playing. Monte Carlo Tree Search (=~ UCT =~ MoGo) is some new way to see computer playing, it looks very interesting now and has enabled a rise of Computer Go playing level. However it is not yet as fully understood as minimax + EF.

The “difficulty” of the rules of a game does not have such a big impact IMHO. It's main influence on computer playing is only the time required to generate legal moves and to check if a position a terminal. Arimaa has difficult rules and is difficult for computers, Go has simple rules and is difficult. Othello has easy rules and is easy, Chess has difficult rules and is easy.

You can check that Othello shares a lot of thing with chess viewing from a computer playing point of view. A relevant EF is easily found (number of possible moves + occupied squares value …), the branching factor is not huge. Hence computer plays Othello well.

Chess, Checkers, Amazon, Breakthrough, Street Soccer and EWN involve moving a non-increasing number of pieces around an otherwise structureless space. Go, Hex, Havannah, TwixtPP and Dots&Boxes involve building structures on a blank board. I think that's the significant difference in the success of computer programs. As of this writing, I know there are programs for Chess and Checkers that can beat the best humans, and there are no such programs for Go, Hex or Havannah. My hypothesis predicts that the best programs for TwixtPP and Dots&Boxes cannot beat the best humans. Does anyone know if that is in fact the case?

I would also predict that good programs are possible for Amazon, Breakthrough and EWN. Does anyone know if they have been written?

While there may be good algorithms for recognizing structures and potential structures, I expect that a massively parallel architecture would work better for them. Instead of 1..256 (Deep Blue had 256, right?) processors, each of which executes a few Giga-instructions per second, I predict the automaton that will beat Mr. Freeling at his own game will be more like intelligent RAM where every byte can execute a few kilo- or mega-instructions per second, with communications mapped more like a neural network.

Whether or not I can beat a computer at dots and boxes depends strongly on the time limits allowed. If a computer is allowed to think for a day or two on its moves then it can play perfectly on a 5x5 board from about the 17th line, and if it has been sufficiently wise beforehand then it should probably win against me. But in a 5-minute game I would definitely rate my chances. On the other hand I'm not sure I would beat a computer 10-0 in a 5-minute game, I would rather think something like 7-3. I should try it!

Let me make some comments about my personal experience with dots and boxes endgame analysis. It is absolutely the norm that in a game of dots and boxes, on a 5x5 board, after 20 lines have been played, that the true analysis of a move may well consist of checking essentially *every* legal response on the board other than the loony moves. In practice this means that every move that does not give away a box for free may well be a winning response to the move I'm considering (there is no real “structure” beyond a certain point, I percieve it as sort of random), and there may well be 10-15 reasonable responses to my move 18; the relevant part of the game tree is very “fat” (lots of branching) but very short (because by 25 moves or so the game is easily analysable). On the other hand, my rather more limited understanding of hex is that, when trying to see the win, the game tree is *much* thinner (many moves have basically only one response) and hence people can analyse *much* further. My understanding is that people like David Bush can beat programs like six something like 9-1 in real time.

But othello has a low branching factor also, and we can not see more than about 3 ply deep. It also has to do if the game is “structured”, understandable to the human brain.

@pedropajarito's post

That's a point of great interest. As it happens, another inventor at Fanatic, the dutch games club I frequented in the early eighties, had invented a game called Explocus (an applet for which will shortly be available).

Explocus, in the above context, turned out to be quite the opposite of Havannah. It was very hard, if at all possible, to look deep into the game's capricious tactics - the fun was in the trying :)

But one student, Wim van Weezep, wrote a program with a very simple evaluation function that was near impossible to beat. Completely impossible I'd say if the current clockspeed is taken into account. We later improved on it, and Ed van Zon implemented it in the Zillions game machine, so you can prove me wrong :)

Both games have simple rules, yet one is extremely hard to program, but relatively easy to read for the human mind, the other is quite the opposite.

So I see a kind of distinction between 'mind-friendly' and 'machine-friendly' games, no quality aspects implied.

Christian Freeling wrote:

> I've put out a modest price in 2002 that no

> program will be able to beat me even one out of ten

> till 2012 in the game “Havannah”.

In the text I have corrected some obvious typos/miss-expressions.

Where can I find the complete regulations for this prize?

Thanks in advance for the details.

Ingo Althofer.

It is put out under the auspices of abstract games magazine in the summer issue of 2002. However, AGM has led a on-and-off existence, and now that the USA has entered the Great Depression, their entire website appears to have disappeared, if you'll excuse the obvious typos and mis-expressions ;-)

Till now I haven't seen a program that even remotely appears to play havannah though, so the details may be futile to begin with.

It is put out under the auspices of abstract games magazine in the summer issue of 2002. However, AGM has led a on-and-off existence, and now that the USA has entered the Great Depression, their entire website appears to have disappeared, if you'll excuse the obvious typos and mis-expressions ;-)

Till now I haven't seen a program that even remotely appears to play havannah though, so the details may be futile to begin with.

> It is put out under the auspices of abstract games magazine in the summer issue > of 2002. However, AGM has led a on-and-off existence, and now that the USA has > entered the Great Depression, their entire website appears to have disappeared, > if you'll excuse the obvious typos and mis-expressions ;-)

>

> Till now I haven't seen a program that even remotely appears to play havannah

> though, so the details may be futile to begin with.

Thanks for the reply.

I am interested in the details of the prize, before I start an engagement.

May you please make a scan or a digital photo of the prize announcement?

If you send an email with it to me (under 3-hirn-verlagbigbang – where

you have to substitute “bigbang” by “@gmx.de”) I am willing to hang that

document on my website.

Thanks in advance,

Ingo Althofer.

Hello Ingo,

One doesn't have to google very far to see you're a big shot in the field, and I welcome that. I don't care either who organizes such an event. My main objective was to counter the general idea that now that computers play Chess at grandmaster level, they will shortly play all abstract games at at least the same level. The idea is supported by successful quests in checkers and oware, the latter by storing the whole tree.

But, as the proverb goes, 'success has many fathers, failure is an orphan', and almost from the onset it was clear that computers and havannah were a poor match.

This started me wondering about our perception of games - the complicated patterns of chess, the simple ones of havannah. More than anything my challenge is meant to make that difference more of a focus point. Why can we break down chess strategy in little pieces and assign values to them, and why can't we do the same with some other and often 'simpler' games like havannah.

Part of the answer has been given by wccanard, but I'm interested in the difference between what I perceive as 'mind-friendly' and 'machine-friendly' games.

Hence the challenge. The stakes are 1000 euros for the machine if it wins one out of 10 games (base-10 board), and 1000 for me if I win all ten games.

I don't care too much about time per game as long as it's reasonable. I do care about the location because I cannot leave 4 raccoon dogs and a 12-foot tigerpython in the care of someone else.

I do think machines eventually (barring a so dramatic chain of events that nobody cares about games in the first place) can 'learn' to play havannah, but hardly by using the good old evaluation function - it's not easy to evaluate any havannah position.

Ah! Interesting, Christian! It's more of a bet then! I didn't know that.

From the several websites where I've read about this proposal, they've all led me to believe it was simply an 'offer'… 1,000 euros if a program defeats you once.

I didn't realize that if you defeat the program all ten times, the author must pay YOU 1,000 euros!

(I also didn't know it was on a base-10 board, but I did assume that.)

Thanks for the clarification.

Hi Ed, you're right about that, and if it goes under AGM auspices it's an offer indeed. But since a resurrection of AGM seems unlikely - at least I haven't heard of it - I feel free to reconsider conditions, and I would have to go to a fair bit of trouble given my current situation. The actual match would probably be held within some games related context with a lot of publicity and a budget to match.

If I could play live online, under some form of supervision (to prevent me from secretly using a computer for instance :), then my trouble would be minimized and could revert to an offer with no other reward than the publicity involved.

Hello Ingo,

One doesn't have to google very far to see you're a big shot in the field, and I welcome that. I don't care either who organizes such an event. My main objective was to counter the general idea that now that computers play Chess at grandmaster level, they will shortly play all abstract games at at least the same level. The idea is supported by successful quests in checkers and oware, the latter by storing the whole tree.

But, as the proverb goes, 'success has many fathers, failure is an orphan', and almost from the onset it was clear that computers and havannah were a poor match.

This started me wondering about our perception of games - the complicated patterns of chess, the simple ones of havannah. More than anything my challenge is meant to make that difference more of a focus point. Why can we break down chess strategy in little pieces and assign values to them, and why can't we do the same with some other and often 'simpler' games like havannah.

Part of the answer has been given by wccanard, but I'm interested in the difference between what I perceive as 'mind-friendly' and 'machine-friendly' games.

Hence the challenge. The stakes are 1000 euros for the machine if it wins one out of 10 games (base-10 board), and 1000 for me if I win all ten games.

I don't care too much about time per game as long as it's reasonable. I do care about the location because I cannot leave 4 raccoon dogs and a 12-foot tigerpython in the care of someone else.

I do think machines eventually (barring a so dramatic chain of events that nobody cares about games in the first place) can 'learn' to play havannah, but hardly by using the good old evaluation function - it's not easy to evaluate any havannah position.

Hi Ed, you're right about that, and if it goes under AGM auspices it's an offer indeed. But since a resurrection of AGM seems unlikely - at least I haven't heard of it - I feel free to reconsider conditions, and I would have to go to a fair bit of trouble given my current situation. The actual match would probably be held within some games related context with a lot of publicity and a budget to match.

If I could play live online, under some form of supervision (to prevent me from secretly using a computer for instance :), then my trouble would be minimized and could revert to an offer with no other reward than the publicity involved.

Sorry about the dups. I wanted to edit a typo, couldn't find how, returned to the page via 'history' and the browser uploads it again. I'm still amazed at these things :)

Hi, i'm curious too, what the original conditions were (although you say the offer is not valid,

atm, unless abstract games magazine is “resurrected”):

If someone lost all 10 games, would he be allowed to submit an improved version of the program,

say, three months later? What if 2 persons submit programs around the same time? (is the better one chosen/or first submitted)

Was a binary to be submitted (so you could practice for a week), or would you see the program

for the first time, when the ten games are played?

Did the program have to be published after a successful test (binary only/source)?

(or maybe only a paper explaining the algorithm..)

Were these details unspecified?

If I could play live online, under some form of supervision (to prevent me from secretly using a

computer for instance :), then my trouble would be minimized and could revert to an offer with

no other reward than the publicity involved.

i.e. in case of the private offer (=non AGM) + internet play (=no trouble of travelling for you),

you revert your private offer to the conditions of AGM?

(sorry, i posted with wrong account)

(jamjam)

\\\* Reply to Christian Freeling ***

Hello Christian,

thank you for your reply. I have been

meditating about it carefully.

> … almost from the onset it was clear that

> computers and havannah were a poor match.

Similar statements have been made concerning

other games of territory and connection games.

But in recent years, impressive progress has

been made using “indirect evaluations” (via

Monte Carlo simulations). So, nowadays computers

have become much better for instance in Go and

in Amazons.

In my own group Monte-Carlo tree search was used

to program Michail Antonow's nice connection

game “ConHex”.

See at

http://www.althofer.de/cebit-2007-english.html

and in the lower part of

http://www.althofer.de/lange-nacht-jena.html

for reports.

In March 2007, Antonow won by 2-0 against the machine,

in November 2007 two games ended in a 1-1 tie.

> The stakes are 1000 euros for the machine if it

> wins one out of 10 games (base-10 board),

> and 1000 for me if I win all ten games.

What do you think of the following setup?

A computer-computer qualifying tournament in

Havannah (on 10-boards) in the first half of 2012.

The winner would get the right to challenge you

for the 10 games (to be played in the second half of 2012),

for instance with one game every 2 weeks.

The right of the first move should be switched

from game to game.

In case of several “almost winners” in the computer

tournament (for instance: the tournament is played

as a double round robin and the top three participants

score 1-1 against each other) each of them may

play some of the ten games (and I would guarantee

the 1,000 Euro for you in case of your 10-0 win).

> I don't care too much about time per game as

> long as it's reasonable.

Would 3 hours in total for the whole game and

each side be ok with you?

> I do care about the location because I cannot leave

> 4 raccoon dogs and a 12-foot tigerpython in the care

> of someone else.

I think, indeed play via internet might be the best solution.

> I do think machines eventually can 'learn' to play havannah,

> but hardly by using the good old evaluation function - it's

> not easy to evaluate any havannah position.

Monte-Carlo does not need to evaluate single positions.

It only has to be able to play “semi-random” games in some

proper way.

\\\*****************

I do not really have an idea who might have better chances

in 2012: it might be you by a large margin, or the computer(s)

by a large margin, or it might be a very close battle.

Taking into consideration that Havannah is your brainchild

and that you will be 65 years old in 2012, such a 10 game

match might be really straining for you. (Perhaps you know

the stories of John Henry and that of Marion Tinsley (as described

in Schaeffers book “on jump ahead”) - or you may contact

Michail Antonow and ask him about his feelings through the

ConHex matches against the computer.)

So, I would accept when you NOW step back from your offer.

(Especially in 2002, when you made the offer, the Monte

Carlo approach was not realized to be a chance to play games

really well.)

However, I would not like when you NOW accept a setting like

the one above, programming people start efforts (the Waldmann

group from Leipzig has started already with a UCT approach),

and then in middle 2012 you say: “Ok guys, but I will not

play by this or that reason.”

Please, think carefully about my ideas and let me know

your answers. I feel prepared to coordinate a (big) computer

Havannah project.

Ingo.

The ConHex program sounds quite interesting. Is there a down loadable version suitable for trying out the game? I have played a few times on Richards PBEM server. It would be nice to practice against a machine to get past the idiot level before playing more people:-)

You play well enough already David :)

Hi Ingo,

Please allow me some time to think this over.

P.S. I've read “One Jump Ahead” and having such an event end in the style of Marion Tinsley would be great … publicitywise ;-)

P.P.S. Marion Tinsley was the greatest Checkers player ever, I'm slightly over mediocre at Havannah, but then … that's exactly my point :)

@Christian

> Please allow me some time to think this over.

Of course. And feel free to contact me with Email

via the address given above.

@David

> The ConHex program sounds quite interesting. Is there a

> down loadable version suitable for trying out the game?

The program GuentHex (developed by student Joerg Guenther)

is not publicly available. The company which is distributing

ConHex commercially did not allow.

Ingo.

@jamjam

My games are public, so it would be nice to have some idea about the program too, and I'd certainly prefer too see a couple of games it played, beforehand.

As for time, I'm a fast player (pattern recognition and all that :). One hour each for the first 30 moves or so would suit me. Three hours would make me fall asleep.