Home » Forum Home » General

Topic: Hypothetical question: Pente software
Replies: 74   Views: 170,826   Pages: 5   Last Post: May 29, 2020, 3:27 AM by: watsu

Search Forum

Back to Topic List Topics: [ Previous | Next ]
Replies: 74   Views: 170,826   Pages: 5   [ Previous | 1 2 3 4 5 | Next ]
up2ng

Posts: 542
Registered: May 9, 2002
From: Northeast USA
Re: Hypothetical question: Pente software
Posted: Nov 9, 2010, 7:40 AM

I have a feeling that you all might be underestimating the complexity of this game as it relates to basically "solving" it. But I could be wrong -- I look forward to seeing what the finished product can do.

Also, in terms of this discussion, I actually think that you can just eliminate the AI ability to play as P2. Just create a program that plays from P1 only. To say that a program will always win from each side is nonsense. There are plenty of human players that can consistantly win as P1 no matter what is thrown at them. The inherant P1 advantage is quite vast IMO, and even moves that appear to be slight mistakes are in fact still winning moves. It is amusing to think of an AI spinning its wheels searching for a solution when there is none -- would it just break down with smoke pouring out of it from the futile effort?? How, then, would it select its move once it is determined that none are adequate? To me, that's probably a totally different algorithm that should be based on totally different principles than the P1 approach of simply searching for, finding and playing a winning move. Someone mentioned that the AI who wins 51% of games from the best player in the world would not be very impressive -- I disagree. I think that would be basically perfect in turn-based play since the best player simply is not going to allow himself to lose more than 2% of his games as P1.

So, instead, I think what we should be talking about here is an AI that is unbeatable when it plays as P1. This means that the best players each could play thousands and thousands of games against it and never win. That's a lot different from an AI that loses, say, 1% of the time against a top player. If an AI never loses after thousands of games it might be safe to assume that it has solved the game and it could be described as simply picking known winning moves each time.

I'm still not sure I understand how this is possible with current computing power. Even if this program could self-generate a perfect opening book up to 6 moves on each side (I'll believe that when I see it), my understanding is that once it leaves the opening book it has to use its algorithm to crunch through all reasonable possibilities until it finds a win. Since it is estimated that certain Pente lines can be forced to continue until about 27 moves (each side) despite perfect play by P1, doesn't that mean that the computer must look ahead 21 moves (42-ply!) into the future, crunching through a tree that widens very quickly, until it finds a move that is a sure win for every scenario? Even by my fuzzy math looking 42-ply deep into a game with the complexity of Pente just is not going to happen with a common PC of today's capability.

Perhaps you could expand on how you plan to approach this problem? Looking forward to seeing your finished product! Good luck!


piecraft

Posts: 34
Registered: Feb 25, 2009
Re: Hypothetical question: Pente software
Posted: Nov 9, 2010, 9:19 AM

Hey up2ng, I can see what you are driving at there. I do not see Pente as a simple game at all. If it was that simple none of us would be here.

As to your points about AI playing only as P1, I would say the following. I never proposed a killer AI would win all its P2s against master players - that would be impossible of course. I am talking about winning all P1s and winnable P2s.

Yes, 1000s of P1 games won against masters would demonstrate the strength of the program, but if it also loses the same number of P2s against those same players we have achieved nothing but equality. The test of the program would be if it did win that small % of games against masters where they do make exploitable errors.

Understanding how Minimax search works is difficult for non-programmers who have not spent the thousands of hours working on it. But suffice it to say, that there are many techniques available to you that enable quite deep search in mid-game situations. This is because of a number of factors, such as the fact there there is information available from the current board position that can be used, but effective tree-pruning is the key one. Techniques for stripping out lines that need not be searched means that other lines can be searched deeper. Eventually all lines will come across wins by consecutive threats for which further search extensions can be triggered.

Along the search path of the pente game tree, there are many moves that result in a loss in a very short time. Therefore terminal nodes of bad moves are well within even a modest search depth of 12 ply. These are quickly pruned out of the game tree, and search down unresolved lines is then extended. With the use of hash tables, bit-boards, intelligent move ordering, and other tricks we can greatly speed up the search.

