Author |
Topic: Arimaa the Sequel (Read 1653 times) |
|
IdahoEv
Forum Guru
Arimaa player #1753
Gender: 
Posts: 405
|
 |
Arimaa the Sequel
« on: Mar 3rd, 2006, 2:56am » |
 Quote  Modify
|
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?
|
|
 IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: Arimaa the Sequel
« Reply #1 on: Mar 3rd, 2006, 9:39am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
Ryan_Cable
Forum Guru
Arimaa player #951
Gender:
Posts: 138
|
|
Re: Arimaa the Sequel
« Reply #2 on: Mar 3rd, 2006, 4:48pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
IdahoEv
Forum Guru
Arimaa player #1753
Gender:
Posts: 405
|
|
Re: Arimaa the Sequel
« Reply #3 on: Mar 3rd, 2006, 5:19pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
99of9
Forum Guru
Gnobby's creator (player #314)
 
Gender:
Posts: 1413
|
|
Re: Arimaa the Sequel
« Reply #4 on: Mar 3rd, 2006, 6:05pm » |
Quote Modify
|
Interesting topic
on Mar 3rd, 2006, 2:56am, IdahoEv wrote:| 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. |
|
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*.
|
|
IP Logged |
|
|
|
Ryan_Cable
Forum Guru
Arimaa player #951
Gender:
Posts: 138
|
|
Re: Arimaa the Sequel
« Reply #5 on: Mar 4th, 2006, 6:16am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
omar
Forum Guru
Arimaa player #2
Gender:
Posts: 1003
|
|
Re: Arimaa the Sequel
« Reply #6 on: Mar 4th, 2006, 11:43am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
IdahoEv
Forum Guru
Arimaa player #1753
Gender:
Posts: 405
|
|
Re: Arimaa the Sequel
« Reply #7 on: Mar 10th, 2006, 12:53am » |
Quote Modify
|
on Mar 3rd, 2006, 6:05pm, 99of9 wrote:Interesting topic
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*. |
|
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.
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: Arimaa the Sequel
« Reply #8 on: May 12th, 2006, 3:13pm » |
Quote Modify
|
on Mar 3rd, 2006, 4:48pm, Ryan_Cable wrote:| 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. |
|
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.
|
| « Last Edit: May 12th, 2006, 3:14pm by Fritzlein » |
IP Logged |
|
|
|
99of9
Forum Guru
Gnobby's creator (player #314)
Gender:
Posts: 1413
|
|
Re: Arimaa the Sequel
« Reply #9 on: May 12th, 2006, 7:13pm » |
Quote Modify
|
on May 12th, 2006, 3:13pm, Fritzlein wrote:
The branching factor is important to hinder computers in Arimaa, but I think the biggest factor is that the position changes slowly. |
|
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.
|
|
IP Logged |
|
|
|
leo
Forum Guru
Gender:
Posts: 278
|
|
Re: Arimaa the Sequel
« Reply #10 on: May 12th, 2006, 8:33pm » |
Quote Modify
|
on Mar 10th, 2006, 12:53am, IdahoEv wrote:
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.
|
|
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.
|
|
IP Logged |
|
|
|
seanick
Forum Guru
SeaNICK
Gender:
Posts: 97
|
|
Re: Arimaa the Sequel
« Reply #11 on: Jun 24th, 2006, 8:08am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
seanick
Forum Guru
SeaNICK
Gender:
Posts: 97
|
|
Re: Arimaa the Sequel
« Reply #12 on: Jun 24th, 2006, 8:11am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
|
Home
Help
Search
Members
Login
Register
Reply
Notify of replies
Send Topic
Print