Author |
Topic: Scalability of bots vs. humans (Read 1350 times) |
|
Cobra
Forum Full Member
Arimaa player #3971
Gender: 
Posts: 16
|
 |
Scalability of bots vs. humans
« on: Apr 8th, 2009, 5:51pm » |
 Quote  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:
Posts: 16
|
|
Re: Scalability of bots vs. humans
« Reply #1 on: Apr 8th, 2009, 7:09pm » |
Quote 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
Gender:
Posts: 5928
|
|
Re: Scalability of bots vs. humans
« Reply #2 on: Apr 9th, 2009, 6:26am » |
Quote 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:
Posts: 16
|
|
Re: Scalability of bots vs. humans
« Reply #3 on: Apr 9th, 2009, 7:01am » |
Quote Modify
|
I'm confused. I thought Arimaa couldn't be stalemated...
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: Scalability of bots vs. humans
« Reply #4 on: Apr 9th, 2009, 9:33am » |
Quote 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:
Posts: 882
|
|
Re: Scalability of bots vs. humans
« Reply #5 on: Apr 10th, 2009, 3:39am » |
Quote 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
Gender:
Posts: 5928
|
|
Re: Scalability of bots vs. humans
« Reply #6 on: Apr 10th, 2009, 5:24am » |
Quote 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:
Posts: 1003
|
|
Re: Scalability of bots vs. humans
« Reply #7 on: Apr 10th, 2009, 9:56pm » |
Quote 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:
Posts: 16
|
|
Re: Scalability of bots vs. humans
« Reply #8 on: Apr 11th, 2009, 9:08am » |
Quote 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:
Posts: 1003
|
|
Re: Scalability of bots vs. humans
« Reply #9 on: Apr 11th, 2009, 3:31pm » |
Quote 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 
|
|
IP Logged |
|
|
|
|
Home
Help
Search
Members
Login
Register
Reply
Notify of replies
Send Topic
Print