Your point about some positions being 27 moves deep holds true for both sides. If the AI is P1 then it can chose not the play a book opening that goes that deep. If it is playing as P2 then it would be expected to push the P2 player to at least the depth that a human player could anyway. As for it perhaps searching 42 ply from move 6; whether or not this is possible is not the issue. The point is that a) it will search further than any (probably) human player anyway, and b) if it loses from such a position it will fold that information back into its database for next time.

I don't expect to try to write such a program myself as I dont have the time, but I am confident it can be done and that it could run on an upper mid-range PC. I have written chess programs, and other game playing programs, I have done work with generic algorithms and neural networks, route planning and optimisation applications, expert systems for controlling high-pressure flow through gas pipelines, dynamic manufacturing and distribution planning solutions, and many other things that would make your hair stand on end just thinking about them. Pente is complex, yes, but it is not so that it could not be overcome with the right approach.

Good luck Aleph, I think you can do it mate.

zoeyk

Posts: 2,018
Registered: Mar 4, 2007
From: San Francisco
Age: 42
Home page
Re: Hypothetical question: Pente software
Posted: Nov 9, 2010, 1:10 PM

if you pay me ill sell you my personal ai opening book file designed for Perfect P1 responses.
its stronger than mark's 1980's opening book file.

and ide be willing to beta test your AI.

i have a 40 game file i made of how to beat mark mammals AI both as P1 and P2 in as little as 13 moves each from either color. the AI8 is predictably beatable. ide be interested to see how strong your AI's P1 is when its ready.

Scire hostis animum - Intelligere ludum - Nosce te ipsum - Prima moventur conciliat - Nolite errare
zoeyk

Posts: 2,018
Registered: Mar 4, 2007
From: San Francisco
Age: 42
Home page
Re: Hypothetical question: Pente software
Posted: Nov 9, 2010, 1:35 PM

and yes, making the same book for P1 and P2 is a big mistake IMO. i can also make you a P2 opening book that is very good, that your AI can take as a starting point and then build on. for a fee of course. or some sort of bartering.

z

Scire hostis animum - Intelligere ludum - Nosce te ipsum - Prima moventur conciliat - Nolite errare
up2ng

Posts: 542
Registered: May 9, 2002
From: Northeast USA
Re: Hypothetical question: Pente software
Posted: Nov 9, 2010, 4:19 PM

When I was referring to the complexity of Pente, I wasn't just trying to say that it is "not simple". I was also speaking in terms of the number of permutations and variations that exist throughout a reasonably played full game, and also during any given position. Since the comparison to chess comes up so often I'll try to use that as an example. During Player 2's first move in chess, how many legal moves are available? I think about 10, correct? (I just realized that pawns can move one or two spaces of course so there are a bit more, but not a HUGE amount more...) Well, there are about the same number of reasonable first moves for P2 in Pente. In fact, during the whole early game in chess where the board is relatively cluttered, there are probably less available legal moves at any given point than people might think. The board is just too cluttered and many pieces cannot move at all or only have a small number of options. Similarly, when the board is extremely sparse, say a king vs. a king and a rook, the number of legal options available is also relatively small. The midgame might open this number up a bit, but I don't believe it is orders of magnitude larger than a complex midgame decision in Pente. The difference, as you mentioned before, is that chess games last for a lot more moves than Pente games in general, if they were always played all the way out to a checkmate or stalemate. This lack of depth does make us realize that Pente will be solved by a powerful computer at some point -- but I still don't believe that day is here yet.

"...talking about winning all P1s and winnable P2s."

This makes sense. But again, in Pente, playing as P2 is very different from playing as P1. It would be interesting to see what adjustments to the algorithm are used to create a strong P2 player. Now sure, if you take a snapshot of a midgame that is already winnable as P2 and then stick the AI into that seat, we should expect it to win. But, when that win is not yet available, how will the AI determine the "best losing move" to try to coerce the opponent into making an error that can be capitalized upon by the "killer AI" routines? This is not trivial. Unless you will lean heavily upon databases of previously played games for this task (and then how is that any better than what a human could do?), I'm not sure what the algorithm would look like that plays a competant P2 game while losing.

