|
||
|
Title: Arimaa the Sequel Post by IdahoEv on Mar 3rd, 2006, 2:56am I've been pondering over what we humans will do when computers can beat us regularly at Arimaa. Obviously ... build a game that's even harder for computers! So what would be involved in an Arimaa sequel? Aside from the obvious answer of "make the board bigger", which is the primary advantage that go gives to humans, my thoughts have been mostly centered around elimination of any materiel advantage. If the game could be made entirely positional, static evaluation could be made extremely difficult. Perhaps such game could be like arimaa but with no captures at all, only freezes (or capture and replace). Maybe making all the pieces identical would be another blow in favor of humans; no numerical advantage but only pattern recognition of global board positions. Any other thoughts? |
||
|
Title: Re: Arimaa the Sequel Post by Fritzlein on Mar 3rd, 2006, 9:39am Omar has said that at one point in designing Arimaa there were no captures. With 16 pieces per side that would be a just be a big mess that nobody could ever break through, so he had fewer pieces per side, but I still think the danger of stalemate would be large. One problem in designing anti-computer games is that humans thrive when the changes in position are gradual, but this can make a game very boring. Who would want to play Arimaa if humans could beat computers every time but it took two hundred moves to do so? Omar has created something really special: a game we can beat computers at which also happens to be extremely fun. |
||
|
Title: Re: Arimaa the Sequel Post by Ryan_Cable on Mar 3rd, 2006, 4:48pm My hunch is that stone placement games are fundamentally more computer resistant (or less human resistant) than games where pieces are moved around. There are simple stone placement games where computers play well such as m,n,k-games (generalized tic-tac-toe) and Reversi (Othello), but strategically deep stone placement games seem to be totally dominated by humans. For instance, Christian Freeling has offered $1000 for any computer program that can beat him once at Havannah in a 10 game match before 2012. And Havannah is likely to be easier to program than go because the winning conditions are tactical. http://en.wikipedia.org/wiki/Havannah My guess is that Grand Arimaa (bigger board, more pieces), would not be sufficient. If a bot is developed that can handle a branching factor of 16,000, I seriously doubt that increasing the branching factor to 160,000 will help significantly. |
||
|
Title: Re: Arimaa the Sequel Post by IdahoEv on Mar 3rd, 2006, 5:19pm If a bot is developed that can handle a branching factor of 16,000, I seriously doubt that increasing the branching factor to 160,000 will help significantly. This is why my thoughts lie more along the lines of making static evaluation difficult, anyhow, because making the board bigger isn't a very challenging task. |
||
|
Title: Re: Arimaa the Sequel Post by 99of9 on Mar 3rd, 2006, 6:05pm Interesting topic on 03/03/06 at 02:56:46, IdahoEv wrote:
As a bot writer I find that having many pieces makes the bot hard to program. Just because there are different strategies for all the different pieces, and each has to be programmed in separately, and then they have to be weighted *correctly*. |
||
|
Title: Re: Arimaa the Sequel Post by Ryan_Cable on Mar 4th, 2006, 6:16am Bots mostly dominate tactical goal search. The importance of this could be greatly reduced by changing the winning conditions to require 2 rabbits to goal or something similar. This would make the game much more focused on material advantage and probably much less fun. Currently most games are decided before tactical goal search becomes important anyway. The other area bots could potentially dominate is tactical trap search in messy positions. If it turns out that some sort of aggressive, messy play is sound, then this could be a huge advantage for bots making the goal issue irrelevant. I’m not sure how you could make Arimaa less aggressive without making it pointlessly defensive though, so I think humanity should probably hope that the blue22 strategy proves to be mostly unsound. |
||
|
Title: Re: Arimaa the Sequel Post by omar on Mar 4th, 2006, 11:43am I think it would depend on what approach the computers were using. If it was a brute force approach resulting from hardware speedups then just increasing the board size and pieces will be enough. But if they were using some other approach similar to how humans construct moves then the branching factor would not matter. This of course would be a significant break through in AI software and such an approach would find many applications in other fields. It's interesting that you should post this because about a week ago Aamir and I played a variant of Arimaa where there were no captures, the rabbits could also move back and the goal was to be the first player to form a connected chain of ones own pieces from your side of the board to the opponents. It didn't seem that interesting and probably has flaws, but we haven't given up on it yet :-) Not having caputres makes the game more difficult for computers, because there is no guidance (or gradients in the state space of the game) from material as to which direction to go to reach the win state. Also having a connection oriented goal as opposed to a race to a specific location makes the game more difficult for computers but not for humans. The visual system of humans are already wired to process connections and shapes. Writting a program to determine if a connection has been made across the board is almost like writting a program to traverse a maze. So these are the two changes I think that would make Arimaa more difficult without increasing the game material. BTW, I also enjoy playing Havannah. I was able to win against Christian the first time I played him, but it was because he didn't take my ring threats seriously until it was too late :-) I haven't been as lucky since. |
||
|
Title: Re: Arimaa the Sequel Post by IdahoEv on Mar 10th, 2006, 12:53am on 03/03/06 at 18:05:04, 99of9 wrote:
The first thing that occurred to me when thinking about how to program an Arimaa bot is that Arimaa only has two pieces, Rabbits and Others. Others just has a "size" parameter. Yet, it is harder for a computer than chess, due to the positioning element and the branch factor. Eliminating the difference in pieces, it seems to me, would prevent the computer from having any material evaluation strategy other than total piece count. And total piece count. might be next to meaningless in a game with a position-oriented goal. When pieces are different, they implicitly have an average game value, which allows a computer to use a material evaluation approach. |
||
|
Title: Re: Arimaa the Sequel Post by Fritzlein on May 12th, 2006, 3:13pm on 03/03/06 at 16:48:51, Ryan_Cable wrote:
The branching factor is important to hinder computers in Arimaa, but I think the biggest factor is that the position changes slowly. Arimaa on a 16-by-16 board would change even more slowly because, for example, an elephant could not switch sides of the board in a move or two. Therefore Grand Arimaa would probably give humans a larger advantage regardless of branching factor. That said, I'm not sure I would have the patience to play a game that slow. |
||
|
Title: Re: Arimaa the Sequel Post by 99of9 on May 12th, 2006, 7:13pm on 05/12/06 at 15:13:45, Fritzlein wrote:
To prove this to yourselves, consider playing chess where each player got 4 "moves" per turn. (That would have a similar branching factor to arimaa). Computers would be able to think to at least 2.5 ply (10 steps), but humans wouldn't have a chance. |
||
|
Title: Re: Arimaa the Sequel Post by leo on May 12th, 2006, 8:33pm on 03/10/06 at 00:53:42, IdahoEv wrote:
Once in a while I try to imagine a game where strengths were determined by particular clusters of pieces, for instance two adjacent pieces would be needed to push or pull a third one, all pieces by themselves being of equal strength. Do you know of existing games of this kind? This might be the Arimaa 2 challenge after the first one is won. |
||
|
Title: Re: Arimaa the Sequel Post by seanick on Jun 24th, 2006, 8:08am If chess had 4 moves per turn, it wouldn't be the computer that had no chance. it would be whoever was not going first. |
||
|
Title: Re: Arimaa the Sequel Post by seanick on Jun 24th, 2006, 8:11am The game bontago written by some students at Digipen ... http://www.digipen.edu/GameGallery/websites/Bontago essentially has a "group" factor, that is, if you have a tall enough tower, the opponents pieces will be destroyed if they are too close... check it out, its an interesting game, actually. |
||
|
Arimaa Forum » Powered by YaBB 1 Gold - SP 1.3.1! YaBB © 2000-2003. All Rights Reserved. |