Arimaa Forum - Print Page


    
      
        Arimaa Forum
        (http://arimaa.com/arimaa/forum/cgi/YaBB.cgi)
      

        Arimaa >> Off Topic Discussion >> How Computer Chess Changed Programming
        
(Message started by: omar on Nov 12^th, 2010, 6:27pm)

Title: How Computer Chess Changed Programming
Post by omar on Nov 12^th, 2010, 6:27pm

One of my friends sent me this link to an interesting article in IEEE Spectrum.

http://spectrum.ieee.org/slideshow/computing/software/how-computer-chess-changed-programming/

Title: Re: How Computer Chess Changed Programming
Post by christianF on Dec 18^th, 2010, 6:33am

on 11/12/10 at 18:27:23, omar wrote:

One of my friends sent me this link to an interesting article in IEEE Spectrum.

http://spectrum.ieee.org/slideshow/computing/software/how-computer-chess-changed-programming/

It's more like an advertisement for the extrapolation to a situation wherein computers rule supremely. It may apply for many games, especially complicated structured ones like Chess and Arimaa. But it doesn't address the question why, then, simple structured games like Go and Havannah appear to be relatively harder to approach using the same type of evaluation functions.

In Go and Havannah, and doubtless a number of other games that still pose a challenge to the computerworld, the Monte Carlo evaluation (http://en.wikipedia.org/wiki/Monte_Carlo_method) is therefore being investigated, a method that wouldn't seem applicable to Chess or Draughts.
I'm not an expert, not even close, but I play against these bots regularly in the approach to the 2012 human versus bot Havannah challenge, where I must beat the best bots combined 10 out of 10.
Here are some of the bots involved, and their programmers:

Castro (http://www.littlegolem.net/jsp/info/player.jsp?plid=21870)
Rating to date: 1793
Rank to date: 19
Havannah program written by Timo Ewalds (here (https://www.cs.ualberta.ca/news-events/computing-news/2009/university-alberta-qualifies-acm-programming-contest-finals-china)'s some info) at the University of Alberta, Canada. UCT based, with rave, some knowledge, and a few other tricks, written in C++.
Currently accepting unrated games on all sizes, and rated games on the smaller sizes for now. Used 90s per move for the first few games, using 5 minutes per move now.

Wanderer_C (http://www.littlegolem.net/jsp/info/player.jsp?plid=21160)
Rating to date: 1685
Rank to date: 37
An Havannah bot written by Richard Lorentz (http://www.csun.edu/~lorentz/) with the help of students. Thanks to Klaashaas for providing the Ruby s-cripts that allow wanderer_c to work without any human intervention and thanks to Richard Pijl for his technical advice.

Deep Fork (http://www.littlegolem.net/jsp/info/player.jsp?plid=20779)
Rating to date: 1676
Rank to date: 43
Havannah AI by Thomas Reinhardt, HTWK-Leipzig, Germany.

Quote:

Timo Ewalds:
In Hex, virtual connections are guaranteed connections, assuming you choose to defend them, but there is never any reason to not defend them.
In Havannah, they are not guaranteed. Frames are often broken, like in the game against Christian Freeling, or could be broken like in this game. A frame that can't be broken is also not necessarily a winning formation, since it could be too slow. It's also not obvious how to use a partial frame, since it could be used in many different ways but with different speeds or certainties.
There are several examples of games where the opponent had a guaranteed win in 2 while Castro was about 10 moves away from a win and without a good frame, but Castro still won by using 9 forcing moves.
Castro does recognize the bridge virtual connection, and is encouraged to maintain them, both in the tree and in the rollouts. It can't be forced to maintain them though, since there may be more important moves elsewhere, like if this virtual connection is now in a dead area. Even when it is encouraged to maintain the virtual connection and when there is a frame, it is tough to see it since the frame may not succeed in a rollout because some other winning formation could happen first. Finding the specific move to refute the frame is even harder given random rollouts.
(thread (http://www.littlegolem.net/jsp/forum/topic2.jsp?forum=50&topic=459))

In the summer of 2012 I will play ten base-10 games against the offspring of these bots and/or other bots.
My current rating is, embarrassingly, 1873, rank 11 (currently the top negotiates the 2100 level) but with a good record against bots, although I've lost a couple of base-8 games and even one or two base-10, if I remember correctly.
On small boards, say up to and including base-6, strategy and tactics become so intertwined that it's all tactics and humans have little chance. If strategy and tactics drift apart as is the case in base-8/10, the bots get blind spots.
Fortunately :)

Title: Re: How Computer Chess Changed Programming
Post by Fritzlein on Dec 19^th, 2010, 8:59am

Thanks for the update, Christian. I will follow the Havannah challenge match with interest.

Title: Re: How Computer Chess Changed Programming
Post by omar on Dec 20^th, 2010, 11:32am

I've played base 10 games against bot Castro as well and it definitely has a long way to go. Although I did manage to lose a couple games by underestimating it's ring threats :-)

Title: Re: How Computer Chess Changed Programming
Post by christianF on Dec 22^nd, 2010, 6:57am

on 12/20/10 at 11:32:18, omar wrote:

I've played base 10 games against bot Castro as well and it definitely has a long way to go. Although I did manage to lose a couple games by underestimating it's ring threats :-)

Yes, strong in close combat, keep your distance :)