I do have a programming background, although not much in this niche so it's always good if you can describe things generically like you are doing...

I might not have been clear about the estimation of games lasting 27 moves. I'm talking about P2 playing in such a way that prolongs the game as long as possible no matter how quickly P1 tries to win. This includes needless extentions and so on. In other words, your response that the P1 AI could choose not to play an opening that goes that deep would be impossible. It would have no choice if it wants to win the game. This is just theory at this point of course and the estimation was a consensus among a group of human master level players from quite a while ago -- at least 10 years ago, and maybe quite a bit longer. The knowledge base for this game has grown since then of course but I have not seen any reliable updates to this estimation. An example of this is:

1. K10, L9

Now, it is generally accepted by human players today (and in the past) that the best response to this position is:

2. N10

and one of the strongest, or at least most complex continuations is:

2 ... N9
3. M9

this creates a "Wedge" opening, which is still one of the most complex openings in the game today. If a wedge opening is played all the way to the end, including all useless extentions, by two top players, it is estimated that P1 cannot win faster than 27 moves if P2 does everything possible to prolong the game. Furthermore, if a different 2nd or 3rd move is chosen by P1, the game can be made to last even longer since those alternate moves are not as strong and so would lead to unnecessary complexity.

Of course, if a computer came along and solved the game, or if a math major came along and solved it mathematically, it would be great to learn of the true maximum number of moves required to win. The estimation of 27 might be innaccurate, but by how much? We'll see when someone solves it...

In any case, it is NOT a trivial depth for a computer to search, considering how broad the tree becomes at each level, to be able to see all the way to the very end of the game for every possible scenario. And in my opinion, unless the computer is doing precisely this it cannot be proven to be unbeatable -- if it relies on opening books and prior games from a database, it opens itself up to innovation by a better player who does something that is outside the book, and early enough to be beyond the search horizon, and now the computer is vulnorable -- even if it were just for that one game.

That brings up your notion of:
"b) if it loses from such a position it will fold that information back into its database for next time."

First, if that happens, it wasn't unbeatable was it?? Next, if this information becomes available, how does the computer identify next time which move along the line was the error? This could take literally hundreds of games of trial and error for it to figure it out. That's a lot of losses for an "unbeatable" AI... But yes, if it can learn from its mistakes in this way we can assume that it can eventually could become unbeatable by playing a "large" number of games and eventually mapping out all scenarios. But at what point would we know that it has found all scenarios? If even one little thing remains that the computer never found and a human player happens to play it, then it's beatable, even if it was just for that one game. How will we know when a computer has actually solved the game in this manner?

So, it seems like there are two schools of thought for how a computer will solve the game (possibly working together?) One, it could use processing power to crunch through all scenarios and select winning moves as calculated. Or two, it can play billions and billions of games and somehow refine its database of results over time so that the game becomes "mapped out" in advance, and eventually when playing against it it will just be doing database lookups and not using any logic or algorithms at all. In my opinion, both approaches require more time than is reasonably available with current computing power -- but we'll see I guess.

The other comment that:
"a) it will search further than any (probably) human player anyway"

This is flawed thinking and I'm sure that this is one of the main conundrums that continues to baffle and elude AI experts today. As powerful as computers are, they just cannot think the way humans can. Humans do not need to search 27 moves deep to recognize winning moves. It is more conceptual and artistic in the human mind and this creativity can often beat computer opponents who are doing the same task methodically, even when they are very powerful. Even if a computer is looking much deeper than a human opponent -- if that computer is not actually seeing all the way to the end, that human can still win. This conceptual thinking appears to be too difficult to create as a hard and fast algorithm that can be programmed for use by a computer -- at least so far...

Anyways, I'm not trying to be too argumentative here -- you have experience with these technologies and you are probably correct in what you are saying. I just find it to be a very interesting topic so I'm just making conversation.

