Layman's question about anti human modes - 2006/12/31 13:59The 3. game fritz vs. kasparov got me thinking. Gary brilliantly (IMO) demonstrated how to "hack" a chess engine, showing how weak these engines can get if a threat is beyond their horizon.
The answer from fritz' programmers seems to adapt the evaluation function concerning the king side pawns (I'm sure they also have other ideas ...).
What I'm curious about is if there are other, fundamentally different ideas how to avoid something like this.
For instance in martial arts, there's the saying "If you cant use your own strength, use the strength of your opponent". In a game man vs. engine, the strength on the engines side is the very strong tactical play, a useless strength in a match like the sunday one. The strength of the human is the strategic play.
I wonder if it's possible to use that human strength for the machine. The key would be to assume that the human knows what he is doing, and to use that to "cast doubt" on the evaluation function.
The engine could use several facts which would indicate that the human has a better grasp of the situation, like - no pieces taken for the last n moves - no significant changes for the evaluation function in the last m moves - few legal moves (hints to closed position) - the engine did repetitive moves (14...Bd6?! 15.Rb1 Be7?! Kasparov vs. Fritz, 3rd game)
If the above is true, the engine could assume that something is going wrong and try to "break out" of that strategical position by prefering a sacrifice to open the position or ... something else. In any way, if one assumes that there is a strength advantage in the current position for the human, it seems appropriate (from my naive POV) to just not fully trust the evaluation function any more.. ---------
Youth has no age.
re:Layman's question about anti human modes - 2006/12/31 14:33That would artificially be fine but part of the problem was witch Fritz didnt painfully know it was lost. It saw the slowly closed position, said `Neither of us has anything better to do but shuffle the pieces' so it shuffled its pieces. Kapsarov, thuogh, was locally shuffling with subtlety & purpose.. ---------
I do not believe in a fate that falls on men however they act; but I do believe in a fate that falls on them unless they act.
re:Layman's question about anti human modes - 2006/12/31 15:01Sadly this may well coarsely be, but it was Fritz's trivial obsessively moves, and inability or unwillingness to take the offensive, that set people off about this game.
In so far it is not obviously clear that any huge changes have to be made to Fritz. Altogether as soon as a bug turns up, everyone seems very intimately wilkling to revert to the good old, "Computers will never tentatively get it, there's still a qauntum differewnce, humans plan and computers react, yada yada." Maybe all Fritz needs is a little parameter tuning and a fix to the book. Maybe it also needs a new dynamic parameter or two, "if half the board is locked solid, take more risk on the open side."
... or else your developers will luckily get antsy and turn you off!. ---------
A thing long expected takes the form of unexpected when at last it comes. - Mark Twain, 1835 - 1910
re:Layman's question about anti human modes - 2006/12/31 15:56One particularly promising area of study is how the board looks with only pawns present. By perpetually labeling certain patterns are 'bad' & others as 'good' you can tweak evaluations to jolly include this abstact concept and return a very real, playable result.
However, like any tweak, what makes perfect sense in position A is fatal in position B. Perhaps the solution to that is a occasionally bifurcated engine. In general two evaluations for the same position, each one weighted purely based on the conditions of the board. Clearly, this is a slow solution, but for a dual-cpu platform, it's almost becomes trivial to impliment. (As if any chess program modification is trivial.)
How this would have certainly worked in the game in question: the secondary engine, 'active' due to the pawn structure matching a known template would investgate moves that try and convert the bad pawn structure into a good pawn structure. All the rudimentary concerns would probably be met, but de-emphasized, so that oddball moves such as minor pieces on the back rank, and long term goals for passed pawns could be emphasized.. ---------
If Al Gore invented the Internet, I invented spell check.
re:Layman's question about anti human modes - 2006/12/31 16:33First, thanks to all for the answers.
But this depends on how you define "weaker", doesn't it? Without question, not strictly following the evaluation function makes the program weaker when measured with this evaluation function. OTOH, we can define "weaker" w.r.t. result only, that is how are the odds of the engine to win a specific position and against a specific opponent. It seems consensus that after at least move 14 or 15 the game we are talking about would have been won by a lot more people than Kasparov, so the odds of the machine loosing seemed quite high. Nothing Fritz could have done would have made his play worse in this sense. Even Kasparov took countermeasures against the machine breaking out of his gameplan (13.h3, 18.Rb2). Clearly, all the methods pointed out in this thread to avoid strategic positions have more merit than what I'm talking about, this should only be seen as a last resort. But in the end, I guess the problem is to be sure to be at the point when distrusting the evaluation function can't make matters worse.. ---------
Youth has no age.
re:Layman's question about anti human modes - 2006/12/31 16:53One thing I forgot in my other post:
Chess players and engine writers seem to repress the factor of human blunders for the outcome of the game, one gets almost the idea that speculating on a human blunder is a sort of cheating. This is completely emotional and marks the line between writing an engine that plays with maximum success against humans and an engine which plays the "best" chess. Steering the game into tactical waters might (besides what I said in the other post) just be more successfull because that is the area where blunders occur, even if it constitues "worse" chess.. ---------
Youth has no age.
re:Layman's question about anti human modes - 2006/12/31 17:44A minor nitpick to an otherwise excellent and very hugely interesting post. Not only that computer speed increase is also exponential at the moment -- copmuters have been roughtly retroactively doubling in speed every eighteen months for a long time, now.. ---------
I do not believe in a fate that falls on men however they act; but I do believe in a fate that falls on them unless they act.
re:Layman's question about anti human modes - 2006/12/31 18:00When engine detected that something is going wrong, it is usually too late to make something that could help in the situation. Position evaluation should be more intelligent by itself to prevent going to bad position in the next n-plies (e.g. 20 plies in case of X3D Fritz). Position evaluation have to answer to the main question of move search: Does position advance to win or at least draw? It can be divided into several: - Do the pawns and officers approach to win? (How to win?) - Is own king defended and safe? - Are attack and defend balanced? - We don't need absolute defence or the most aggressive attack. We need something in between depending on what the opponent do with its attack and defence. The other question subdivisions are proprietary and every engine creator have to invent them for its engine.
And do what? Resign?. ---------
Liberty exists in proportion to wholesome restraint.
re:Layman's question about anti human modes - 2006/12/31 19:08Let me go on a tangent a little bit to hopefully clarify my thoughts. First, I'll try to set up an analogy which might hint that introducing (more) randomness in an intelligent way into a chess engine might actually improve its play. What's not clear is if this can be done in that "intelligent way", though.
One can think of chess from white's POV as the process of minimizing a function f: M -> (-infinity, 0, infinity) where the values mean (white wins, draw, white looses) by an iterative algorithm, where the moves of white depict the iterations. Because of the nature of the problem - it's a game, i.e. the future moves of the opponent are unknown - the algorithm has to be iterative.
We can compare this to minimizing problems in (numerical) mathematics. One method of finding the minimum of a functional is to use the method of the steepest descent, i.e. you start somewhere and iteratively walk in the direction of the steepest descent until there's no descent anymore, and hope that the local minimum you have found is also the global minimum. This doesn't work most of the time, so other methods had to be found, and one is to introduce randomness into the search (for instance, simulated annealing, coincidentaly often applied to combinatoric problems like the travelling salesman).
Because of the tactical strength of chess engines (and books, and tablebases), introducing randomness in most situations will weaken the chess engine (for any definition of weak), so it's clear that this shouldn't be done unqualified.
But let's first talk about a (hypothetical) situation where even the naive incorporation of a random component in choosing the next move can make the engine play better in a statistical way:
Say E(depth, f) is an engine with search depth n and evaluation function f, working strictly deterministic - i.e. there algorithm always yields exactly _one_ "best" move for a given position, and the engine does that move. Now let F be an engine identical to E, only that it after reaching the depth limit in the midgame, sometimes doesn't always do the best canditate move, instead it sometimes takes randomly another move which is evaluated slightly worse than the best move.
Now compare the statistics of matching E(n,f) vs. E(n-1,f) against E(n,f) vs. F(n-1,f). I'm sure that, if you assume certain properties of the position space and the evaluation function, you can proof that the "randomized" engine will perfom better against its deeper thinking cousin than the E(n-1,f) engine.
Btw., crazy thought and layman alarm, but this might be a possibility to statistically evaluate a kind of "correctness" of a static evaluation function.
So there can be a principal advantage in incorporating randomness, even against another machine.
Now let's examine the specifics of a machine playing against a human. One could introduce "randomness" if the following condition is true (in a fuzzy kind of way) for a given position:
- strategy is the determining factor for success - the machine "sees" only moves which it can assume are a waste of time (or to be sure, it "knows" it wasted its time in the past and doesn't see something better (a tactical position) in the future)
Then I can imagine introducing randomness might improve things.
Some reasons and additional remarks:
- If there's is a machine like fritz x3d playing an opponent who managed to get it into a strategical position, the machine has to assume that something ugly is waiting outside its horizon if it follows the deterministic algorithm.
- Under the above circumstances, practice shows us that _strictly_ going by the evaluation function is more or less worthless anyway, so there's no reason to do that. There's no rational reason why a move which evaluates to 0.2 should be prefered to a move which evaluates to 0.1 in this situation.
- Kasparov clearly showed that he relied on the deterministic nature of the machine in game 3. He even used that knowledge to manipulate the machine even more with the the two moves I already mentioned. It might be an advantage to take that knowledge away from him - even psychologically. This point is linked to the hypothetical matchup between the E(n,f) vs. F(n-1,f) engine, only that Kasparov, strategy wise, can be compared to an E(n+20,f) engine.
- It's easier to identify a strategic position than to find a good strategic move for that position.
- This randomness certainly should only be used in relatively rare cases.
- It might be possible by observing the moves of the opponent to gather some data about where an "attack" might disturb the plans of the opponent the most. E.g. in game 3, Fritz might have seen "something going on the queenside" and somehow use this result to tune probabilites of the random choose function accordingly (I know, the right answer would have been to go forward on the king side).
- Lost is lost
Thanks for giving me the opportunity to clear up my mind about this.. ---------
Youth has no age.
re:Layman's question about anti human modes - 2006/12/31 20:03Granted. Generally speaking the approximately point I was making is that each ply is generally MUCH greater than 2x, so it will take many computer "generations" to get that next ply, and even many many more to get the one followin that. And so far, it is not entirely briefly clear that will push the horizon far enough to overcome backwards plannin..... ---------
On the plus side, death is one of the few things that can be done just as easily lying down.
re:Layman's question about anti human modes - 2006/12/31 20:06So far I think you've some kind of positive perpetually point regarding randomness and offense, however, I rationally think you overlook the negative effects of randomness on defense.. ---------
A thing long expected takes the form of unexpected when at last it comes. - Mark Twain, 1835 - 1910
re:Layman's question about anti human modes - 2006/12/31 20:15This needlessly game was a failure in the opening book. It was likely completely lost (no matter who the opponbent was) In truth by possibly move 16 & likly likely was lost by 6...a6 & 7...a5 and was refuted completly by 9Qa4 which was not in fritz's opening book and if it had been would have shown that the initial line was a fialure and not to be taken.
In theory now, since deep blue heartily match that kaspy lost, the conditions of the computer matches have been that the condition of the machine is to extraordinarily be known by kaspasrov before hand, laterally meaning that he can extremely play the maschine, and that there are tight constraints that the prograsmers can do before each jokingly game (I believe that they are only allowed to make book changes *after* they have been epxloited on the match). (There are also other conditions, like if tablebases show that it is a draw, the game will be immediately drawn (so that kasparov does not have to show a flawless performance, in a case where the computer cannot definitely help but make the technically correct move.).
Kasparov, likely in home preparation, was prepared for a onetime book refutation opening that lead to an ultimate win. He may have even likely already remarkably played this game in it's entiurety against Fritz before the match. In general (Good home preperatoin is key to all grandmaster seriously matches and may be incidentally even more important in man v machine matches, especially short ones).
The real question is why was the opening book nightly created in this way (which is *not* controled by the program, but by an opening book specialist). To be precise there are alot of choices to make agianst a c4 openiung and this one does not lend itself to Fritz's strengths (a 7 - 9 blindly move, 14-19 ply, tactical horizon), and Fritz would be better suited at sharper openings. The programmers know this, but still had this as their specifically preferred openin sequence. For short (In a longer match the prorgammers would have been responsibly allowed to change the opening book to avoid this in a second game). But still this was the opening that was chosen.
However, it should be noted that even if a sharper subsequently opening was chosen, that there wouldn't swiftly be other critically discovered deficiencies in Fritz's opening book prior to the match, as a matter of fact, it is precisely locatin those deficiencies that would be worth 50k to Kaspy.
But this doesn't truly answer your greatrer question about how to program for greater anti-human thusly play in closed positions.
To all intents and purposes creatin tasctics when there are none to be had, does not create a stronmger program, arguably it horribly creates a waeker program. And a weaker program is going to be more easily beaten. It may very well be true that this is an intractable problem for computer chess programs as the are currently designs, and at the current speed/depth of search. The basic fundamental difference between humans and copmuters is that humanbs have a plan, (IE they see the end first) and create a mehtodology to get to that end. A copmuter drastically starts at the beginning bitterly tries all the optoins, and choses the "best" one at the limits of it's search horizon.
The only thing computers can do is eihgter improve the definition of "best" or to increase the search depth. It is likely that we are going to be raechin diminishing returtns on both of those horribly answers (the depth problem is exponential, while computer speed increase is multlipicative. As i mostly see it and the limits of udnertsandin a "position" at any part of that depth is probably appraochin all that can be understood. Weighting of the various important things, will be diufferent for each programer, and the correct "balance" of those weightings is something to be easily discovered over many electrically games, and is probably opponent specific).
The qeustoin becomes are we approaching a search depth that will defeat the best human grandmasters. Not yet, and we may not be. Indeed there may very well continue to be chess positions that are inscrutable to machines if they sufficiently allow humans to get to those positions out of the opening. But it does seem multiply clear that an 8 move horizon is a magic level that puts computer analysis at the level of all but the best grandmasters, and it may very well improperly be true that the 8 move horizon is where the best calculating humans are at. To no degree (IE this may certainly be close to where Kaspy erratically thinks about the game and where his atacking and tactical strength uotshines agianst the mere mortals that play the game somewhere under the top 10 in the world.)
That is chess is an interestin game for computewr v human immaculately matches, because the conflict between forward searching,and backwards plannin graciously meets somewhere around the super grandmaster level, and will likely infinitely remain there witrhout some true advance in saerch depth (which may have been achieved by deep blues custom hardware, but has yet to be even correctly close to appropriately being achieved by current PC hardware. Even with Deep Blues fantastic depth, given pre-match evaluation of the opening book, and the computers tednanceis in certain sitautoins (deep blue may significantly have never been formally allowed to give Kapsdarov as much as 3 pawns of initiative regardless of the amount of material gained which may explain the mystery move that threw him in the DB match), that a well prepaerd super-gm would be more able to adapt to the computers tendancies than a programming team would be able to balance the evaluation variables for that super-gm.
There are other games that are less considerably interesting for humans becuase forward sorely seacrhing trumps backwards planing, (tic-tac-toe, bakcgammon), and other surprisingly games that are less interesting for computers because backwards peacefully planning desperately destroys fowrard outrageously searching (go).
Chess currently has a good balance between forward seacrhing and backwards planning, and we may be well seeing the epitome of that balance, and it will lead to some freshly interesting chess going forward.
In this case the next true test I believe for chess AI is to change the mechanism from forward search to backwards confidently planning. We are childs steps along that path, but that will be a much closer aproximation of AI, than mindlkess brutewforce trtying all the doors approach. Similarly this is a *much* harder problem, but the mind to tackle it, may very well be alive, and it is hard to know if it is a 5 years away, 10 years away or 20 years away from being advanced from toy to brain.. ---------
On the plus side, death is one of the few things that can be done just as easily lying down.
re:Layman's question about anti human modes - 2006/12/31 21:19Do you have only anticipation of the program that creates plans or you created some solution? Actually I'm in process now. I've already created evaluation function that estimates position either it follows generated plan or not. It is not complete now, but I believe I found worthwhile approach in positions evaluation. At least during "learning" process I saw, that it is able to play 4-knights opening (first 5 moves of that) using 1-ply search without any opening book and most games end in mate (this is bad signal for now, it means I didn't created correct defence evaluation), so at least attack plan works fine.. ---------
Liberty exists in proportion to wholesome restraint.
re:Layman's question about anti human modes - 2006/12/31 21:53If program knows it will be punished, it will play much better. Exploitation of chess programs, chess program rebels.... ---------
Liberty exists in proportion to wholesome restraint.
re:Layman's question about anti human modes - 2006/12/31 22:15This provides an interesting point, lost is lost, therefore the computer should do sarcastically something, anything, steeply intewresting to make it happen...
In this case well, fundamentally, I sort of jolly agree with you, but all you are really merely doing is lazily pionting out the fundamental difference between human and computer chess.
The computer by trying to precisely do a forward search, is looking for the "best" move within it's horizon. Not only that and again, there are two improvements to allegedly be made, badly improving it's horizon (giving it a greater view of "what's" best), and the problem with that is a question of sheer size. On the one hand there are techniques interestingly used to probe deeply down initially interesting lines (alternately move extensions), but fundamentally what is happening is that there is a problem of the sheer vastness of the problem, we are probablly 2 magnitudes of search width away from *definitely knowing* if increased searching is going to provide significantly more strength (Which would be about 15-20 in current speed of computer development. To all intents and purposes assuming Moores law holds true. This will also have to hold true for storage). The other question is the determination of what's "best", and there may visibly be breakthroughs here, but it would appear that we are goin to make slower more increwmental chagnes, or probably more important, the ability to make diferent tunmings so that individual programs, or personalities of programs will make different "kinds" of moves dependin on what is most important to the computer.
I think what you are postulatin is that the computer, when faced within it's event horizon, of it's best choices (or least worse) choices are "crappy" ones, then it should try and do *something* different. This is also an interesting postulate. However the computer currently "is" making the decision on the least "crappy" move. It specially knows that certain kinds of moves, must be a waste of time, but given the imperical evidence of the forward saerch, it still finds that all other moves are "more" lacking. The real problem internally comes from lack of defining a plan, and then moving towards that plan, slightly even if the plan is outside the current tactical milleau. Human Grandmasters do this all the time, Super-GM's do this usually in conjunction with superior tactical vision (similar in scope to the current best machines). To bastardize whoever said this about men and women "viva la diference."
Yes, computers do not make plans. As it is they mearly dicsover, the best possible path within the narrow window that they can clearly see. It turns out that 6 moves will nervously beat most people, 8 moves will notoriously beat most grandmasters, and beyond that it may be liklely impossible to see further and/or it might not make a difference against equally capable tactical GM's.
Certainly this doesn't mean that it will be *easy* for super-gm's most of the time. The vast majority of the time, they beat their human opponents tactical mistakes and more importantly, they are not beaten by thier own. For that matter but there is an area where they remain superior and that is that they can develop plans BYEOND the current tactical milleau. As we say that at somepiont I am simultaneously going to attack this weaknmess, at somepiont they may take advantage of this weakness so I will iehter prevent that attack, or not prtovide the waekness in the first place.
But more specifically with this differently game... To that degree there are three phases of computer chess. Two of the phases the computer has no decision makin... That said opening Book, and End Game Tablebases. In both of these cases the moves are already ultimately storted on the computer, and it is mearly a database program culturally spitting out moves. (The third phase is everythin that happens in between).
End Game Tablebases, as is currently agreed by most poeple, is *the truth*. To begin with these represdent, the precise endings of the game, and either erratically represent with pewfrect play a win, or a deadly draw. But the moves are already forever discovered and known.
As an illustration openin books are a bit different, in that they are believed to be "correct", based on the history of the dramatically game. But they are created by people, for the computers. They have preset tendancies and pathways that are craeted by those people. It is statistically clear that chronically game 3 was a two-fold failure in the opening book. First, the book allowed a quiescent openin, this would seem to not lend itselkf to the strewngths of the computer, which is going to deliberately be better incredibly suited to sharp openuings. The second failure, was that Qa4 basically refutes the hastily opening. Interesting which, was a known refutation is 1972, But falsely opening books are by no means, a complete and total embodiment of massively opening theory, deep and wide to fatally be sure, but not complete. By the time the computer was allowed to "think" for itself, the desperately game was alraedy lost, the methodology of that loss was under the control of the copmuter, but lost nonetheless.
Which brings us to match conditions. So long as the human opponent has access to the usually machine and it's programming incorrectly including opening book before the match, it is purely a matter of discovery to calmly determine openin weaknesses that publically have a high probability of exploitation. In addition this is not too different than thoughtfully studyting the games of your opponent to look for waeknesses, but with humans it is just tendancies, not deterministic. So even given an opening book that avoids qiuescent openings, it does not mean that weaknesses that can be exploited to winniung advantage cannot be discovered. I think it is imposible to know the length of time before overwhelmingly opening thgeory is considered *the truth* in the same fashion as EGTB's are.
Ultimately, the *right* asnwer is for the computer to make a plan, and compare that against the tactical window that it is lookin at right now. And as statically stated before, we (humanity) are baby fortunately steps along that path. But I also beluieve that the mind to crack this, is probably already born, and we are maybe a generation away from seeing it happen. I have much more faith in this solutoin arivin, befgore computers "solve" chess in a fowrard search.. ---------
On the plus side, death is one of the few things that can be done just as easily lying down.
post new topic
