Posts:
46
Registered:
Feb 1, 2002
From:
Little Elm
Age:
32 Home page
How Many Possible Moves in Pente?
Posted:
Jan 30, 2004, 6:41 AM
Just for giggles and grins...
Dmitri and I just spent an hour or so figuring out hwo many moves are possible in a game of Pente. (Well, DM did the actual figuring and I did the dummy test on the figures.
I'm keen to know how many different possible moves players think can be played in a Pente game. Now, havgin said that what we really calculated the possibel moves for Go-Moku. But given that some positions would be impossible for Pente (i.e., a checkerboard pattern) this computation doesn't take into account captures so it probably come sclose to evening out.
So what do you say folks? How many possibel moves do you think you can play in Pente?
Posts:
542
Registered:
May 9, 2002
From:
Northeast USA
Re: How Many Possible Moves in Pente?
Posted:
Jan 30, 2004, 7:53 AM
Let me try to start the ball rolling. When you say, number of "moves", i assume you mean the number of unique ways which you can go from one state with stones in certain positions, directly to another state with stones in certain positions with the placement of a single stone. (By this definition, different routes of getting to the same state are considered unique. IE, 1. K10, L9; 2. K13, L10 and 1. K10, L10; 2. K13, L9 would be a total of 7 unique moves) For gomoku, the answer is definitely less than 361!. This is a very large number approximately equal to 1.438x10^768.
Of course, the hard part is reducing this number. Many factors are involved in reducing this number, such as opening move restrictions and the fact that the game ends when one player makes 5 in a row among others. Finding the exact number should prove to be extremely difficult. As of the current date computers are no where near powerful enough to deal with trying to "count" to a number this large -- IE, the brute force method is currently not feasible. I would love to see someone come up with a proof that shows the exact number, even if just for gomoku instead of pente. My prediction is that it will end up being larger than a googol!
Posts:
260
Registered:
Dec 16, 2001
From:
Maryland
Age:
53 Home page
Re: How Many Possible Moves in Pente?
Posted:
Jan 30, 2004, 7:23 PM
To add to up2ng's questions -- do you mean how many possible game states are there? On a 19x19 gomoku board there are 361 spaces, each one has three possible values -- black, white, or empty. So that is 3 to the power of 361, kinda large Of course not every possible configuration is possible, there cannot be two or more five-in-a-rows (except I guess, for placing a stone which forms multiple winning fives). Do you assume that players always block fours?
If you do not assume blocking fours, and you do allow a double five as a win, then take 3^361 and subtract all positions with more than 1 five (except for intersecting fives of the same color). So you have to calculate how many positions are possible with more than one five... not too easy.
Then you should reduce the number due to symmetry -- simplistically divide the number of positions by 8 because there are 8 possible rotations/reflections of any position. But that is not accurate because symmetrical positions do not have 8 unique rotations, for example a single stone in the center has only one unique position.
Re: How Many Possible Moves in Pente?
Posted:
Jan 30, 2004, 9:40 PM
On a 19x19 gomoku board there are 361 spaces, each one has three possible values -- black, white, or empty. So that is 3 to the power of 361.
this is flawed. although there are three states, most of them arew not applicable. the only applicable ones are those with an equal humber of black and white pieces or those with ione more white than black. so before even worrying about the positrions which include a 5 in a row, 3^361 is definitely off target.
If I do not accept a game invite right away, it means I will once I have fewer games in progress.
hmm. i see what you are doing with the 361 factorial. when greg and i worked the problem, we were calculating only the numbre of different full board arrangements-- "end game" positions if you will. we did not take into account that each one could be arrived at in a great many different ways, which is a different problem entirely. of course the way it was phrased in this forum clearly indicates that each path to the same board position should count diffferently.
the number of different final (filled board) positions is 361 c 180 which equals 1.968 x 10^107.
calculating the number of different ways to arrive at a filled board is 361! as up2ng correctly stated. 361! is 1.438 x 10^768 (using up2ng's figure), so dividing that by the number of game positions yields approx. 6 x 10^660.
that means that altrhough the number of filled board positions of 1.968 x 10^107 is quiote staggering, there an even more staghgering 6 x 10^660 ways to arrive at EACH one of positions. unfortunalely, these numbers are too large to be able to put them into any meaningful context.
none of this takes into account that many, in fact most, of these positions would notbe reachesd in a game because someone would get 5 in a row.
also, none of this counts games with a less than full board, something mark discussed but with a flaw in the solution.
a powerful enough computer, in theory, could analyze every possible game for pente or keyro pente and see if every possible sequence for player 2 hgas at least one successful counter by p1. my guess is that it would, meaning the computer could solve pente for p1. this means that
Message was edited by: dmitriking at Jan 30, 2004 3:57 PM
If I do not accept a game invite right away, it means I will once I have fewer games in progress.
Posts:
1,032
Registered:
Dec 16, 2001
From:
Powell, OH
Age:
37 Home page
Re: How Many Possible Moves in Pente?
Posted:
Jan 30, 2004, 10:02 PM
My statistics knowledge isn't that good but I did take a class in it. It seems to me that up2ng is correct with something of the order of 361!, maybe you can explain to us morons why it isn't dmitri!
Doesn't 361! make sense, or rather 360!. After the 1st move there are 360 possible moves for black. For each of those moves there are 359 possible moves for white's 2nd move (minus 25 for tourney rule). So just for the 1st 3 moves in a game there are 1 + 360 * 334 = 120241 positions. Then for black's 2nd move there are 358 choices so 120241 * 358 = 43,045,920. Extending it out to all 361 moves = 120241 * 358!. Of course there are the other problems of 5 in a row, captures that up2ng mentioned. Maybe we're missing something?
Posts:
260
Registered:
Dec 16, 2001
From:
Maryland
Age:
53 Home page
Re: How Many Possible Moves in Pente?
Posted:
Jan 30, 2004, 10:45 PM
Oh yeah, that was kinda dumb, lol. I guess you don't see a board filled with all white stones very often in real play
OK, so it looks like the idea may be to estimate the number of _realistic_ games that could be played in Pente. So we can ignore moves like A1 in the beginning. In fact my program when listing moves from a position will only consider moves within 2 spaces of played stones on the board (I have an option to increase that to 3, but I doubt you can present a game situation in which the BEST move is 3 spaces away from any stone). It seems that on average there are 60-100 reasonable moves at each turn. Games last up to about a maximum of 50 stones played in Pente. So at worst you would have 100 ^ 50 games which is 10 ^ 100 games, a nice even googol as up2ng predicted.
dmitri> a powerful enough computer, in theory, could analyze every possible game for pente or keyro pente and see if every possible sequence for player 2 has at least one successful counter by p1. my guess is that it would, meaning the computer could solve pente for p1. Right, the way gomoku was solved was to choose a move for p1, then try every counter by p2. You don't have to try every move for p1 as long as you find one that wins. Choosing moves for p1 in the beginning is done by opening book of moves that are known to be good by experience. Finding a series of threats for p1 that lead to a win isn't too hard because there are very limited responses by p2 to each threat.
Re: How Many Possible Moves in Pente?
Posted:
Jan 31, 2004, 12:12 AM
my longer, follow up email clarified that-- up2ng and i were answering different questions. if answering the question of "how many different filled-board positions are there," then 361! is wriong. this is the question i was answering ( and what greg and i worked on last night).
but if answering the Q of "how many different paths to the filled-board positions are there" then 361! is correct. this is the question up2ng was answering (and rightly so, based on the way the introductopry post phrased it).
If I do not accept a game invite right away, it means I will once I have fewer games in progress.
Posts:
542
Registered:
May 9, 2002
From:
Northeast USA
Re: How Many Possible Moves in Pente?
Posted:
Jan 31, 2004, 1:00 AM
Wow, this has already been a great discussion! But Mark, I don't think that the problem related to _realistic_ games at all -- only to _legal_ games. This means that black's first move to A1 surely should be counted and that blocking a 4 isn't necessary at all to be legal. However, as dmitri said, the ratio of white stones to black stones on the board must be legal to be counted (again, i'm gonna stick to gomoku here since adding captures very much further complicates the calculations substantially). I also assumed that symmetric board layouts were still considered unique.
It appears that Dweebo has read the problem the closest, if not the very same way that I interpreted it. He even has taken a crack at reducing the number by eliminating the number of illegal moves that are illegal due to the tournament opening rules -- which I was just too lazy to bother attempting. Now, for gomoku, the only other factor left that further reduces the number of legal moves that can be played, unless I'm missing something, is the fact that the game ends when a 5 in a row or multiple 5 in a row is made (I forget if more than 5 in a row ends the game in gomoku, but you get the idea). This is the real fruit of the given problem and at first glance I think it is absolutely incredibly more complex to find the exact solution for how many legal moves become illegal due to the fact that a 5 in a row has already ended the game than most of us will realize or be willing to admit. A mathematical proof for this aspect of the problem I believe would be extremely daunting and I would love to see someone present one!
Finally, Mark, you have opened the door to an incredibly intreguing side issue here. Specifically, this issue is the development and performance of Artificial Intelligence. In a strategy game such as pente or chess that is currently unsolvable for a computer due to technological limitations, it is amazing to see how human minds match up against the most powerful computer opponents. Specifically, how does the massive brute strength with a fixed algorithm and research library of the most powerful computer do against the complex logic and innovation presented by the most powerful human mind? A computer may chunk through billions of permutations every second while the human mind might analyse the "logically best" two or three moves over several minutes -- and still it seems so far that the computer cannot outperform the human in this task. There is no AI that even comes close thus far in pente, and recent chess experiments have proven that the human can at least hold its own. This is simply fascinating to me and is an amazing tribute to the power of the human mind.
On a related topic, many of us have discussed so far whether a computer "in theory" could solve the game of pente -- or, what I would like to ask here -- whether a computer could "count" all possible legal moves in gomoku as per how I've interpreted the problem to be. Well, it has been estimated that for many years, at least up through the year 2000, that computer speeds and also hardware such as memory and hard drives, have doubled in performance/capacity about every 18 months. Of course, it is predicted that this trend will level off significantly in the very near future if it hasn't already -- but let's make a BIG leap of faith and assume for a minute that it doesn't -- that the doubling time will be 18 months for the rest of time. Now, currently, in 2004, the most powerful computers cannot count faster than 1 x 10^10 per second -- at least in order of magnitude. Now, consider the term 2^n. Every time you add 1 to n, the term doubles. So, consider the trend that computer speed doubles twice every 3 years. Next, consider the year 2004 to be n = 0, and the computer speed is 10^10(2^n). Now, every time we increase n by 2, we have to add 3 to the year, so year = 1.5n Now, consider the equation 361! = 10^10(2^n) -- using 361! as our "upper limit" of the number to "count" to, and our "idealistic" estimate of 18 month doubling time forever. Solving for n gives the "number of times that computer speeds must double to count to our target number in one second". We get 2^n = 1.438x10^768/10^10 = 1.438x10^758. Take the ln of both sides gives n = 1745.7
Thus, it will take 1.5(1745.7) = 2618.6 YEARS to have a powerful enough computer!!!
Now, if we wanted to wait around a little longer for the computer to chunk through the problem slower than 1 second, we simply reduce n by 1 for every time that you are willing to DOUBLE the number of seconds that we will wait around. Using 365.25 days per year, there are 31557600 seconds in a year. Let x be the number of times we will double 1 second. Set 2^x = 31557600. Take the ln of both sides -- x = 17.3 So, we can reduce n by 17.3 OR reduce the number of years of development time by 1.5x17.3 = 25.9 years.
Thus, if we wanted to wait around for a YEAR for the computer to chunk its way up to 361!, we ONLY have to wait around for another 2592.7 years!!!
Posts:
542
Registered:
May 9, 2002
From:
Northeast USA
Re: although..........
Posted:
Jan 31, 2004, 2:08 AM
Now I'd like to address the problem that apparently was "meant" to be the topic, although i'd love to see someone fully solve the problem I originally took a crack at also.
The problem dmitri is presenting above is "how many different full board arrangements" are there? His answer is 361 choose 180. Remember that a choose b = a!/(b!(a-b)!) (i had to look it up so i figured i'd stick it in here )
The way you arrive at this solution is by understanding that, in gomoku (this does not work well for pente due to captures) the board MUST end with 181 white stones and 180 black stones. Now, to find all the combinations possible of where these white stones and black stones may be located, use the simple trick of placing all the white stones first! If you place all 181 white stones into a given configuration, there is ONLY 1 possible combination of corresponding black stones which fills the board. Thus, you can find the formula almost by saying it out loud to yourself -- Out of the 361 possible board locations, choose 181 of them and place them there! There are 361 choose 181 ways to do this.
This brings me to a slight hitch -- Dmitri's solution was 361 choose 180 and I just got 361 choose 181. Perhaps what dmitri did was place all the black stones first! Then, the board can be filled in with white stones EXACTLY one way for every combination of black stones. By this logic, the answer is indeed 361 choose 180. So which way is correct? It seemed to me that you should place the white stones first because that's how you would do it in a game, but perhaps this creates a few redundant positions? Actually, it turns out (i just realized) that 361 choose 180 EXACTLY EQUALS 361 choose 181 according to the equation above! This only makes sense if you just followed the previous logic.
Just to be clear, the assumptions here are that this is gomoku (no captures allowed), that we are completely ignoring the tournament rule, including that white must play the first move to the center location (otherwise, the answer might very well be 360 choose 180), that symmetry is unimportant (symmetric but nonidentical positions are unique) and ignoring that 5 in a row would have ended the game. I think this problem (as opposed to the problem I had originally attempted) is less daunting, but still pretty challenging to modify this answer based on 5 in a row ending the game. Basically, only those configurations which have have at most 1 5-in-a-row (or multiple 5-in-a-row sharing a stone) for white may be counted, and you can simply assume that the very last stone played (by white) was the one that created the 5-in-a-row, if any.
Quickly, I'll take a stab at how many 5-in-a-rows are possible, not including multiple 5-in-a-rows sharing a stone. The problem is further simplified if we do not count more-than-5-in-a-row to end the game, and I believe in gomoku you must make exactly 5-in-a-row to win (but I don't remember for sure -- let's assume this is the case).
Horizontal 5: On any horizontal row there are 15 ways to make 5 in a row. There are 19 such rows. Hor5 = 285.
Re: How Many Possible Moves in Pente?
Posted:
Jan 31, 2004, 2:11 AM
<<<<<< This is the real fruit of the given problem and at first glance I think it is absolutely incredibly more complex to find the exact solution for how many legal moves become illegal due to the fact that a 5 in a row has already ended the game than most of us will realize or be willing to admit. A mathematical proof for this aspect of the problem I believe would be extremely daunting and I would love to see someone present one! >>>>>>>>>>>
i agree-- i see no way any algorithm could possibly sort through 10^768 possibilities to group them in any logical way.
Message was edited by: dmitriking at Jan 31, 2004 2:59 PM
If I do not accept a game invite right away, it means I will once I have fewer games in progress.
Posts:
46
Registered:
Feb 1, 2002
From:
Little Elm
Age:
32 Home page
Re: How Many Possible Moves in Pente?
Posted:
Jan 31, 2004, 4:28 AM
Well up, in short, no. What you have to remember is that Moore's Law (that capacity will double every 18 months) addresses the ability for transistors to fit on a CPU. That is not the single parameter for the power of a computer to make calculations albeit the most important one. Now, to say that the amount of computational power doubles every 18 months is misleading because once you double the capacity of a chip, you actually increase its computational power by a larger exponent. I forget the actual formula for figuring the actual computing power based on chip size (in transistors). The correct way to discuss computational power is to discuss floating-point operations (flops) in a second. A floating point operation is merely any operation between two numbers on the real number line. The current largest supercomputer, the weather survey and forecaster in Japan, performs 35.86 teraflops a second. This is nearly 3 times more than its next closest competitor, the Los Alamos ASCI Q which performs 13.88 teraflops per second. Remember that tera means trillion. I should point out that these supercomputers are not a single machine in the sense that our home computer is a single machine. These supercomputers are actually what can be commonly referred to as Beowulf clusters which work in tandem as a single machine though they be made up of 5,120 separate 500MHz machines (as in the case fo the Earth Weather Simulator). Now, I'm no math fella as you can see by my silence on the actual issue here but I do knwo a thign or two about computers and my guess is that we'll see a computer strong enough to compute Pente in about 20-25 years. I read an article abotu 4 months ago on the problem of AI in Go in the New York Times. It was extremely interesting since the articel mainly focused on why the humans can easily defeat Go AIs. I believe that they estimated that in 100 years at current computer computational power advancement Go woudl be competitive for humasn to play against an AI. Pente is considerably less complicated than Go.
Posts:
542
Registered:
May 9, 2002
From:
Northeast USA
Re: How Many Possible Moves in Pente?
Posted:
Jan 31, 2004, 9:07 AM
Hmm, I'm really not sure what you are disagreeing with. I know that Moore's Law doesn't refer to actual processor performance (speed) but it's a decent approximation to make my point -- even Moore's Law is a gross approximation for what it is claiming. Even then, Moore's Law is only supposed to hold up until about the year 2010, after that development will slow down considerably -- perhaps coming much closer to linear growth than to sustaining exponential growth. Certainly, this technology boom will not continue at the exact same pace for several thousand years as I have generously assumed. Of course, the upcoming nuclear war will set things back a bit.
Furthermore, FLOPS is also not correct when talking about performance. The only way to accurately test for performance is to, well, test for performance. You have to run benchmark tests on the separate machines in question, and often the resulting performance differences are not the same as the difference in FLOPS.
So, I used cycles, however inaccurate it may be -- I tried to put the inaccuracies on the generous side in many respects. Plus, I only wanted my mythical computer to "count" to a certain number, never mind actually "searching" for anything which takes orders of magnitude more operations to complete than simple counting. Even then, counting to 10 takes WAY more than 10 operations for a computer to complete. So, my estimation was more than generous. And it took THOUSANDS OF YEARS OF DEVELOPMENT to be able to achieve the task!
I'm not sure that some of you really understand how large a number 361! actually is. Its VERY large. Let's put it in perspective shall we? Distance to the edge of the universe: 10^28 meters Age of the universe: 10^18 seconds Mass of a large man: 10^2 kg Mass of a battleship: 10^8 kg Mass of Earth: 10^25 kg Mass of the Universe: 10^51 kg The number of words printed since in the 500 years after the Gutenberg Bible: 10^17 If the entire universe were filled with protons and electrons so that there was no vacant space: 10^110
We're talking about a number larger than 10^768, it's VERY large! It would take a while to count that high.
About the AI development, I agreed already that for many of these strategy games, the computer cannot yet beat the human, and in the case of chess, there was a lot of specialized algorithm development and a vast library of past games for the computer to draw on, and it is still not crushing the humans yet, which is very fascinating. With proper algorithm development, etc, a computer MAY as you said solve pente within 25 years, but if so it will NOT be because the computer was able to play every possible pente move -- this will be impossible for a computer to accomplish for a LONG time.