It will be interesting to see if such software ever materializes and if it will be truely unbeatable.

niobium

Posts: 30
Registered: Apr 6, 2008
Age: 37
Re: Hypothetical question: Pente software
Posted: Nov 9, 2010, 5:49 PM

Many interesting ideas from everyone

Chess is very different from pente, and much more complex.
In chess a 6 piece endgame can be very difficult for a human player, but in pente, the game gets much simpler in the ending part of the game.

Solving a game can mean various things.
(for example: analysing every possible position or analysing nodes/positions received through threat search)

A simple game like tic tac toe can be easily solved by brute force - analysing every position in a minute or two.

With more comlex games, analysing every possible position is not possible, so programmers use for example a threat search algorithm or alpha beta pruning.

That means they only analyse moves which lead to a threat
(for example a closed 4, an open 3...).


More similar games to pente would be gomoku (free) and renju (free).

Gomoku was solved in 1993. - via brute force
Renju was solved back in 2001. by János Wagner and István Virág. (Btw. Virag is also a well know Hungarian pente player)

Both games took a hit, but got "fixed" with new opening rules.


As for a pente ai, and solving pente:

The ai for P1 and P2 doesn't have to be different.
In case you want the ai to play the longest line, that's no problem, although a sure loss in 10 moves and a sure loss in 15 is not different in proving a loss

Mark Mammel's ai could be much stronger with little tweaks.

1. giving the comp. permanent brain (that means, the ai would think while the human player is thinking)
2. splitting the lines in multiple threads

I think pente could be solved easily today.
(at the end of the pdf -3rd link- you can see that Renju was solved in the shortest solution in 47 plies/moves, so 27 moves is not that much)


Solved game:
http://en.wikipedia.org/wiki/Solved_game

Alpha-beta pruning:
http://en.wikipedia.org/wiki/Alpha-beta_pruning

Solving Renju (a pdf file):
http://www.google.hu/url?sa=t&source=web&cd=1&ved=0CBYQFjAA&url=http%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fdownload%3Fdoi%3D10.1.1.102.7838%26rep%3Drep1%26type%3Dpdf&rct=j&q=solving%20renju%20janos%20wagner&ei=xXDZTMSzC8_Gswa1hPHyBw&usg=AFQjCNH0-i3hVdQHgxULLz2TEsskyozWSw&cad=rja

watsu

Posts: 1,168
Registered: Dec 16, 2001
Home page
Re: Hypothetical question: Pente software
Posted: Nov 9, 2010, 7:06 PM

"Someone mentioned that the AI who wins 51% of games from the best player in the world would not be very impressive -- I disagree. I think that would be basically perfect in turn-based play since the best player simply is not going to allow himself to lose more than 2% of his games as P1."
Up2ng, I think you misinterpreted what I was saying there. What wouldn't be impressive is if the computer won more p1 games than it lost p1 games to the top human players. 51% wins in sets would be impressive, just not as impressive as if someone were able to program a P2 computer which could beat top human players more often than that- I was just trying to make clear what would be meant by the statement that the hypothetical computer program could "beat Nosovsky most of the time".

Also perhaps worth noting is that both Richardiii and Nosovs have lost turn based tournament P1 games recently, so top level mistakes are possible- even if the mistake was just to bring a B game to that tournament...


Message was edited by: watsu at Nov 9, 2010 1:17 PM


I don't want to play non tournament rules games. If you take one of my unrated invites, play tourney
zoeyk

Posts: 2,018
Registered: Mar 4, 2007
From: San Francisco
Age: 42
Home page
Re: Hypothetical question: Pente software
Posted: Nov 9, 2010, 9:50 PM

has any one considered the idea to make a Shapes Library?
so the AI could automatically see shapes with in a pattern, or partial potential shapes in a pattern. give them values, and also show surrounding coordinates of basic defusing places that redefines values? a possible short cut method to help the AI read the board?

is this a silly idea?

z

Scire hostis animum - Intelligere ludum - Nosce te ipsum - Prima moventur conciliat - Nolite errare
zoeyk

