Home » Forum Home » Analysis

Topic: Pente - Understand vs Memorize
Replies: 122   Views: 260,318   Pages: 9   Last Post: Nov 17, 2010, 10:26 AM by: zoeyk

Search Forum

Back to Topic List Topics: [ Previous | Next ]
Replies: 122   Views: 260,318   Pages: 9   [ Previous | 1 2 3 4 5 6 7 8 9 | Next ]
jasonb

Posts: 105
Registered: Jan 3, 2010
Home page
Re: Pente - Understand vs Memorize
Posted: Oct 30, 2010, 4:31 PM

up2ng, I have tried multiple variations with the computer playing both sides at the highest level and me playing one side or the other against the computer. Option 1 was the best I could come up with, and the computer did not think of it, it was inspired by you. With your opening sequence, the computer can't beat black. Without it, the computer thinks white is the only winner.

I am pretty sure Zoey has an entirely different solution for black with the starting sequence he recommended.

This begs the question . . . what is perfect play? Humans are not perfect, and neither are computers because they are designed by humans. We can say one play is more efficient if it gets to a win quicker, but we can't define perfect because we are not.


up2ng

Posts: 542
Registered: May 9, 2002
From: Northeast USA
Re: Pente - Understand vs Memorize
Posted: Oct 30, 2010, 6:35 PM

That is interesting. Which level for each side were you using to let the computer play against itself? The "highest" level on his program from what I remember is 18 -- and no computer is powerful enough yet for that level.

