ok, Watsu. This is a tricky question and maybe Piecraft would be better at answering this one but I will have a go anyway. (Pete, please correct me if I am wrong here).
I will try to answer both HappyJ0 and you at the same time
Happyj0: Assume you get the bot to perfectly play (i.e. win 100% of the time against anyone and everyone) as P1. The bot now knows that all moves as P2 lose. How does it as P2 differentiate between choosing a move like 1) K10 A1 vs 1) K10 L9?
Just to be clear - the KAI (or bot) does not 'know' that all P2s lose. As P2, it discovers each time afresh whether the moves played by P1 have strong replies that have winning chances. It does not know what it will do next or what it did previously. The unconscious number crunching machine blindly plows along like a Lemming off a cliff, or potentially to an improbable victory due to P1 error.
Happyj0 ...Not just for the opening move, but for all moves. All variations lose for P2 according to the bot, so how do you get it to have a good record against humans (or other bots for that matter) as P2? Is it simply a matter of playing the variation that loses in the longest number of moves according to the bot?
This is the heart of the question. In other words, if all roads lead to a loss than how can any one move be chosen by the KAI other than by random?
The developer will not have as a working assumption that the human opponent playing as P1 will play perfectly. The working assumption of the developer will always be that human P1 will make at least one error (this may not be meaningly exploitable of course). When minimax kicks off for P2 to move, all that happens is that the app searches to the search horizon and prunes off all nodes that have terminated in P1's favour. It will be left with only those nodes that are still 'alive' and then will return a numerical evaluation of those positions for minimax and the current move that heads in the direction of that future position that rates best will be chosen.
Now, I know your point is that if the program is really a killer app then surely it would always search to the terminal nodes of the pruned game tree and will always discover that P1 wins. Well in chess software this problem is come across all the time. Complete End-game databases for all 4 and 5 piece end games have been created and the computer can play straight out of this resource and play optimally. But what if the database tells it that it is on the losing end of the chain of moves? What happens? Does it just play those losing moves? The answer is potentially yes (or it resigns), but it can also be programmed to throw in a random move to mix things up. Think about it - why would you write a program that acted like a lemming? Surely you would say "well in a situation like that, when theoretically you would lose to perfect play anyway, why would you not try some 'bad moves', something a bit crazy?" This exact strategy is routinely employed in AI programs because otherwise they can be completely moronic. I know that in real-life non-game situations where AI is used, various strategies are use such as forms of 'fuzzy logic', statistical techniques and so on to stop the AI system just going into a loop or locking up in an impasse. Another approach used in game design when the program is faced with only a bunch of bad news at the terminal nodes, is to base its minimax value on the net value of the position 2 ply prior. These prior positions will vary somewhat in their minimax valuation and allow the program to chose one path over another.
Happyj0 ...[Edit] P.S. Is there any reason to think that such a bot would have a better record as P2 than a top human would? Especially a human with access to a database of his opponent's opening repertoire....
Watsu ...How can its play as P2 against opponents other than itself be improved/optimized? Granted, it will be able to capitalize on any fatal mistakes by P1, but how will it be able to evaluate a non KAI opponent in order to seek out lines where those fatal errors are most likely to be played by that particular opponent.
There are two answers to this: 1. The KAI would win all its P1s, and might lose all its P2s against that player, because that player when playing as P1 simply plays away from those positions he/she does not play very well. In this case the KAI is at worst drawing every set. It is more likely though that due to human error and novelties discovered by the KAI for which the human has no response, that the KAI will end up with a + score against that human such as 50.5% to 49.5% 2. If you really wanted to, you could include research into the target player's tendancies into the software (this was actually done with deep blue against Kasparov). The program could use retograde analysis to determine weak moves made and map that position. It could be programmed to rank such a position high in minimax than normal for that player, thus steering the software towards this position. This strategy is fraught with problems though, since it applies an artificial value on the position that may lead the software to make suboptimal moves in order to get to that position. It could be that such a path will actually make the app vulnerable.
Okay, I think your #2 is starting to head in the direction I've been considering. I think that if it were done well, this would end up being more effective than #1. Which is why I tend to think that KAI's play as player 1 is a separate entity from how it would optimally play as P2. I may have more to say on this topic later, but for now that was the main point which I was debating.
Retired from TB Pente, but still playing live games & exploring variants like D, poof and boat
Re: Hypothetical question: Pente software
Posted:
Nov 12, 2010, 1:02 AM
P1 would be programmed the same was as P2 though, since you still have to consider the possibility, however small, that P1 might be in a position at some point where all nodes a losses and so would need to invoke the same tactics. At any rate, those tactics would be written into both sides whether they get used or not. There would not be any difference between the code when playing as P1 and P2 other than the first move being made by P1 and the opening book being the source for the first N moves.
Posts:
23
Registered:
Aug 31, 2005
From:
Iowa City, IA
Age:
52
Re: Hypothetical question: Pente software
Posted:
Nov 12, 2010, 1:09 AM
Great discussion. I have time for just one observation - I think watsu is right in the sense that the Pente AI with the best record as P2 against top humans will be the Pente AI that is the most human-aware. This can take several forms. 1) The best AI might include, and stay up nights analyzing, a complete database of the games of the top players, probing for weaknesses, determining the lines that feature the best winning chances. 2) The best AI might include knowledge of human-known Pente theory (or at least large parts of it)(as reflected in the database on this site and the archives at Brainking), would compare this to its own larger and ever-growing opening book, and on the basis of its knowledge of what opening theory is known to humans, would exploit every opportunity to steer the game early into directions that are still uncharted for humans. 3) The best AI would not resign as P2 on calculating that P1 has a subtle but forced 14-ply win. It would stick with the line that requires P1 to work the hardest (in either required number of moves, or the lines in which P1 needs to find relatively more subtle (non-obviously-threatening) moves in order to seal the win. There's probably much more to be said along these lines. Bottom line, watsu is right, the AI that wins the most games as P2 will be the one that's meanest and sneakiest, at least in terms of knowing the opponent's games and/or knowing and avoiding the lines that humans know and/or not giving up despite seeing a forced loss, but rather continuing to make life as difficult as possible for P1 for as long as possible.
Posts:
542
Registered:
May 9, 2002
From:
Northeast USA
Re: Hypothetical question: Pente software
Posted:
Nov 12, 2010, 2:19 AM
alisontate: "As far as I know, the design for a strong P2 player is identical to the P1 approach."
As others have already started doing, I'm also going to disagree with this in the case of Pente. Watsu was pointing out the role of targeting specific opponents' weaknesses. But it's more than this. In Pente, playing as P2 really is different from playing as P1. The philosophies are different, the applicable strategies are different -- the very nature of the "best" moves played as P2 have a very different look and feel from the "best" moves played by P1. If the same AI algorithms are used on both sides then that is flawed and it will not necessarily be able to play a strong P2 game. This is a very significant difference from chess, for example. In chess, as far as I know, P1 really does not have a strong enough advantage to intrinsically expect to win -- the expected outcome is a draw. Playing essentially similar styles as P1 and P2 makes sense in chess until you get to extremely high levels of play, and then the differences are relatively minor compared to Pente. In Pente, P1 is supposed to win, and it really isn't very close. Playing an effective P2 is vastly different from playing an unbeatable P1 in Pente.
The question a couple of us have posed, and are not getting very good answers for, is what happens when the AI evaluates its position to be a loss -- what move will it pick? A master level human player will attempt "subtle" or "sneaky" tactics, such as setting up a trap that is not easily seen by another human opponent, based on some understanding of how humans tend to evaluate the current position. Will the computer choose moves like this as P2 when in a losing position? From what I'm reading so far, the answer is a clear no. As Alison put it, the computer will simply use some algorithm to determine "which is the least worst move", according to mathematics -- not according to asthetics, deception, or any other human-like psychological attributes. In such a case, the math might lead the computer to play a very straight-forward move where almost all responses for the opponent leads to a loss and the one choice that leads to a win will take a long time to get there -- but here's the thing -- that one choice ends up being an obvious move in this case, and therefore the human player is less likely to make the error which leads to the loss than he might be if another tactic was used by P2. This is the aspect of the game which the "brute force" P1 algorithms will be utterly unable to perform effectively.
Because of this, the ideal, "best" possible computer player would have to use seperate programming for P2 than it does for P1.
Again, in terms of a discussion of a "Killer AI" for Pente, we really should restrict ourselves to speaking in terms of an AI that can solve the game as P1, or can always play P1 without making a mistake and therefore will always win.
alisontate: "your disadvantage here is not having worked through how minimax and alpha-beta pruning works in detail..."
Alison, you are correct that I have not worked on a specific project that uses these exact concepts, but I've already pointed out that I do have a programming background and am familiar with many of the more generic concepts upon which these are built -- enough so that I could follow the wiki link that was posted by nobium and could immediately understand exactly what is described and could even imagine what the code probably looks like. Knowing this, I still believe that people are underestimating how vast the move tree ends up being in Pente. Now there are some properties of board positions in Pente that often make the move ordering pretty straightforward. For example, if there is an open 4 by the opponent and we do not yet have any 4s made, blocking the open 4 should be the first move considered. All other choices after this can be quickly terminated since they are clearly worse moves. But not all moves in Pente are this clear. There are usually at least a few moves where there are many reasonable choices and not necessarily any forced moves -- and most of us know this is where the meat of the game is anyways for the most part.
alisontate: "the idea that pente is in some way a special case or that is more complex then we realise, is just not the case."
To me, this is the sort of statement that just shows close-mindedness and/or a refusal think or consider the ideas posed. First, I have already given an example of how Pente (and other stone games in general) is a somewhat special case -- that is, P1 and P2 are played extremely differently. This just isn't true of chess, othello and many other games -- at least not to the same extent. In addition, I believe the game IS more complex than we realise -- and perhaps I'm using the word complex incorrectly because it appears to me that the intent of my statement continues to be misunderstood. In this case, I'm not speaking of complex in the sense that it is somehow difficult for a human mind to grasp. I'm speaking in mathematical terms -- mainly in terms of how vast I believe the move tree is for the game, and also, that there are some positions that may be difficult to correctly evaluate with a logical or analytical algorithm. Which leads me to my next point of contention...
When this discussion started, I believed we were speaking of an AI which "solves" the game of Pente. To me, this means literally searching so many moves ahead that the end of the game is literally seen at the end of every possible branch of the move tree. I tried to point out how many "ply" that is likely going to have to be and how much computing power it would likely take to do this...
All of a sudden, people then are speaking in terms of an algorithm that "evaluates" a given board position, without looking any further ahead, and scores how good this resulting position is relative to hundreds of other resulting positions so that a much earlier move can be scored relative to other much earlier moves...
... No matter how you slice it, I believe that this opens the door to losing. Yes, the minimax and the alpha-beta pruning and all of these other searching optimization concepts are doing a fine job of speeding up the search and allowing the computer to look twice as deep as a non-optimized search in the same period of time ... BUT, if at some point during this super search you stop searching and evaluate snapshots of the board based on an algorithm that is supposed to fit every possible situation perfectly 100% of the time -- I believe that exceptions to these rules will crop up and cause the computer to lose at some point. This clearly happens in chess all the time. There's always that one oddball game where the computer begins playing wierd moves in response to an unconventional board position and the human takes advantage and wins. Maybe the computer beats or ties the grandmaster 9 times out of 10 -- but there's that one game where the computer misplayed one move because the positions at the search horizon were not evaluated well -- the algorithm for this evaulation was lacking in some way -- and BOOM, the computer is NOT unbeatable -- it is merely extremely strong.
alisontate: "...but the human world chess champ was beaten by a brute-force calculator that only averaged a 16 ply search depth. "
Alison, how confident are you that if this particular human played against this particular computer 1000 times that the human would NEVER win? How about 10,000 times? How about 1,000,000 times? NEVER and "unbeatable" are awfully strong words...
piecraft: "whether we can write a program that will efficiently examine the board, and perform move ordering prior to searching in order to minimise the search tree. "
I agree, this is the question. And to me, the question still comes in two parts: Are we talking about performing these tasks well enough so that the entire move tree can be solved by the computer? Or, are we speaking in terms of searching only so many moves into the future and then relying on an algorithm that evaluates the position and picks the best move accordingly? I believe that in some way, such an algorithm will be inadequate and there will be scenarios where the computer will rely upon such information and will lose a game as a result. Of course, if the entire move tree is solved, such an error would not occur -- but in this case, is current computing power adequate to do this in a reasonable amount of time? I still believe we are not there yet. So, in either case, I believe an unbeatable AI would not be possible today. But maybe soon.
piecraft: "It its not flawed at all, and there is no "baffling" going on."
Ok, you have totally missed the point.
I guess I was making two seperate statements here, both of which are valid. First, you were making a rather dismissive statement about how the AI would basically be "good enough" (I'm paraphrasing) to always win because it can search deeper than any human can, regardless of whether or not it actually searches all the way to the end. This is flat out false. If the computer is not, in fact, searching all the way to the end, then it has some search horizon and is evaluating the results based on incomplete information. It might have great skill at performing such evaluations, but the fact is, if it is only searching to a certain depth, it can and inevitably WILL be outclassed by an opponent who plays a move whose relavence does not become clear until AFTER this search horizon -- in other words, the computer will be unable to recognize the threat until it is too late. I vividly remember a widely publicized chess match several years back where the human was playing a series of pawn moves up the left side of the board to create pressure that would not actually materialize for MANY more moves -- the computer simply did not recognize it, and played one or two wasted moves, assuming that they were in a stalemate situation. By the time the computer realized what was happening it was too late. Now, if I recall, the game itself actually ended in a draw, but only because the human decided ahead of time that a draw was a desireable result (based on how the previous games of the match had ended), but in fact, the human probably would have won the game if it had continued. Now, did this human player LITERALLY look more moves into the future and visualize exactly what was going to occur dozens of moves beyond the current position? Highly doubtful. He was conceptualizing a slow building attack in a different manner than a computer who simply crunches through all permutations. He was thinking differently -- not deeper, in fact, probably not nearly as deep, and yet was able to punish the computer that was not able to search all the way to the end of the game.
Next, I was making a broad, general statement about the fact that there are ways that humans think which computers are not yet able to emulate very well. This was not meant to be confined to logic and games and math. I'm speaking of all manner of thinking -- some of which is still rather mysterious and extremely powerful compared to modern supercomputers. Some of these human abilities do indeed baffle AI programmers who wonder why their computers cannot compare.
-----------
Anyways, a lot of that might have been going off on tangents so I apologize if that's the case! You all might still be right about the possibility of creating an unbeatable Pente AI, but I'll believe it when I see it...
Re: Hypothetical question: Pente software
Posted:
Nov 12, 2010, 4:31 AM
First off, I want to thank alisontate for her response. It was not 100% what I was looking for, but it was pretty close.
My issue, and up2ng covered a lot of this ground, is that with human play there is a radical difference in how to play as P1 and P2, at least amongst strong players.
With P1, all you have to do is not screw up too much, and you win.
With P2, you know that with perfect play by your opponent that you are lost. With lots of suboptimal play by your P1 opponent, you can still lose.
The trick to winning as P2, at least vs a strong opponent, is one of two things in my opinion. You can play a "sneaky" move that isn't perhaps too complicated of a follow-up to win with a wrong response by P1 who missed the sneaky play.
Alternatively, you can win by a move that isn't so much sneaky, as it is very much complicated to find a way to win as P1. In this scenario you opponent may not find her win due to the complexities of the position.
That is pretty much the only way that you can win as P2 vs a strong human, excepting an outright blunder by P1.
For a bot as P1, you only need for it to find its win which it is handed to by the rules of the game.
For a bot as P2, in order to maximize its wins, it needs to FUD (an acronym meaning Fear Uncertainty and Doubt) up its opponent somehow. I don't see an adequate response on how it may do this.
P.S. This may be a framing mistake. The issue at hand is not how to win as P2, but rather how to maximize one's wins in an objectively lost position, which can be obtained as either P1 or P2.
Posts:
2,220
Registered:
Mar 4, 2007
From:
San Francisco
Age:
45 Home page
Re: Hypothetical question: Pente software
Posted:
Nov 12, 2010, 8:38 AM
i have not finished reading all these posts yet. i will when i get time. and not sure if this was addressed, but, we could have the AI-P2 linked into the data base, and teach it our master human methodical ways of analyzing human players to target and plot on their P1. the human as P1 would declare to the AI that a match is desired. then the human would wait for the AI-P2 to send a notification that it is ready. could take a while for the AI to prepare for the match. but, it can be the same in human situations when declaring match challenges to wait some time while studying up for it. sounds ok?
Scire hostis animum - Intelligere ludum - Nosce te ipsum - Prima moventur conciliat - Nolite errare
Posts:
2,220
Registered:
Mar 4, 2007
From:
San Francisco
Age:
45 Home page
Re: Hypothetical question: Pente software
Posted:
Nov 12, 2010, 8:57 AM
happy, you listed 2 ways that P2 can win. these are not the only ways. there are more. one example is find where their P1 wins in the db. and realize it has flaw. then hope they repeat it.
and i believe there are other ways. especially in live play. psychological tactics as well.
like in the first 3 moves, even tho you know your moves, you burn clock time and stall. make them think you didn't have a plan, or that your not familiar with their P1 offence so they think you didn't study them. keeps them from getting spooked when you want them to go predictibly positional.
also if you don't have a plan you can move very fast slapping stones down, they will get spooked and try a radical move to try and shake a imaginary threat, often times making their situation worse.
what if the AI could speak/type? and was programmed to mess with player's heads?
what if the AI had the ability to accept or deny undos for its own devious reasoning?
if certain players get into time troubles in certain types of lines, the AI could look for this?
can a AI tell if a human is a linkage style player based on data base?
can a AI tell if a human is strong at judging captures based on data base?
can a AI tell what Mechanicle trap shapes with in patterns a human is not familiar too much with by checking them in the data base?
and so on,.. i could really go on and on here...just some food for thought.
something ive learned about humans P1s is, whether they are predictibly positional, or switch it up radically, they still have a style. learn this style and use it as your advantage.
know thy self, know the board, know thy opponent.
this should be the AI's basic mode of thought.
if a master player always pulled the same line on all players as a regular way of playing as P2, they wouldnt stay at the top too long. you need to know which player should be presented with which line. you must know thy opponents to do this. this maximizes ability to have higher win percentage as P2 vs humans, thus... the AI needs to do the same.
Message was edited by: zoeyk at Nov 12, 2010 3:31 AM
Scire hostis animum - Intelligere ludum - Nosce te ipsum - Prima moventur conciliat - Nolite errare
Re: Hypothetical question: Pente software
Posted:
Nov 12, 2010, 9:16 AM
OK, I'll do my best Happyj0. Thanks for your thanks
Before responding I also want to say this. To you and Dean and other master players, I am aware that discussions about comparisons with chess, levels of complexity and suggesting that pente is not a special case may be more than a little irritating to you. I appreciate that - although you have not said this - but as you are master level players and I am a relative plodder, it would be a reasonable thing to say that I just don't appreciate the game like you do. I think that would be a fair point to make if you wanted to make it. I hope that in all of this I have not ruffled too many feathers as this is not my intention. But just as it may be a little harder for me to fully appreciate the game the way you do, equally it is hard - even for a programmer - to appreciate the operation of brute force game playing software if you haven't really worked with it.
I won't attempt now to answer all of up2ng's points, as I have spoken to piecraft and he said he will do that for me (phew!). I am getting out of my depth a little when it comes to the technical stuff.
I will simply respond to happyj0 now (and essentially up2ng) and say this: I think you sense a contradiction between the idea that a program on the one hand can play using exhaustive (or near exhaustive search) search premised on the human P1 opponent always playing optimally, with that search (if the program is as good as we are saying it is) always concluding that the position is lost. And, on the other hand, that that same algorithm simultaneously chooses suboptimal moves to try to trick the opponent in the short term.
By suboptimal I mean that the KAI perhaps plays a move that, with perfect responses from P1, will lose sooner than another move. AND - more importantly - is determined on the basis of an assumption that the opponent will not necessarily play optimal responses.
Clearly, on the face of it, we have an apparent contradiction. Although this does not address every point made by up2ng it does I think get to the heart of the problem from a software point of view.
There are some assumptions being made here about how modern minimax programs work. Please understand that for the layperson and even for the competant programmer, this is a vast field and an extremely advanced one. You would be amazed at just how sophisicated these programs are. What you see on the wiki link about minimax with alpha-beta pruning is circa 1950 simplicity. Modern day game playing software is by comparison as different as dynamite and a Nuke. The chess program I worked on with some programmers at Uni was some 30,000 lines of code. It was really intense and complicated stuff. The minimax function itself was probably 100 lines long rather than the 10 or so in the wiki article, and the function called many sub-routines along the way. Small changes in many variables produce quite drammatic variations in performance, and the great thing is there are many variables to try.
Modern software can treat all sorts of things as variables even within the ongoing search. It can for instance set the search horizon to varying depths as required by a first pass analysis of the current position. It can switch to breadth-first search on the fly based on what the current position calls for. Some programs will fully expand the game tree to 3 ply (picking a number), back-up the minimax value to now and use this information to order all the current moves for searching, and also to spot any short term traps not picked up by the first pass analysis of the current position, or errant pruning. After this initial expansion (which is stored) it can then re-expand further down critical threat lines and also lines that show an intermediate structural score than warrants further search expansion.
Based on intermediate analysis, a program can be made to dip into a preset 'bag of tricks' and explore deeply some lines that have intermediate low scores in order to find the result of the trick that may be just past the search horizon. I know I said that this approach is fraught (and it is) but it can be handled correctly and can provide good results if you are prepared to do the work.
Hash tables and transposition tables are also features of modern software that need to be appreciated. These tools reduce search time enormously and can be exploited to solve all sorts of difficult analytical problems and 'in-flight' search optimisation issues.
But even so, how exactly do we get P2 to play sneakily or with a FUD-like style? Well, the answer to this is quite simple and I have alluded to this above. Position evaluation does not have to be limited to leaf-nodes but can be perform anyway in the game tree. obviously we do not perform it on every node, but there are shortcuts available to us. There is a high correlation between the minimax score of a parent node and it's child nodes. A parent node score that is bad will - if your analysis is any good - be likely to result in child nodes that are bad also. We can also shortcut searching every node by standard pruning techniques. The thing is, we can write the program to look over a shorter timeframe (depth) and simultaneously a parallel search can be run to look at longer term strategy considerations. All of this means that such programs can be made to look simulataneously short and long term, and can be made to place greater weight on certain move types depending on how intermediate evaluations compute.
Your evaluation functions can be tweaked to place a high value on tricky positional moves exactly because these are more likely to induce and error from your opponent. But this higher value can be another program variable adjusted by the program whenever it finds that all nodes 12 ply from now are terminal for it. This adjustment will be written to apply for whichever side the KAI is playing as.
I could go on and on. The point is, until you have really worked with this stuff, it is very hard to understand how these tools have been invented to tackle an enormous range of problems. I know that the pente P1 default 100% win is a point of difference, but I am saying that based on my knowledge and experience (which is nothing compared to piecraft's), even I know that modern AI programing techniques can deal with this stuff.
So, to summarise. I am very confident that a program can be written that does not need to have a special P2 variant to be written in order to play well as P2. Having said that, I am saying that while the software would have all the same features available to it no matter which side it is acting as, there will be features that would more likely be of benefit to a P2 game than a P1 game and vice versa.
One more thing to bear in mind too. In practice these applications are written to allow different performance levels to be set for different players. Although this discussion has been about testing the limits of such a program in optimal play, just consider that for these apps it is routine to have it play 'well' (sensibly) even when its search horizon has been arbitrarily reduced. Such software copes with this by not just reducing search depth, but by also adjusting other paramaters such as breadth first search, intermediate position evaluation and short term threat analysis.
Anyway, I hope I haven't just added more to the confusion!
Posts:
2,220
Registered:
Mar 4, 2007
From:
San Francisco
Age:
45 Home page
Re: Hypothetical question: Pente software
Posted:
Nov 12, 2010, 9:47 AM
also, back to the P1 side on the AI. someone was talking about limiting the AI's search distance required through some kinda method. ide like to pose this question,..
would this possibly eliminate the AI's ability to do one of the 2 things of either, out side of the box moves, or creative adzi sequences.
because, there are certain P1 lines that require these i think.. in my opinion.
i see you guys talking with in comfort zones of straight forward AI concepts, theories ext,.. my posts are to try and pull you guys out of that comfort zone to get extra creative thought going.
Scire hostis animum - Intelligere ludum - Nosce te ipsum - Prima moventur conciliat - Nolite errare
Wow, this thing just keeps on going! The subject is a fav of mine so I'm diggin' it.
Alison first. You are doing a great job and you certainly don't need me to help you. But I will offer a little more of the technical perspective in this post.
Zoeyk, I like your creative thinking, and all your questions are good thoughts, as are similar points made by up2ng and watsu and others I think.
I agree with Alison on the difficulties around appreciating how these programs work if you haven't worked with them. I have had that problem dealing with my clients over the years! I guess ultimately the proof is in the pudding right?
There are a couple of things I want to describe for everyone so as to gain a bit more understanding of where I am coming from on this. We'll start with how a chess program evaluates a board position - well in simplified terms at least.
OK. First point is that material value in chess is paramount and you can actually write a program that can beat a 10 year old easily just by counting up material. But at the highest level, analysis of board position is a very subtle business and there are tomes written about just this topic. The trade-off is to do with choosing between the accuracy of the valuation function (its error value) and the processing cost. Some of this is addressed by better tree pruning so that you evaluate the least number of nodes and so you can expend more effort on more intensive (lower error) examinations of leaf node positions. Anyway, the main point here is that this analysis is very expensive in chess. I'll come back to this later.
Next, move generation. A move generator is a device within the program that creates a copy of the current board position in memory and then generates all possible moves that can be made for the player next to move. Let's say it is P2 next to move (this is the computer). For each move, a new copy of the board is generated in memory with the move applied to it. Then for each of those boards the same thing is repeated and so on. Now how exactly do you 'generate' these moves?
In chess you have to take a map of the whole board and compare this to the ray paths generated for each piece on it. If a bishop is in the middle of a board it has 4 diagonal rays and the application has to work out which squares it can move to. It can calculate this either iteratively (loop within a loop style) or by using bit-wise operators and bitboards. It must find which squares are blocked by both its opponent or its own pieces. Before it can move this piece it must test if this will result in a revealed check on its own King and it must know if it is in check to start with. This process is repeated for every piece currently on the board. At the end of this process, the possible moves are sorted in order of importance, such as checks and checkmates first, check blocks, captures and capture threats, pins, forks, skewers, open file moves, castling opportunities (checking for castling accross check and if either the king or rook have moved previously), queening opportunities, stalemate threats or desireable statemates, pawn advances, and so on. To order these moves you have to analyze each move and know if it is one of these. You have to test to see if something is a checking move, or a capture, of if it is a pin or breaks a pin and so on. Optimal move ordering therefore comes at quite a cost in processing, but it does reduce the game tree quite a bit. Applying these moves then requires the program to test for the consequences such as putting a king in check or out of check and so on. In short, all this takes a lot of time and processing.
Now, to generate possible moves in pente is trivial by comparison. It is a simple grid where it is possible to place a stone on any empty point. So ray tracing and bit-wise operations are unnecessary at this point. Also you don't need to know if the spot is empty or not. So move generation in chess is expensive, whereas in pente it is cheap.
Move ordering. Yes, the program could be written to recognize adzi, just as it can recognize open threes, fours and double threats and so on. It would not be hard to do this. Pre-built templates can be used to recognize positional components using bit-wise and operations. This is also very simple in pente compared to chess as all stones have the same value and cannot move across the board. While positions are not static because of the capturing aspect of the game, grid points have one of only 3 possible states - empty, black or white. It is fairly simple to test very efficiently what structures and shapes are in play. It is important to recognize that it doesn't matter how subtle or complex you want to make this, it will have exactly the same processing cost to recognize adzi as it will to recognize an open three because both are simply 2D templates. Your CPU can crunch through many thousands of these comparisons in a couple of seconds because they are bitwise operations. So identifying good move ordering is very fast compared to chess because the game much more readily lends itself to these programing techniques.
One other point worth noting on move generating in pente. We do need to consider moves that may be 6 or seven points away from the action, and this does complicate things a little since we cant just say 'only generate moves within n spaces of the outermost piece from K10'. But this is where a breadth first search - as Alison rightly pointed out - would have significant value.
To summarize the points so far. Chess is much more expensive to evaluate board positions, generate moves, copy boards, apply moves, evaluate the effect, and generate optimal move ordering to minimize the game tree. Pente on the other hand - due to its structure, simple rules, relatively static (non-moving pieces), uniform piece value, is inexpensive for evaluating board positions, generating moves and creating optimal move ordering. In chess the trade-offs between doing these tasks and search depth (and number of nodes checked) are the essence of the programming challenge. In pente though, since these tasks are comparatively cheap computationally, there are enormous advantages in search time. Generating boards and storing them in memory in pente will also be cheaper in pente to btw.
I estimate that for the same minimax search time in chess to ply 10 (5 moves per side) could generate 25-30 ply in pente, simply due to computation factors.
Now, a couple of other factors.
In chess, very often it is possible to arrive at the same position with different move sequences. This can occur any time during the game potentially, but is particularly true in the end game. To avoid researching the same recurrent positions over and over, the program uses hash tables to store previous scores for the same position. The hashing operation though is problematic because it must store the board position. This not only uses a lot of memory but checking the table can be more costly then just re-searching position again. Shortcuts are used in the hashing process which introduces small errors here and there. Now because chess is costly to re-search and then re-evaluate all the end nodes, hash tables are used extensively even though they are costly.
In pente hash tables would be a far simpler affair again due to the nature of the game. storing and checking a hash table would be much more efficient in pente. This could also help reduce the number of board evaluations more readily than in chess in with more accuracy.
For an equivalent standard or play (subjective I know) memory costs for a pente app would be far less than chess.
Now to get to up2ng's point about complexity. This seems to be a sticking point. Let's expand on this here. By complex what I mean is that there are interrelationships between things, and interdependencies, predecessors, differential considerations and valuations, deep sequence dependances and so on. I know that pente has these too, but - and I don't want to offend people here - in my opinion chess is well beyond pente under this definition of complexity.
It you consider this purely in terms of permutations and combinations, then chess is still move complex. At any rate, as described above, the sublime efficiencies afforded by the nature of the game itself and its suitability for conversion to an AI app, means that the permutations and combinations are a trivial thing for a modern program to swallow.
So, yes a well written pente app can perform far more efficiently than a chess app. This gives you advantages of written far more subtle and clever evaluation functions where the subtleties of adzi and other concepts can be divined. By comparison, a chess app of the same power would be a lumbering leviathan.
That's enough for now. On my next post I will address more directly the 'top down' thinking expressed by zoeyk and others. Here I just wanted to address the issue of relative performance of the killer App and a chess app.
Thanks again Alison. That was most helpful, especially this bit, which basically answers my question:
Your evaluation functions can be tweaked to place a high value on tricky positional moves exactly because these are more likely to induce and error from your opponent. But this higher value can be another program variable adjusted by the program whenever it finds that all nodes 12 ply from now are terminal for it. This adjustment will be written to apply for whichever side the KAI is playing as.
Zoey,
Thanks for the additional methods of winning. The past opening repertoire is in particular something that I should have added, however I was thinking in terms of winning vs a generic opponent so it didn't come to mind.
Great points about the relative speeds (number of operations required) of performing move generation and move ordering in chess vs. in pente. I had not really considered just how much more computation is required to build the same size tree. In CS 101 when you are taught about evaluating the speed of an algorithm and you talk about things like O(n) or O(log(n)) and so on, of course it's important to remember that two functions performing at O(n) might take vastly different amounts of time if the "n" you refer to is taking hundreds of times more operations to complete for one algorithm vs. the other! Of course, even a big disparity like this becomes insignificant as n becomes large compared to what would happen if you had, say O(n) vs. O(log(n)) or whatever, but the point is a good one and I was not really factoring that in appropriately. (My CS terminology is failing me at the moment, lol) Furthermore, I have to agree that move ordering would be much stronger in pente than in chess so that you probably do get closer to the O(log(n)) example vs. O(n) (I'm making these examples up cuz I forget what the best case / worst case actually is with the alpha-beta pruning...)
Plus, the more I think about it, the more I agree that for at least half of a pente game, the number of reasonable moves to consider is relatively small. Often times P2 has only one or maybe two options, and other times there might additionally be a few outside the box moves available, but would probably still be at most 5 - 10 moves available. P1 often has more options than this, but not a whole lot more "good" options really...
I guess this would be sort of equivalent to a situation in chess if every move of the game (after the opening) resulted in putting P2 into check -- P2 then has very few options available for that next move, each step along the way. Of course, chess is generally less forcing than this (although a lot of chess games do have a rhythm where some sort of threat is always being countered by the one or two possible moves which can adequately deal with such a threat...) and so there are probably often a lot more moves to consider, and the move ordering is probably a lot less accurate.
Do these factors really translate into a 10-ply chess search taking the same time as a 25-ply pente search? I'm not so sure about that, but the point is well taken that it is indeed a significant difference.
I guess I'm coming around on the idea, Piecraft. You have been very persuasive. But I still have the same two questions:
1. Do you really think that these optimizations are enough for a standard PC to have enough power to perform a 54-ply search to effectively solve the game within a reasonable amount of time? Say, within a 20 minute timed game?
2. If not, do you really think an algorithm can be developed that takes snapshots of the board (at some future position at the horizon of the search depth) and can correctly score the board state to determine if it is a winning or losing position which will work for every possible scenario?
As I said, you pretty much have me convinced -- the problem is that I'm just not seeing either #1 or #2 happening, although I'm starting to think that #1 might be possible with some serious optimizations...
Back to the same/different Ai for P1, P2 discussion. The core part (building the tree) is the same regardless the unbalance between P1 and P2 in pente.
Evaluating the tree is an other question.
As I see most players think a human like AI, at least as P2 would be stronger than a comp. like. This can be true, but can be done with little effort compared to the main part of the AI.
@zoeyk - pokerbots already "chat" with their opponents
The AI as P2 seeing all lines as lost, doesn't necessary mean, it will lose the game. Playing the longest line will put the human player under pressure, raising the probability of a bad move. (as many lines are forced in pente, a mistake means a loss in many cases)
Compared to chess, pente is much simpler. A chess program can easily find mates in 50 moves...
I think the only reason pente isn't solved yet, is the relative low popularity compared to gomoku, renju, chess.
@up2ng - I'm not really sure about the complexity of pente. It may be complex to the human brain, but for an AI it's not different from any other game. At the end the captures could make the game less comlex, and not more comlex.(compared to renju)
Although we can't be sure about this until the game is solved
We have to differenciate what kind of a program are we speaking of.
-brute force or -using an advanced algorithm +using an opening book +using a game database +adaptive to the player's style +confusing opponents with chatter +causing power failure at he home of the opponent +ruling the world
I think most people would like an AI wich is FUN to play, it could even let the opponent win a game or two.
+causing power failure at the home of the opponent lmao ..haha thats funny. i forgot to list that one.
i think it would be great if the AI-P2 would make insults. your mama jokes ext.. hehe some players abilty to play is altered by emotions. for better or for worse.
Scire hostis animum - Intelligere ludum - Nosce te ipsum - Prima moventur conciliat - Nolite errare
(Pete, please correct me if I am wrong here).