Posts: 2,018
Registered: Mar 4, 2007
From: San Francisco
Age: 42
Home page
Re: Hypothetical question: Pente software
Posted: Nov 9, 2010, 9:53 PM

also, is there a way to teach the AI how to learn Adzi?

adzi explained here;
http://pente.org/gameServer/forums/thread.jspa?forumID=27&threadID=4643&tstart=0


Message was edited by: zoeyk at Nov 9, 2010 6:19 PM


Scire hostis animum - Intelligere ludum - Nosce te ipsum - Prima moventur conciliat - Nolite errare
alisontate

Posts: 157
Registered: Nov 27, 2008
Age: 30
Re: Hypothetical question: Pente software
Posted: Nov 10, 2010, 3:23 AM

Hi everyone, this is a very interesting thread. Just thought I'd chime in on this. I have dabbled in the dark arts of AI programming a bit (although I didn't do the coding myself).

I agree with piecraft on all his points. This is very possible in my opinion.

As far as I know, the design for a strong P2 player is identical to the P1 approach. With minimax, the algorithm just switches back and forth to find the least worst move in turn for each player successively through the game tree. A position that is strong for P1 8 ply from now is equally weak for P2 (since this is a zero sum game). The program just calculates which branch of the tree results in the least minimal value position for P2 (it assumes P1 will always chose its best options too). So P2 is just the reciprocal of P1 and vice versa. (I expect some of you will debate this, but mathematically they are for all intents and purposes identical.)

As far as I recall, Chess has an average branching factor of 34 which means that there are on average 34 possible replies to each move each player makes. Yes, at the opening chess has a lower branching factor but as the game progresses this increases unevenly until towards the late middle and then end games the BF is much larger and can be in the order of 80 or more. The position evaluation at leaf nodes for chess is quite involved and the complex interplay between different pieces, potential capture sequences, their differential piece value, differential positional value and so on make chess extremely difficult to master in AI. I am no pente master, but from where I sit pente is nowhere near this difficult to analyse. I agree with piecraft that the evaluation of leafnodes in pente positions is a much simpler task. And as for zoey's concept of a shape database, this would be in the form of bitboards that would be 'ANDed' against the current position to detect shapes and proto-shapes.

Up2ng, your disadvantage here is not having worked through how minimax and alpha-beta pruning works in detail. Your comments about combinations and permutations are exactly the kind of thing that these algorithms are designed to contend with. Believe me, when I first came across this, I was impressed by how effective various techniques can be in dealing with potentially massive amounts of data. Without having worked in-depth in this specialized area, it is hard to appreciate the power of these algorithms.

As piecraft mentioned, it is important to remember that these algorithms are able to work effectively on lots of different games, both zero-sum abstract games and games involving chance, and the idea that pente is in some way a special case or that is more complex then we realise, is just not the case.

One last point I would make. Yes humans think differently and are able to conceptualise positions and think abstractly, but the human world chess champ was beaten by a brute-force calculator that only averaged a 16 ply search depth. Are you suggesting that a search depth greater than this is required to defeat the current best human pente player on a game less complex than chess? When Kasparov lost to Deep Blue he said that the machine played 'beautiful chess' which was a very human abstract appreciation for what was achieved without consciousness. Brute force search beats humans these days even on modest computors.

~Alison

piecraft

Posts: 34
Registered: Feb 25, 2009
Re: Hypothetical question: Pente software
Posted: Nov 10, 2010, 6:09 AM

The question is not really whether a standard PC can handle it, its more 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 think both of these are very possible with pente.

In the first instance, examining the board is a question of pattern identification and classication. This is the smarts of the program and will be the thing that most impacts on its effectiveness. As Alison said, bitboards are one effective way of doing this. There are others of course. The second thing is move ordering. This is fairly simple because threats in pente are not that hard to detect (for a computer at least). These are short term threats I speak of here. Short term threats should be searched first since these are the most pressing and need to be avoided or examined to see if a sound response is possible. Good move ordering improves the efficiency of minimax alpha-beta search dramatically.

