Reading this thread makes my head hurt. You guys + gal are way too smart.
Pete said: "1. It is possible now to write a pente program that beats ANY human player running on a standard (upper middle range) PC. Currently world championship chess competitions exist with Grandmasters and PC software playing as individual entrants against each other. PC software now frequently beats the best players in the world. Chess is far more complex than pente with game-tree termination horizons several times the depth of search horizons, so to create a program that can win all games of pente is not an issue."
I agree! It just takes getting the right talent interested in taking on the project. Money was the incentive for Chess, there will have to be a different motive for Pente. I'll bet that Pete and Alison could make a very good Pente program . . . but what would motivate them to do it?
piecraft; 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.
zoey; adzi is not a move. it is a concept, and it is a sequence of moves, some times the sequence is split into sections with none adzi moves inbetween pausing the adzi sequence and then resuming. this is in no way the same catigory as see a open 3/ or 2D template as you call it. in my opinion. perhaps i have not posted good enough examples yet of this in the other thread. nosovs had warned me that most players would have a tough time with this concept of his in pente.
Scire hostis animum - Intelligere ludum - Nosce te ipsum - Prima moventur conciliat - Nolite errare
picraft; On my next post I will address more directly the 'top down' thinking expressed by zoeyk and others.
zoey; ahh ok i forgot to mention that one. yes another important one to think on. but there are 2 different forms of this. i have a feeling your not meaning my concept of reverse engineering. but more your meaning to work backwards from end game to K1o direction. reverse engineering requires putting stones to the side, watching what the opponent does, and then slide in the stray stones in a (sometimes very creative) methodical reverse order to solve it. this is generally a 3-5 stone order found in either the opening-early mid, or just in the mid. and this can be done by both P1 and P2 but, the thinking will be a little different when switching sides with this method generally.
Scire hostis animum - Intelligere ludum - Nosce te ipsum - Prima moventur conciliat - Nolite errare
Re: Hypothetical question: Pente software
Posted:
Nov 13, 2010, 1:28 AM
I am no expert of adzi but tell me, how do you recognize a potential adzi situation? Surely we have stones on a board and the relationship between them is implied by their location? There are sophisticated techniques - particularly neural-nets - that are very good at extracting this sort of information. For example. You could train up a NN on 1000 different adzi positions and get it to recognize them. The neural weightings can be extracted into a function for adzi detection. There are many very clever techniques for this sort of thing.
Btw, top-down verse bottom-up is not to do with reverse engineering which is otherwise known as retrograde analysis.
The problem as you describe it zoeyk is also that adzi is kind of a 'running theme' through a game or subsection of it. That there are positions within a sequence of moves where it can be ignored, or perhaps disguised. I understand this. The thing is, many abstract games have these features. In chess, detection of pending situations and short, medium and long range threats is part of the standard evaluation. There are other games where the conditions of a board situation from several moves ago have to be stored in memory because later on the program cannot tell how the game reached the current point and that information affects what can be done next. In Othello, where - unlike what most people think the game is about - the objective is to limit your opponent's options to as close to nil as possible, there are all sorts of subtleties around edge acquisition sequences and so on, and all of these can linger on for many moves. Believe me, the experts in these games make all the same kinds of points you are making, and pretty much the same software with a few tweaks can solve all of them.
I would be happy to find that adzi is some sort of unique thing because this would make it an interesting challenge, however I don't expect it to be very different from similar considerations in other games.
To make a few comments about top-down verses bottom up approaches. The points made by many of you about studying the opponent, second guessing them, dealing with the pre-game psychological stuff, and for that matter the psychology during the game, the emotions of fear and so on. These are all loosely under the heading of top down considerations. These are very human ways of looking at the world.
For program playing as P2, your question is also about the kinds of moves you make. Consieration of many of the moves played by human P2s and also the mm_AI program reveals a commonality. That is that P2 moves are often of the following types (or combination thereof). Either they are * Blocking moves * Containing moves * Prophylactic moves * Counter-threat moves (I am sure you guys can add to this list but you get the gist of what I am saying). These are move types that are not unique to P2 but in fact are simply the kinds of moves you make when you don't have the initiative, and perhaps just trying to forestall the inevitable. But what makes you think that a pente app would not make the same sorts of moves when playing as P2 or when it does not currently have the initiative? If these sorts of moves are appropriate in a given situation, then look-ahead search will identify this because accurate minimax will score these moves higher than others. The effect will be that kinds of moves played by the pente app as P2 will look eerily similar to most of what is played by humans.
I think a lot of what Alison said about ways in which the program can be tuned to consider intermediate evaluations and breadth first search is very relevent here and will further address the P2 playing approach issue.
In the top-down world of people thinking. There is always this concern expressed by human game experts that you have to try to mimic the way that human masters think about the game. History has unfortunately shown otherwise. All attempts to create top-down only AI game software have failed when compared to brute force bottom-up methods.
One key difference between pente and chess which I think has not been discussed, but which is important what I will call the Zebra factor. I think that pente is harder to 'picture' future positions beyond 8 or 9 ply than chess. I am no great shakes at chess, but can play an OK game, but I know that I can see much further in a chess game than in pente. I think this is because of the homogeneous nature of the pieces. Holding many similar future options in your head and evaluating their merits is not so easy in a game without so many distinctive markers against which to anchor your visual memory. In chess, it is possible to imagine future high level structures many moves ahead and fill out the blanks in between with shorter range tactical search anchored to key pieces and pawn structures. When trying to do this in pente you find that it all kinda looks the same and it is all a bit confusing. I think of this as camouflage. Zebras don't blend into the Savannah landscape but instead blend into each other, often confusing the whiskers off the Lions, and it is the same with pente beyond a certain ply depth (this is obviously different for different people). The result of this I think is that human pente players have to resort to thinking about the game differently, and preparing differently. Greater emphasis is placed on current master level lines and possible new secret variations. I think this is because it is just so hard in real-time play to actually think through the implications of a new variation when seen for the first time in actual play. In chess, this does occur of course and players do prepare as well, but much more emphasis seems to be placed on your knowledge of positional themes and the use of tactics to counter new ideas being thrown at you.
Naturally, because of this, strong pente players don't readily believe that an AI program could be effective without doing the exact same thing. What I am trying to get across is that because the AI is essentially immune to the zebra problem, and it can search quickly and deeply, it does not need to rely so heavily on preparation.
The bottom up approach says that if we simply efficiently search all the options (with pruning of useless alternatives) then we will find the best lines without all that preparation. Of course this entirely depends on the quality of the search, and how fast it can be done, but as per my previous post I am very confident on this front.
Niobium's points are well made. The fact that a completely dominant pente app does not exist already is purely lack of interest. Whether it is due to popularity, money or whatever doesn't matter. It can and will be done.
Posts:
2,220
Registered:
Mar 4, 2007
From:
San Francisco
Age:
45 Home page
Re: Hypothetical question: Pente software
Posted:
Nov 13, 2010, 2:53 AM
your zebra has merit, but im not so sure of your conclusion that a AI being immune means that all the human stuff is a moot point.
lets say you will face 2 opponents. the names are blue and red.
and you have 2 lines prepared as P2. both lines will lose in perfect play. but the opponents are not perfect.
now, one of the two losing lines is stronger than the other by AI standards. line number one is stronger than number two.
ok,.. now,
Red player will beat line number one, but will lose to line number two.
and the reverse is true for blue player. he will lose line number one, but he will beat number two.
there was a way that a human could had predicted this out come. and thus the human uses line #2 on red, and uses Line #1 on blue,.. result human wins both sets by using 2 different lines.
if the human used only the stronger line, the human wins only one set but ties the other.
so,.. some time the stronger looking line is the wrong way to go. the AI wont know the difference if it doesn't understand the opponents.
does any one agree here?
Scire hostis animum - Intelligere ludum - Nosce te ipsum - Prima moventur conciliat - Nolite errare
Re: Hypothetical question: Pente software
Posted:
Nov 13, 2010, 3:43 AM
up2ng, thanks for your open-minded attitude, and also for your insightful 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?
Self-generated opening book to 12 ply leaves 42 ply remaining. You don't need to search the whole tree the remaining 42 ply, but only a small part of it. This is for the following reasons. 1. On move 7 (ply 13 from the start) your worst case would be searching 42 ply, on move 7 you search 40 ply, move 8, 38 ply and so on. If all games paths went to 42 ply from end of book you only have to search on average to 21 ply. 2. Optimized search will come close to cutting the game tree in half breadth-wise. So this leaves only half the total game tree to search to 42 play from move 7. 3. The vast majority of games don't exceed 40 ply in total. I am only guessing here, but let's say that 10% of game paths might exceed 40 ply total and perhaps 1% reach 54 ply. So how many positions at move 7 will have possible (and viable) paths to a further 42 play beyond this? Not very many is the answer. 4. All games end in a series of forcing moves. The sequences can be between 2 and perhaps 10 moves each player (lets say an average of 6). This means that for large parts of the game tree working backwards you find that there is no branching. This makes an enormous difference to the size of the tree being generated. Due to this factor, a pente game tree of depth D will have an average non-branching depth of D - nb, where nb is the number of ply where there is only one or two possible moves that still lead to a forced loss or win. Using my above estimate, from move 7, the actual maximum branching ply depth might be only D - nb or 42 - 6 which gives only 34 ply of branching. 5. Along the course of the game tree many paths will terminate early. So as per my point 4 above, the game tree self-prunes. As you agreed the tree is very narrow for much of the game for many games. 6. Pente has translational, rotational and 2 x Axial symmetries. Transposition and hash tables will greatly assist pente much more so than chess. In fact this will in my opinion reduce the average number of nodes to be searched by at least 50%.
If you add together the above considerations you will see that the game tree search task is far less daunting that you might imagine. In fact I think it will be really not that big at all. So to answer your first question, and with consideration of the above points and my previous posts, I think that real-time exhaustive search is a very real possibility.
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?
Well, assuming for a minute that exhaustive search is not always possible. It would only be not possible for a very small percentage of games. But to answer your question, the accuracy depends on two things. 1. The quality of the programing of the evaluation function (this is where masters advising developers comes in) and the processing overhead of that function. In my opinion, this evaluation function would only need to be called a minimal number of times during play and so could be a fairly comprehensive test with a high degree of accuracy. Remember also that if we don't always have exhaustive search than the evaluations would be done at points pretty close to the end anyway and would no-doubt detect forced lines and at least a cornucopia of threats which have usually built up. Detection of this stuff is computationally and quantitatively simple to do. I don't foresee much qualitative analysis being needed at that point. One more point worth remembering here is that as you have said, in reality it is not even that close between P2 and P1 and so it should not in theory be that hard to identify the strength of a future board position. If you follow my thinking here.
Re: Hypothetical question: Pente software
Posted:
Nov 13, 2010, 3:49 AM
No, zoeyk. One does not agree here. The program will simply play the best move no matter the opponent. If a best move is ultimately just that, it will win anyway (or be the strongest defence in the case of P2).
Posts:
2,220
Registered:
Mar 4, 2007
From:
San Francisco
Age:
45 Home page
Re: Hypothetical question: Pente software
Posted:
Nov 13, 2010, 4:18 AM
> No, zoeyk. One does not agree here.
oh?
>The program will > simply play the best move no matter the opponent.
yes, i agree, thats the problem of the current AI as P2.
>If > a best move is ultimately just that, it will win > anyway (or be the strongest defence in the case of > P2).
first, i was Not speaking of a AI-P1. i was just refering to a AI-P2 to be clear. and the strongest line for a AI is not always the strongest line to pull on a human.
so i'll need to disagree there i guess.
> You are thinking like a human again!
agreed, which is what i think a AI-P2 is lacking to maximize set based victories vs multiple human players.
Scire hostis animum - Intelligere ludum - Nosce te ipsum - Prima moventur conciliat - Nolite errare
i dunno,. ive been reading alisons posts, and so far im not seeing any thing that makes my point moot.
there is not many forced longest lines any ways except wedge or boston as basic examples that we have already solved,.. white just switches its second or third in 99% of openings and the AI_P2 will not be going too far. the AI-P2 needs to use different tactics in pente. if the strength of your AI is based around length it will be weak i believe. i realize you guys talked about other concepts too, like when there is no win the AI makes some random crazy move out of the blue to then pray for a miracle, but it seemed to be so much emphasis on longest lines as the main deciding factor for the AI-P2. it might work in chess, but pente it is more simple, so instead of focusing on the board, its better to focus on the player. the board doesn't always have error, but you can find it hiding in the human's mind if you know how to persuade it. I strongly think nosovs will still hold a higher P2 win ratio than the AI-P2 will... the AI will be missing a special component in my opinion.
i think we can all agree that a perfect play AI-P1 can be made. sure no problem...
but when it comes to a AI-P2 that will be better than any human player at beating humans, you can talk about amazing new advancements in the AI world ext..., but until you prove it by making it and having it earn its reputation there will be a couple skeptics such as my self. im not saying you can't do it, but i am saying i doubt it, unless you are replicating human thinking to add to its tactics of course. imho
Scire hostis animum - Intelligere ludum - Nosce te ipsum - Prima moventur conciliat - Nolite errare
and, correct me if im wrong, but deep blue only won the last set because the human mind became exhausted and didn't want to think that hard after that many games.
resilience of the human mind is another issue. computers don't get tiered. if they just did one set it would had been a tie. i don't think the brute force deep blue example proves a AI-P2 can be superior to a human other than long term resilience. and what if instead of playing each other, they played other human masters? the ratio of P2 wins could had gone in the humans favor i think.
and, deep blue was not just brute force, but it also had a human played data base to search. i believe you guys were saying a data base would not be required.. for the P1 sure, but for the P2 im not so sure its best to disregard this tool.
Scire hostis animum - Intelligere ludum - Nosce te ipsum - Prima moventur conciliat - Nolite errare
Re: Hypothetical question: Pente software
Posted:
Nov 15, 2010, 2:28 AM
zoey, if I was designing the program, I would sit down with you and ask this question "zoey, when you think of a move designed to trick P1 into error, what is your thought process? What characteristics does such a move have, and in what board situation can you create this sort of move?" (Setting aside for a moment any player targeting)
I expect that if you can answer that question, then it can be programmed.
Posts:
2,220
Registered:
Mar 4, 2007
From:
San Francisco
Age:
45 Home page
Re: Hypothetical question: Pente software
Posted:
Nov 16, 2010, 11:15 AM
hi again, so, i'll start with 2 things here. firstly, i take no offence to someone saying that a AI-P1 can surpass the greatest human minds in the world in terms of a geometric board game with out requiring understanding of the human mind. this is acceptable in my opinion.
second, when it comes to saying that a AI-P2 can surpass the greatest human minds in the world with out requiring any understanding of the human mind, i found this personally insulting to my own potential and like wise for the human race in general.
was i right to be offended? im not sure.
it seemed i was being disagreed with, where the majorities stance was that a AI-P2 vs a human master's P1, (where the only way to win is through the human's error), (and that the AI-P2 didn't require understanding of human's mind), could play P2 better than a human master vs human master could. That a AI will have higher odds of defeating human masters than a human master could playing as P2.
this didn't seem very logical to me. and also has a stance that states a limit on human's capabilities, thus setting our bar kinda low as far as hopes of human greatness.
a human master spends a chunk of his life mastering a game, and along comes some people that don't even require knowing the game, they just script some code and all of a sudden the human master is obsolete? replaced as useless...?
should it bother me? i don't know...
next, then if switching the stance of the majority to then say, ok we still think a AI-P2 can surpass the human, but admittedly we will need to teach it how to understand humans, which still is a easily obtainable goal, says the programmer.
this both scares me and offends me. on one hand, perhaps its true, maybe it can be done, and i would not sit too well with this for some reason. second, to say that a soulless piece of metal and plastic, can understand even the deepest depths of the human mind to understand the human mind even better than the smartest human on the face of the earth, i find insulting to humans, and i still think it can't be done any ways. you can synthesize it to an extent, but to teach it everything about human's minds is rather far fetched.
now, im not sure what the current stance on this is by alisontate for example. seems now she thinks a AI-P2 would require human understanding to surpass. but although she had said now that she'd ask me for my ideas, it doesn't mean she thinks understanding the human mind is required for the AI-P2 to surpass. so, im unclear on where she's at there. I'll further say that there are other masters that are better than me. so im probably not the first guy's door you should knock on for the info if trying to script such a AI thinking. although, sure, i have some ideas i could contribute to such a project.
any how, i just want to say im sorry for interrupting you guys. i realize i haven't much to offer about AI coding knowledge. and i realize you all had a great flow going on here, with all kinds of friendly agreeances between all. so ill back out of the discussion and let you guys get back to your flow. sorry.
z
Scire hostis animum - Intelligere ludum - Nosce te ipsum - Prima moventur conciliat - Nolite errare
