Posts:
23
Registered:
Aug 31, 2005
From:
Iowa City, IA
Age:
52
Hypothetical question: Pente software
Posted:
Nov 3, 2010, 2:14 AM
Imagine that you develop some really good Pente software. It's much faster and smarter than Mark Mammel's Pente software (hard to imagine, I know, but this is a thought experiment, so just play along.) It can beat Nosovsky most of the time. It comes awfully close to solving the game, seemingly unbeatable as P1.
What would you do with it?
1) Keep it to yourself, and use it to play your games and tournaments for you, gradually taking over the #1 spot on Pente.com and Brainking.
2) Keep it to yourself, and use it just to *prepare* for games and tournaments by a) developing and memorizing a great opening repertoire, and b) probing for and exploiting weaknesses in the lines played by the top players.
3) Use it to play games and tournaments, but make it clear to all involved that it is computer software playing, not you. Those who want to take on the great and mighty software can do so, knowing they're doing so. Whether it would be allowed to enter a tournament would be up to the tournament director.
4) Share it with the world, letting anyone and everyone use it in any way they like.
5) Pat yourself on the back for your accomplishment, and then shelve it, neither using it yourself, nor sharing it with the world.
My thoughts:
1) would be unethical and, I think, fairly pointless.
2) would be ethical in my opinion, and consistent with the rules. But would it be satisfying, knowing that your high ranking is based on preparation that's helped significantly by a technological advantage that others don't have? I don't know.
3) would currently be my choice. Though I'm concerned that the more games the software plays, the closer Pente comes to being solved - and that could lead to declining interest - and that would be sad for those who love the game.
4) is an apparently generous, sporting thing to do. But would it be good for the game? Or would it kill the game? Anyone could use the software to play world-class Pente. Good thing, or bad thing? And if it would kill the game, because of so many early forced lines being at anyone's fingertips and/or easily discovered by anyone, does that mean Pente simply deserves to die, as its former devotees switch to something less nearly solved, like 9x9 Go?
5) is perhaps the way a true altruist might go, like Gandalf and Galadriel turning down the Ring, keeping the dark and powerful secret dormant rather than a) using it to dominate all others or b) making its discoveries available to all and, in doing so, taking the risk of ruining/almost solving the game.
What do you think? Which of the above (or are there more than these five possibilities?) would you go with, and why?
Posts:
2,233
Registered:
Mar 4, 2007
From:
San Francisco
Age:
45 Home page
Re: Hypothetical question: Pente software
Posted:
Nov 3, 2010, 9:21 AM
interesting topic. most people don't have a computer strong enough for this imaginary program. even my 8 cpu computer would choke. what would i use it for,.. there is a certain type of position i would use it for. but defining this type of position is difficult. all i can do is show an example of a specific position where a AI 12 with VCT was used. and it ended up destroying a common P1 3rd move through presice exploit of an error the 3rd leads to by force. so, it would only be used for a special type of position to find only one move in the line. all other moves in the line would be figured out using the human mind. this is for me, in my opinion. and this is not for while playing, this is only for studying on the side. would i share it? yes, probably, but only with very select people. people on the same page of mentality as me. absolute power corrupts absolutely, and if in the wrong hands, the game would be ruined for many, but not all. circles of players would become divided. segregating from the AI type players. and any player whos very good would be suspect of using the AI. now if the AI was known to play a certain way always as P1 then we could easily ban those moves. but if the AI can be preset manually to a position then ordered to run from there, then we could not tell the difference. will this imaginary AI become real one day? yes i am almost certain. a very strong algorithm programmer will come along, and super computers will become cheap for average consumers. eventually people will find the need to play live OVER THE BOARD. which is how it is supposed to be any ways. internet pente although much more amazing moves generally, is some what artificial in my opinion.
in addition, i think that this software should be designed where no matter how fast your comp is, the AI is not allowed to give you more than one move per line per week. this limits it from being used for destroying pente. if this type of safety feature is not in place then the AI should be erased, in my opinion.
zoeyk
Scire hostis animum - Intelligere ludum - Nosce te ipsum - Prima moventur conciliat - Nolite errare
It would be difficult in practice to enforce a 1 move in a line per week limit, I think. I can think of three ways to circumvent such a limit off the top of my head as I type this. No doubt there are others as well. As to the choices involved, since I'm replying to Zk's post I can't see them but...
I believe I would market and sell the program at any stage in computational power where it would actually be useful in practice. Granted, this would likely kill pente as it is currently played online to a large degree.
However, I believe that there are enough possible variants of N in a row games with captures, swaps, poofs, added dimensions, etc. to make it difficult to come up with a universal N in a row killer program within the next few years. So, at least for a few years, N in a row games would basically be similar to chess as it is currently played. Computer preparation is an essential part of the highest levels of chess these days. No doubt there is a significant amount of online chess computer assisted play. Which is why for a rating system to effectively distinguish between different forms of intelligence, there needs to be a way of insuring what intelligence(s) are allowed and involved in the game. Probably OTB, as Zk says.
Being aware that there exists at least one program which can beat MMammel's (as to regularly beating Nosovs, IDK) I would say this question isn't a moot one. Of course, anyone who has and uses such a program - if it returns an improved move in a line - will never be sure that the same move made by an online opponent was one made solely by human thought power.
The fun would go out of a game for me personally if I had access to a program which consistently found moves at least as good as my best efforts, but that's just me speaking personally.
Retired from TB Pente, but still playing live games & exploring variants like D, poof and boat
http://nosovsky.narod.ru/index16.html You can dopwnload Victor Barykin (lancer) program 2.4 This version of program lost Mammels program, but as I know version 2,6 or 2,7 won against Mammels software. As I know all versions need to be improved because of some mistakes during playing. It is big job to make software which always play correct. we had discussed with Victor possibility to improving his program , if it'll be a company which want to buy it. Just working on software 6 months is minimum 30 000 USD. Anycase the program level is under 2100-2200 rating . So, to produce such software is useless until we can not find who need this software and ready to pay
Does anyone have any links to articles which describe contests between Pente AI programs? How was the contest conducted? What were the rules? What criteria was used to determine which program won or lost?
For example, if you were to allow two AI programs to play a single set of Pente to determine the winner (assuming one side won 2 - 0) then the results are highly suspect. The reason is (at least in the case of mmammel's AI) that the opening book varies very widely between strong and weak openings and one of these openings is generally chosen at random for every new game. There are plenty of times where mmammel's program plays directly into a clear losing position as player 1 before the AI algorithms even get a chance to run. Clearly this would have a serious impact on the results of any one game.
In a way, I believe that an opening book like this is included by design -- it allows for the casual user to play against a very wide variety of openings in order to enhance the learning process and to keep the game fresh.
In order to make the program truely competition ready, its opening book would have to be reduced substantially to include only the best possible openings as agreed upon by Pente masters -- and I have a feeling that was never done prior to any competition.
agreed. the results are suspect. to do a true comparison of algorithms both AI's would need to be required to use the same opening book. or none at all for either. opening books are human tampering which can tie down the algorithms ability to show its true potential.
Scire hostis animum - Intelligere ludum - Nosce te ipsum - Prima moventur conciliat - Nolite errare
Re: Hypothetical question: Pente software
Posted:
Nov 8, 2010, 7:07 AM
I have a bit of knowledge of this subject. I can say a few things about this with some confidence.
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.
2. The cost of writing a killer pente program would be 30-60K USD at a minimum.
3. It is inevitable that such a program will exist. Some IT Masters student somewhere will write it for sure.
4. Such a program would play itself and generate its own opening book. This book over time would become closer to perfect than any human could achieve.
5. The search horizon on the program could exceed 14 ply, meaning that 90% of games could be solved to perfect play from K12. The rest would be solved to perfect play from the 3rd or 4th move.
6. As there are probably many possible perfect lines from many 3rds onwards, the program could randomly choose from any of these. So, it would not be easy to be sure if you were playing this killer AI other than from never being able to beat it.
7. This has the same ethical considerations as drugs in the Olympics. Yes its cheating, can we ever stop it completely? No. Should we just 'allow' everyone to do it - may as well. OTB play is the only way to be sure (except for hidden ear pieces!).
The only other question is, would it destroy Pente? Maybe at the top level and in tournements, but for most other social players i don't think it will matter.
I don't necessarily disagree with some of your points piecraft, but the chess/pente AI comparison is not currently a valid one- since basically the dawn of the computer era one of the tests of computers is how well they can play chess. Even when they were so basic that they could only handle a 6x6 board, they've been playing chess. Now, if we had 50+ years of Pente AI funding, programming and refinement, then yes such a program would already exist. However, what we've had so far is maybe a couple of dozen Pente AI programs over the years, most of them performing very poorly against a good human player. The genetic AI avenue was explored in one of them, but for whatever reasons (probably insufficient iterations) it was horrid. Currently, there's just not the financial payoff to write a killer Pente AI. We don't have the computer speed benchmark people behind us, nor do we have the pool of grandmasters who can make a living at the game- whether through government subsidies, exhibitions, prize money, chess columns, etc. And, we also don't have nearly as many books on theory... another source of income for chess masters and grandmasters.
Having said that, I would say that there are probably roughly a dozen or so current and former pente players who - in collaboration with excellent programmers and sufficient funding and a year or two- could come up with a program which could probably beat top level players 6/10 in two days per move games. Perhaps even more. Solving the game by brute force, on the other hand is, I think a few years away at current processing speeds.
Retired from TB Pente, but still playing live games & exploring variants like D, poof and boat
Posts:
23
Registered:
Aug 31, 2005
From:
Iowa City, IA
Age:
52
Re: Hypothetical question: Pente software
Posted:
Nov 9, 2010, 3:35 AM
piecraft - your confidence in all of your points seems well-placed. As someone who's been a professional programmer for 20 years, and who's currently waist-deep in the spare-time project of developing a killer Pente AI - which is the reason I asked the hypothetical question - here are my thoughts on your seven points: 1) Right. I think it is possible now to write a Pente program that beats any human. 2) This is your only observation that I disagree with. It needn't cost 30-60K USD. I'm doing it in my spare time - the cost will be basically zero. If mine winds up not being "killer," some other Pente-and-programming enthusiast will write the killer Pente AI in their spare time. 3) Yes, it will exist. 4) Yes, well-written Pente software could spend *its* spare time continually exploring lines, growing/refining its transposition tables and opening book, continually approaching perfection in its theoretical charting of the game. 5) I agree, the vast majority of lines will be solved from the first couple of moves on. 6) I agree, the software will usually have many forcing options from which it could choose randomly, thereby disguising its identity as software if desired. 7) I agree, the only way you can be sure you're not playing against a computer (and this is true even now) is by playing OTB. (Anyone up for an annual Pente U.S. Open in, for example, Chicago?) And finally, I agree that top level Pente would probably suffer - casual/social Pente, not so much.
Re: Hypothetical question: Pente software
Posted:
Nov 9, 2010, 6:22 AM
I suppose we should probably clarify what is meant by "it can beat Nosovs most of the time". Of course, this can't mean most of the time as P1, since that wouldn't be at all outstanding. So, in terms of Pente sets, what would most of the time mean? Taking 2/3 sets from him on a regular basis? 3/5? or are we talking about 51%? That's still beating him more than he beats it, but would basically mean that he plays nearly as well as P1 as the killer AI does. Because, with the P1 advantage, a program would need to be incredibly better than the very best human players in order to beat them more than 2 sets out of three. Playing perfectly as P1 isn't enough to set it well above any human player, it would also need an extremely mean and sneaky P2 game. Otherwise, it would win all its P1 games and whatever fraction of its P2 games an error was made in.
Retired from TB Pente, but still playing live games & exploring variants like D, poof and boat
Re: Hypothetical question: Pente software
Posted:
Nov 9, 2010, 6:26 AM
Watsu, you are right about the AI endeavour being, from its inception, one of creating a chess program to beat the human world champion. However, the AI field since has broadened its focus. In fact, the first Checkers program to beat the then current world champion was written in the 70s. Checkers is not as complex as pente but is not far behind. Games such as Othello, Backgammon, Connect-4, and many non-commercial games have been conquered by AI and are currently unbeatable by any human player.
The great weakness of pente as a game is it's shallow game tree. Sure, the game tree is broad, since on the first move for P2 there are (19x19)-1 places to drop a stone, but smart software gets around these issues easily and confines the search breadth (or branching factor) to a very narrow subset. The total game tree then is well within the capabilities of modern PCs and certainly much smaller than many other games including chess.
Effective opening books could easily be generated with AI V AI play around the clock. After a few months of continuous cycling I expect a near perfect opening book could be generated to Move 6 or more. There are a range of very clever techniques to do this which can be borrowed from AI programs of other games. In my opinion, self-generation of the opening book would remove the need for master level input.
Genetic optimisation of leaf-node evaluation functions may be useful but I doubt it. Pente is far less interpretive than that, and besides rather then evaluate leaf-nodes with a set of functions it would be far better to just re-invoke minimax search from that position until terminal nodes are reached for each response (I am talking here of opening book generation, not real-time play).
The question will not be if P1 perfect play can be achieved. For me this is a given. It is more to do with how it deals with near-perfect P1 lines from human players, particularly if these lines are not in the opening book. This is the real test of the killer AI. Its ability to calculate the error in a near-perfect P1 and then find a winning exploit on the fly will be the thing. But I think this is entirely possible based on what I have seen with other AI apps.
Aleph, thanks for your responses too. DIY software at this level is very challenging though. Input/ideas from others as well as independant testing is valuable. I recommend approaching a college to find an IT Masters student to work with you as part of a Thesis project.
Message was edited by: piecraft at Nov 9, 2010 12:28 AM
Message was edited by: piecraft at Nov 9, 2010 12:35 AM
Some OTB pente against some Americans would be a hoot!