Welcome, Guest. Please Login or Register.
Nov 23rd, 2024, 1:57pm

Home Home Help Help Search Search Members Members Login Login Register Register
Arimaa Forum « Scalability of bots vs. humans »


   Arimaa Forum
   Arimaa
   General Discussion
(Moderator: supersamu)
   Scalability of bots vs. humans
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Scalability of bots vs. humans  (Read 1357 times)
Cobra
Forum Full Member
***



Arimaa player #3971

   


Gender: male
Posts: 16
Scalability of bots vs. humans
« on: Apr 8th, 2009, 5:51pm »
Quote Quote Modify Modify

Has anyone explored how the gap between bots and humans changes as the board size is increased? Like say, a 16 x 16 board with double the pieces and more traps.
 
A larger board will make for even more possibilities per turn, thereby "exploding" the branches of the game tree. In fact, as we all know, this type of thing is what primarily makes Arimaa more difficult for bots compared to Chess.
 
If existing bot performance vs. humans degrades with a size increase then I think it would be an indication of human intelligence.
 
Of course, the bots are almost certainly hard coded for 8x8 at this point. I guess that's also a sign of intelligence: Human players could immediately play on a larger board whereas most, if not all bots, would break. They are brittle.
IP Logged
Cobra
Forum Full Member
***



Arimaa player #3971

   


Gender: male
Posts: 16
Re: Scalability of bots vs. humans
« Reply #1 on: Apr 8th, 2009, 7:09pm »
Quote Quote Modify Modify

I said "double the pieces" for the 16x16 board. But it could be quadruple if you decide to put pieces 4 rows deep.
IP Logged
Fritzlein
Forum Guru
*****



Arimaa player #706

   
Email

Gender: male
Posts: 5928
Re: Scalability of bots vs. humans
« Reply #2 on: Apr 9th, 2009, 6:26am »
Quote Quote Modify Modify

In the case of Go, it seems that humans scale up much better than computers.  I understand that at 9x9 Go bots are already playing at a professional level, whereas at 19x19 Go they are still amateurs.  A more surprising observation, however, is that the game of Go itself scales so well.  Playing on a larger and larger board doesn't break the game; to the contrary it apparently makes the game richer and more subtle.
 
For Arimaa, I'm afraid that scaling up the game would break it so badly that they human vs. computer question would not even be interesting.  Certainly having only 4 traps in a 16x16 board would make capture impossible.  I expect that at a minimum one would need 16 traps to keep the game fluid.  But even so it is not clear to me that having four times the number of pieces wouldn't stalemate the game.  Or maybe the defensive tendency could be overcome by having four times as many ranks of pieces, so that it would be less likely for pieces of equal rank to neutralize each other?  One would definitely have to play test to get the right balance, unlike in Go where the obvious generalization just works.
 
On the other hand, it is possible for a game that is broken for humans to be very computer-resistant.  Bram Cohen suggests that the ultimate anti-computer game would be intolerably slow and boring for humans.  Maybe even if 16x16 Arimaa tended to get massively bogged down it would still have deeper strategies and greater depth than 8x8 Arimaa.  But if the game takes 640 moves to play, who cares that it is deep?
« Last Edit: Apr 9th, 2009, 6:27am by Fritzlein » IP Logged

Cobra
Forum Full Member
***



Arimaa player #3971

   


Gender: male
Posts: 16
Re: Scalability of bots vs. humans
« Reply #3 on: Apr 9th, 2009, 7:01am »
Quote Quote Modify Modify

I'm confused. I thought Arimaa couldn't be stalemated...
IP Logged
Fritzlein
Forum Guru
*****



Arimaa player #706

   
Email

Gender: male
Posts: 5928
Re: Scalability of bots vs. humans
« Reply #4 on: Apr 9th, 2009, 9:33am »
Quote Quote Modify Modify

on Apr 9th, 2009, 7:01am, Cobra wrote:
I'm confused. I thought Arimaa couldn't be stalemated...

The rule against repetition insures that every game will eventually end.  But how long is eventually?  Consider the position below:

  +---+---+---+---+---+---+---+---+
8 | e | m | h | h | d | d | c | c |
  +---+---+---+---+---+---+---+---+
7 |   |   |   |   |   |   |   |   |
  +---+---+---+---+---+---+---+---+
6 |   |   | * |   |   | * |   |   |
  +---+---+---+---+---+---+---+---+
5 | r | r | r | r | r | r | r | r |
  +---+---+---+---+---+---+---+---+
4 | R | R | R | R | R | R | R | R |
  +---+---+---+---+---+---+---+---+
3 |   |   | * |   |   | * |   |   |
  +---+---+---+---+---+---+---+---+
2 |   |   |   |   |   |   |   |   |
  +---+---+---+---+---+---+---+---+