On your point about folding the info back into a database. Typically all such programs go through a proving period from first release. I did not mean to suggest that you would one day switch on the program and right there it is unstoppable. There is a knowledge curve with these things as its first and second releases are tested on the market. The important thing is how it address issues as they arise. It is incorrect to think of an unsound position being stored statically in its db until it comes to that situation again. Such programs (and their programmers), will perform exhaustive search
on the situation prior to that position to all the terminal nodes and find correct responses to this and its variants and all this information will go into either its opening book or its transposition tables. Further to this, the developer will analyse what innaccuracy (if any) lead to a negative outcome and draw conclusions which will help avoid similar situations in the future.

Ultimately as has been pointed out by niobium, Pente can be completely solved via AI and no doubt this will be done before too long. I would also expect that my estimate for a minimal self-generated opening book depth to be too low, and would really be more like 8 moves (16 ply). The quality of this book will be dependant on the program having performed exhaustive search from these positions to the end of the game tree. When this is done to that depth it will be almost as good as saying that the game is solved.

up2ng..."This is flawed thinking and I'm sure that this is one of the main conundrums that continues to baffle and elude AI experts today."

It its not flawed at all, and there is no "baffling" going on. The problem is well defined and understood. I understand very specifically the relative performance of humans verses computers on matters of search depth and breadth, pattern recognition, structural and strategic thinking and planning verses tactical analysis when comparing AI and human approaches. This field is very advanced now and the concepts are well understood with literally thousands of papers on the subject and programs written. Extensive testing of human search performance has been made and one of the key findings is that human performance varies greatly within any one game and from game to game. The computer performs the same all the time and does not fatigue. Even searching to the same depth as humans are capable of at their best, will usually beat humans simply because sooner or later they don't search that deep on a couple of moves and this leads usually to a loss.

Anyway, thanks for all your points up2ng. I know this is just a case of throwing some questions out there and having a convo. All's good.

watsu

Posts: 1,168
Registered: Dec 16, 2001
Home page
Re: Hypothetical question: Pente software
Posted: Nov 10, 2010, 10:45 PM

"I expect some of you will debate this, but mathematically they are for all intents and purposes identical." Okay, I'll debate the statement that "the design for a strong P2 player is identical to the P1 approach."

I'll state a couple of reasons why I believe that while this may indeed yield a strong P2, it will not yet be of optimal strength simply because it plays a perfect game as P1.

Analysis of how one's opponent plays is a key factor in winning as P2, particularly in turn based games. Therefore, if a computer AI simply picks what it conludes is the least weak possible move for it to to make (however it may determine that move), it has already pruned the tree. Even if you let it choose between its top three choices at random or favoring the first choice but occasionally playing the second or third choices, a well chosen first move designed particularly for that opponent at that particular point in time will be a superior choice. Since P1 has many chances throughout the game to make a less than optimal but still winning move, P1 can afford to make many minor blunders which P2 will not be able to exploit enough to achieve a win.

Even if you somehow pre arm the computer with a database of all known games played by the human/computer who is going to be the next opponent, some sort of judgement needs to take place in order to calculate the optimal P2 line at that moment.

1. This opponent just made an exploitable error as P1 in their last game which was not exploited. Shall I try to exploit it? Depends. If the line was unusual, they may suspect a trap based on analysis of the prior game and therefore diverge from the line they played last time. This in fact happened to me recently.

2. This opponent just made an exploitable error as P1 which was exploited. Should I try to exploit it again? Depends. Does the opponent always correct exploited mistakes immediately after the loss occurs, and do they always correctly identify the precise move which changed a winning line into a losing line, or do they abandon a portion of the line which is still winnable?

3. This opponent has recently played more than one game which illustrate an error in his/her/its understanding/perception. Should one of these lines where the mistake was not exploited be chosen? Depends. Can another line be found which they have not encountered which offers a similar enough situation that they are likely to make the same type of error, and if that error is again made will it be a fatal one in that case.