The computer will essentially look at each reasonable move and look ahead as far as the level allows. If you are on level 12, it will look 6 moves ahead. If a sure win can be found within 6 moves, the computer will never lose and it will make its moves faster and faster with higher and higher scores until it wins. But if there are some scenarios where the game continues beyond 6 moves, then it will use an algorithm to score each possible move based on what the possible results look like on the board 6 moves later. If it is clear that the 6th move is very close to a sure win, the score will be higher than if all possible moves appear somewhat unclear after the 6th move. In those situations, the algorithm is probably not perfect, as you were suggesting -- which is precisely how humans beat computer opponents -- using moves which do damage further out than the computer can recognize. So, if you are starting it out on move 21 (black), the start of the puzzle, the computer is more likely to miss the best moves because the position is still very unclear by move 27 (as we're seeing!). But, if you follow it through and start out at move 27, it might get stronger results since the game might be better decided by move 33.

Anyways, that's why I suggested level 12 starting with move 27 -- to see if this line we're looking at for black has some obvious flaws that we're not seeing. It sounds like you tried that and black ends up with the victory, which supports, but is not necessarily conclusive, that black does win with this line -- although if it appears to have found a forced win before move 33 then it is conclusive.

(By the way, my older computers really would not be able to do this any higher than level 10 -- but I'm assuming that much faster current computers might be able to play through the position at level 12 without waiting TOO horribly long for it to finish.)

up2ng

Posts: 542
Registered: May 9, 2002
From: Northeast USA
Re: Pente - Understand vs Memorize
Posted: Oct 30, 2010, 6:50 PM

By the way, "perfect play" is actually pretty clear to me. You're right, there are times when humans and computers may not be capable of identifying it, but that doesn't mean that it doesn't exist.

Perfect play to me means that the player that is currently winning continues to play through the entire game, ending in victory, without making a mistake. A mistake, in this case, is a move that allows the possibility of the other player winning the game (whether or not it is too complex for a human or computer to recognize is irrelavent -- if it exists, then the move was a mistake).

Note that there can be, and often is multiple pathways to achieve a sure win, so all of these would be considered perfect play. In my opinion, the number of moves required to win should have no bearing on comparing how strong a move is relative to another one. Neither should the level of complexity. I have seen some old proposals for tournament rules that use the number of moves as a tie-breaker. I am strongly opposed to this. A win is a win in my opinion and comparing the number of moves is arbitrary.

Also note, the way I'm describing it here, the losing player really does not have any option to execute "perfect play" -- although often times the term is used interchangably for a slightly different concept (used often in puzzles) where the losing player tries to prolong the defeat for as long as possible. The idea of playing a "perfect" or even a "best" move as the losing player is somewhat subjective -- it depends on which strategy you happen to be using to try to coax a mistake out of your opponent. Again, the level of complexity does not factor in -- although increasing the level of complexity is often a sound strategy as the losing player.

If players disagree strongly with how I'm describing it -- it might be a discussion better moved into a new thread.

jasonb

Posts: 105
Registered: Jan 3, 2010
Home page
Re: Pente - Understand vs Memorize
Posted: Oct 30, 2010, 7:02 PM

Level 12 is the highest level on Mark's program; see attached screen shot. My computer is about 4 years old and was $250 at the time I bought it, so it's no speedster, but it can crank out a game like this one in about 20 to 30 min at highest level (that is a guess, I did not time it with my watch) .

I believe I already tried it at moves 27 and 28 on the highest level, but I've worked this so many times, it's hard to remember. I will run it again.

Anyway, I think perfect play, in computer speak, involves more than just looking X moves ahead. The computer has to be smarter, than it's human opponent. In this case, you outsmarted the computer with outside the box thinking, IMO.

up2ng

Posts: 542
Registered: May 9, 2002
From: Northeast USA
Re: Pente - Understand vs Memorize
Posted: Oct 30, 2010, 8:52 PM

Hmm that's interesting. I know I have a version on my computer that goes up to 18 -- maybe he changed it back in a later revision for some reason. It's not necessary to go beyond level 12 anyways...

jasonb

Posts: 105
Registered: Jan 3, 2010
Home page
Re: Pente - Understand vs Memorize
Posted: Oct 31, 2010, 1:45 AM

up2ng said: "Perfect play to me means that the player that is currently winning continues to play through the entire game, ending in victory, without making a mistake. A mistake, in this case, is a move that allows the possibility of the other player winning the game (whether or not it is too complex for a human or computer to recognize is irrelavent -- if it exists, then the move was a mistake).

Jason: Here's the rub with that statement; how do we know for certain that a mistake hasn't been made if we can't recognize it . . . we can't. If Einstein was alive today, or someone even smarter than him, and he was to study this game, he would redefine what we consider to be "perfect play". And even then, it would be nowhere close to perfection. Recognizing perfect is like recognizing infinity . . . the human mind is incapable of doing so. I said earlier that we can't define perfect. Perhaps it would be better to say that we can't achieve or recognize it. I understand what people mean when they use the term, I just find it interesting.

I don't think it's necessary to move this to another thread, it's just an interesting thought about a term that I have seen used many times within this thread. Just my opinion.

jasonb

Posts: 105
Registered: Jan 3, 2010
Home page
Re: Pente - Understand vs Memorize
Posted: Oct 31, 2010, 3:26 AM

AI play removed because VCT was not set and rendered poor solutions.


Message was edited by: jasonb at Nov 13, 2010 10:57 AM


watsu

Posts: 1,265
Registered: Dec 16, 2001
Re: Pente - Understand vs Memorize
Posted: Oct 31, 2010, 10:51 PM

The older version of Mark's program did go up to 18, yes, but I guess he figured that was higher than anyone could find useful given current computer speeds. Also, Jason - are you using the VCT setting? If not, that's a good addition for a scenario like this, although it will significantly increase the processing time involved. As long as the computer can find a line where one threat after another can be achieved from a position it will continue looking down that line beyond level 12 (or whatever level is used) until a victory is found.

Retired from TB Pente, but still playing live games & exploring variants like D, poof and boat
jasonb

Posts: 105
Registered: Jan 3, 2010
Home page
Re: Pente - Understand vs Memorize
Posted: Nov 1, 2010, 1:44 AM

Ah yes, forgot all about those hidden settings. I turned them all on, and now it's been thinking for 15 min on the first move. Hmmm. This might be a job for Zoey's 8 CPUs. Anyone else have a zippy PC that would like to take a crack at it? I posted the text files earlier so you don't have to build the board.

Marks Pente Program Settings:
VCT : When in Victory by Continuous Threats mode, the computer will extend the search past the current level whenever it sees a series of threats. These extensions of the search will take significantly longer than the standard search depending on the situation.

Breadth: The number of moves to further explore at each branch of the tree is usually about 20 (Medium breadth). You can double it with High breadth. High is useful for situations where the best move is not a high threat, but will take much longer to search. It is not recommend to use hi breadth for usual play.

Extent: The extent of the search allows the program to consider moves up to either 2 or 3 intersections away from stones on the board. 2 is standard. It is unusual but possible for a move 3 away to be a good move. The search will take about twice as long with an extent of 3 rather than 2. It is not recommended to use hi extent for usual play.

zoeyk

Posts: 2,071
Registered: Mar 4, 2007
From: San Francisco
Age: 43
Home page
Re: Pente - Understand vs Memorize
Posted: Nov 7, 2010, 11:28 PM

ive been running a AI 12 with VCT on 2 different positions at the same time for 15 hours now, still calculating. each position currently has 6 billion moves searched in each game so far. thats 12 billion in 15 hours. im doing this for a different opening than discussed here. but this gives you an idea of the speed i can do. it will probably take a couple more days at least to complete, since the positions im searching are very vague and have too many possibilties. im not using marks prog. marks i think it ends short of the search which makes it seem faster. it doesnt do a complete search i think. the one im using seems to check much more.
when it concludes its search, i will post the positions and the results if you guys are interested. let me know.


i just had a look, and its calculating at an average of 100,000 moves per second per game. both games combined is 200,000 per second.

this is with stock comp settings. does any one know how i can tweak my comp to increase calculating speed with out over clocking? i think there is a way to order it to miximize performance for this program running. im using windows 7, 64 bit.


Message was edited by: zoeyk at Nov 7, 2010 5:50 PM

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

Posts: 2,071
Registered: Mar 4, 2007
From: San Francisco
Age: 43
Home page
Re: Pente - Understand vs Memorize
Posted: Nov 8, 2010, 12:22 PM

one was finished when i got home. the other one is still going. and im not surprized. ill guess the one that finished hit close to 10 billion moves. ill post them when the other finishes. these might be interesting, becuase i know they are 2 positions players have been looking at lately as a new P1 position to take down as P2.

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

Posts: 2,071
Registered: Mar 4, 2007
From: San Francisco
Age: 43
Home page
Re: Pente - Understand vs Memorize
Posted: Nov 13, 2010, 4:06 AM

M8 was the AI's choice. this search took 24 hours.



O14 was the AI's choice. this search took 48 hours.
the reason this is double time, is P1's Special jump
shape is stronger than the diagnal 2 jump shape in the upper game.
although it has been thought that P2's second is stronger to go O12,
this is now being questioned. O8 needs to be studied further, but is possibly better.





although something dawned on me. and i studied the lower board for a bit. why would the AI knowing the special jump being stronger, why would it move further away after such a in depth search. and then i realized something. P2 has one cap. it is now set up to get a capture #2.
all the AI needed to do was figure out that no matter which way white builds its shape,.. that P2 can attack for 3 more captures from the shape. this is similar to mid game structure issues dealing with cap probs in the wedge opening. i found this interesting,..

n e wayz


Message was edited by: zoeyk at Nov 12, 2010 10:23 PM


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

Posts: 58
Registered: Mar 12, 2010
Re: Pente - Understand vs Memorize
Posted: Nov 13, 2010, 6:02 AM

K10 looks to win in both variations, no?

White sets up an unblocked 3-stone triangle, while black has nothing but a 2-in-a-row that won't provide a 3-stone triangle in turn from blocking white's triangle.

I suppose I am missing something elementary here. Either that or the bot in question wasted 24 to 48 hours on this position.

Upon further inspection, I no longer wish to play K10 in the first position. The second position looks to be markedly worse for P2 however....


Message was edited by: happyj0 at Nov 13, 2010 12:03 AM


zoeyk

Posts: 2,071
Registered: Mar 4, 2007
From: San Francisco
Age: 43
Home page
Re: Pente - Understand vs Memorize
Posted: Nov 13, 2010, 9:38 AM






in this position i have put AI with vct off as player one.
and have asked it at lvls 1 through 12 with no vct,
what move should it do? the results have been interesting.
im still waiting for levels 10, 11, and 12 to finish.

moves 1 and 4 are the same
moves 3 and 7 are the same
so far 2,5,6,8,and 9 are unique.
but the next 3 lvls might show another matching move.
why does 4 agree with 1? why does 7 agree with 3? hmmm...

lvl_____move

1 ______J11
2 ______K9
3 ______K8
4 ______J11
5 ______L8
6 ______N8
7 ______K8
8 ______M12
9 ______G7
10______M12
11______M12
12


{updated} level 10 finished, it matches level 8,..

{updated} level 11 finished, it matches level 8, and 10..

Message was edited by: zoeyk at Nov 13, 2010 5:36 AM


Message was edited by: zoeyk at Nov 13, 2010 4:05 PM


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

Posts: 105
Registered: Jan 3, 2010
Home page
Re: Pente - Understand vs Memorize
Posted: Nov 13, 2010, 4:47 PM

Zoey, what do these boards have to do with the puzzle?

Replies: 122   Views: 260,318   Pages: 9   [ Previous | 1 2 3 4 5 6 7 8 9 | Next ]
Back to Topic List
Topics: [ Previous | Next ]


Powered by Jive Software