1 | E | M | H | H | D | D | C | C |
  +---+---+---+---+---+---+---+---+
    a   b   c   d   e   f   g   h

This is a forced win for Silver, or perhaps a forced win for Gold.  By the rules of the game it can't be drawn because eventually one player or the other will have no option other than repeating the position.  But each player's non-rabbit-pieces can be arranged in 3,706,773,840 different configurations, which gives an upper bound of 27,480,344,601,816,691,200 moves before before any position repeats for a third time.  In my book that's a stalemate.
 
Let me emphasize that there has never been a position like this in 100,000 games so far.  It is merely a theoretical possibility.  In an Arimaa variant, however, such theoretical possibilities need to be taken more seriously.  There are specific ways in which Arimaa might be broken, but isn't.  In variants of Arimaa, those possible breakages are the first thing to check.
« Last Edit: Apr 9th, 2009, 9:36am by Fritzlein » IP Logged

RonWeasley
Forum Guru
*****




Harry's friend (Arimaa player #441)

   


Gender: male
Posts: 882
Re: Scalability of bots vs. humans
« Reply #5 on: Apr 10th, 2009, 3:39am »
Quote Quote Modify Modify

I wonder if any of our leading bot bashers could construct this wall of rabbits.  Do it unrated and resign once completed.  Has this really not been done yet?  I have a vague memory of attempts at this years ago.
IP Logged
Fritzlein
Forum Guru
*****



Arimaa player #706

   
Email

Gender: male
Posts: 5928
Re: Scalability of bots vs. humans
« Reply #6 on: Apr 10th, 2009, 5:24am »
Quote Quote Modify Modify

We did something similar in an attempt to lose by immobilization as quickly as possible, but not only was the objective different, it required the cooperation of both players.
 
http://arimaa.com/arimaa/gameroom/comments.cgi?gid=23325
 
It would be a strange bot-bashing challenge to demonstrate superiority by forcing a stalemate.  That would only be coup against a stronger opponent.  The closest I can think of to that was this game
 
http://arimaa.com/arimaa/gameroom/comments.cgi?gid=18806
 
But between humans I don't think there has been any game whether the weaker side (either in skill of position) was able to jam up the position so that the stronger side had no hopes of progress.  There was a game involving robinson which was close, and which I can't find now, but if I recall correctly, it wasn't really a stalemate because robinson's opponent was overlooking a way to make progress.  Do you recall that game?
IP Logged

omar
Forum Guru
*****



Arimaa player #2

   


Gender: male
Posts: 1003
Re: Scalability of bots vs. humans
« Reply #7 on: Apr 10th, 2009, 9:56pm »
Quote Quote Modify Modify

I would venture to guess that the gap would be wider between humans and computer if the size of the Arimaa board was bigger. The process of trying to generate all possible moves and picking the best one I think would break down to completely infeasible as the branching factor increases. In a way life is a game in which you have an immense number of possible moves at every second, but we don't get overwhelmed trying to determine what all choices we have.
 
One of the problems with making a game too large is the time it would take to finish it. The longer a game takes to finish the less number of people who would be able to play it. Go is a perfectly scalable, but for thousands of years people have been content with the 19x19 (or smaller) size. I would think this is mainly because larger sizes would take too long for the game to finish.
IP Logged
Cobra
Forum Full Member
***



Arimaa player #3971

   


Gender: male
Posts: 16
Re: Scalability of bots vs. humans
« Reply #8 on: Apr 11th, 2009, 9:08am »
Quote Quote Modify Modify

Yeah I agree that too large a board is bad for enjoyment and popularity. But it also strikes me as a way to emphasize the difference between [semi-]brute force search and "real intelligence" (whatever that is).
 
It may be an area to explore some day after the bots beat the 8x8 board against humans.
IP Logged
omar
Forum Guru
*****



Arimaa player #2

   


Gender: male
Posts: 1003
Re: Scalability of bots vs. humans
« Reply #9 on: Apr 11th, 2009, 3:31pm »
Quote Quote Modify Modify

on Apr 11th, 2009, 9:08am, Cobra wrote:
Yeah I agree that too large a board is bad for enjoyment and popularity. But it also strikes me as a way to emphasize the difference between [semi-]brute force search and "real intelligence" (whatever that is).
 
It may be an area to explore some day after the bots beat the 8x8 board against humans.

 
Until then it will be fun trying to stay ahead of the bots on such a small board. Just imagine a position can be represented as an 8 pixel by 8 pixel image with just 13 possible colors per pixel. Most games could be completely displayed in a 8x800 strip. I wonder what they would look like Smiley
IP Logged
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Arimaa Forum » Powered by YaBB 1 Gold - SP 1.3.1!
YaBB © 2000-2003. All Rights Reserved.