I could go on, but these few examples should suffice to illustrate what I'm getting at, I think. Play as P2 is enhanced greatly by analysis of one's opponent. Now, if millions of games of pente can be played against the same opponent at the same level of understanding, the P2 wins will stack up due to perfect play by one P1 and slightly less than perfect play by another P1. However, if the goal is to find the best chance to beat THIS opponent in THIS not yet started game while playing as P2, perfect play as P1 ability falls far short of what I've described above.

I don't want to play non tournament rules games. If you take one of my unrated invites, play tourney
happyj0

Posts: 58
Registered: Mar 12, 2010
Re: Hypothetical question: Pente software
Posted: Nov 11, 2010, 6:38 AM

To those who seem to know something about creating bot software,

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?

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?

My apologies if this has already been answered in a long post somewhere where I might have skimmed the post carelessly (cough).

[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....


Message was edited by: happyj0 at Nov 11, 2010 12:38 AM


alisontate

Posts: 157
Registered: Nov 27, 2008
Age: 30
Re: Hypothetical question: Pente software
Posted: Nov 11, 2010, 7:45 AM

Hi Watsu, you raise an interesting question here and I don't know that piecraft really covered this that well (sorry Pete! ).

The thing is, in the chess world, players prepare for their opponents as well. People prepare for competition against computers just as they do for human players. Yes, computers have biases too!

Assuming that our killer AI or KAI does not search the terminal nodes of every position, so it therefore must be looking at future non-terminal board positions and making some sort of evaluation. The question is what evaluations should it make, and should these be different for P2 and P1.

Any such evalution needs to look for structural strengths and weaknesses, threats, captures and so on. Not only does it need to do this, it must also determine if a loss is lurking just over the search horizon. So, such an evaluation must be clever enough to identify strengths and weaknesses effectively. As mentioned before, a strength for P1 is met by an equal and opposite weakness for P2 and so on. The value of a position is in-effect always given for both sides, even though the minimax value returned at each ply oscilates between a high and low with respect to the side the computer is playing for. (I hope this makes sense). From the perspective of the program each side is identical and the same analysis is performed regardless.

As for preparing for players. The computer does not prepare, but this does not matter. It simply plays the best move it can calculate. This will mean that all of the good options available to P1 will be considered by the program anyway - current lines, new innovations will all be treated the same. Remember that the program neither knows nor cares about the human activity of secretly creating traps and new lines to trick new opponents. The program will have no biases to play one line or another so cannot be tricked in the first place. Everything is evaluated from each position as it is found.

Having said all that. As I said, in the chess world players prepare for the biases of their computer opponent and try to 'take it out of book' as soon as possible. This is effective to a point with chess because it is so vast and the values assigned to future board positions are based on imperfect evaluations which, no matter how good these are, vary in their degree of perform from one position type over another. These variations are studied, and players try to direct play to position types where the program is believed to play less optimally.

So, why can't we attack the KAI the same way? Well, in principle we can, but with the following caveats. Due to the shorter game length, by the time the player directs play to positions the KAI theortically does not play as well (we maybe talking miniscule differences here), the KAI will already have been working from an optimal (proven) book and will likely be able to exhaustively search to terminal nodes from there most of the time. Secondly, the game is fairly homogeneous (uniform) and not likely to have certain types of positions where it plays better or worse. While Mark Mammell's program has limitations as described by zoey, we are talking here about a new program that does not have these same limitations.

watsu

Posts: 1,168
Registered: Dec 16, 2001
Home page
Re: Hypothetical question: Pente software
Posted: Nov 11, 2010, 9:47 AM

okay, I understand the gist of what you are saying Alison, but it is (to my reading, anyway) still all about the KAI's P1 play. What we are wondering about is the question 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. IMO, this is basically what happyj0 is asking as well, and I don't think your post above answers it.

I don't want to play non tournament rules games. If you take one of my unrated invites, play tourney
Replies: 74   Views: 170,826   Pages: 5   [ Previous | 1 2 3 4 5 | Next ]
Back to Topic List
Topics: [ Previous | Next ]


Powered by Jive Software