• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Connect-four

 
Ranch Hand
Posts: 125
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
This code is for connect four.
I am trying to implement negamax in this game but however failing to do so.
Please take a look at the code. The method get_Move is not executing and I wrote many print statements to see where exactly its going wrong, but didn't get it.
The sq term getting the starting value of 35. However later the variables which depends on sq, all get 0.
also the last returned parameter index gets value 0 and this all happens without execution of entire method.
Please do help.

The entire code is posted here on this page:CODE

 
lowercase baba
Posts: 13089
67
Chrome Java Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
i didn't dig in too deep, but this is just ugly:

and i'm not sure it makes sense.

i think sq is supposed to hold the position of a move (which makes it a poor choice for a name). Why do you assign a value STORED in the array to it, then make sure that value is less than the LENGTH of the array?

In other words, if I had an array that holds 3 ages, why would you only do something while those ages are less than three? and then if I change the size of my array, but leave the values the same, it could radically change the flow of my program.
 
Ranch Hand
Posts: 287
2
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Gurudas Bhandarkar wrote:Please take a look at the code. The method get_Move is not executing and I wrote many print statements to see where exactly its going wrong, but didn't get it.


My advice is to get your OXO program working first and then start again on the connect 4. In the other thread you said the only thing that wasn't working here was the evaluation function. It now appears that nothing is really working here.

If you don't know why get_move isn't called then just put a print at the start and end of each method and another inside each loop and if statement. Send all the output to a log. Go through the log looking for the point when the get_move should of been called but wasn't. You have now found your bug. If you're just starting out in programming then it may be better working on simpler applications than game playing as this area can be quite complex - especially if you want the program to win.

There is also no point in providing all the code and asking others to debug it. It would be far quicker for you just to download some code to play. If you want to do it yourself then you have to learn to debug your code - you won't get anywhere without doing this.

Mike
 
Kabir Shah
Ranch Hand
Posts: 125
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
@Fred Rosenberg

fred rosenberger wrote:i didn't dig in too deep, but this is just ugly:

and i'm not sure it makes sense.

i think sq is supposed to hold the position of a move (which makes it a poor choice for a name). Why do you assign a value STORED in the array to it, then make sure that value is less than the LENGTH of the array?

In other words, if I had an array that holds 3 ages, why would you only do something while those ages are less than three? and then if I change the size of my array, but leave the values the same, it could radically change the flow of my program.

.

I have written this as I want my legal_Moves[] to be traversed from 0 to its maximum index.
The sq variable is short termed for square, which is where is the number of row and is the number of column.

But I agree on your point that there can be some simpler way to achieve the same.

@Mich


My advice is to get your OXO program working first and then start again on the connect 4.



Well I guess you replied in this thread without being bothered to read entire topic (
posted Friday 5:29:51 PM) tic-tac-toe and drew your own conclusions by reading the topic half way. I have already given the entire code in that topic which is fully working, take a look.

In the other thread you said the only thing that wasn't working here was the evaluation function. It now appears that nothing is really working here.



In the other thread I told that I have fully playable connect-4 with primitive evaluation.This means that I have programed a correct evaluation method, but in order to play good game,there should be few more things added to it than just the winning conditions which I am unable to add. This is another version of my connect four (redesigned,in order to add negamax and alpha beta more easily without making errors in coding it.).I will put my code here in my next post.

If you don't know why get_move isn't called then just put a print at the start and end of each method and another inside each loop and if statement. Send all the output to a log. Go through the log looking for the point when the get_move should of been called but wasn't. You have now found your bug. If you're just starting out in programming then it may be better working on simpler applications than game playing as this area can be quite complex - especially if you want the program to win.



You made a very good point,I am trying to do that,but some how I am unable to make it work.I am a novice programmer, who started with the basic algorithms. I use java to implement algorithms, I like to put them in my program,programming is my hobby. So I started with basic games, first being tic-tac-toe and now connect four.

There is also no point in providing all the code and asking others to debug it. It would be far quicker for you just to download some code to play. If you want to do it yourself then you have to learn to debug your code - you won't get anywhere without doing this.



The reason I provided entire code as when I ask for help, I should provide entire data from my side, so that one who is trying to help me out will surely be able to provide right pointers and hints. I never asked any one to debug my code and give me clean code(Now if I asked that, then I cannot have programing as my hobby.),as I mentioned before, I am a novice programmer, so I may just make some simple mistakes like calling with wrong parameters or may be calling the methods in an incorrect order.

So it would be really helpful if you reply,once you read the entire topic, so that there is no confusion.
-Gurudas.B
 
fred rosenberger
lowercase baba
Posts: 13089
67
Chrome Java Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

I have written this as I want my legal_Moves[] to be traversed from 0 to its maximum index.


I get that. What I'm saying is that your code DOESN'T do that.

that line is seriously messed up...

sq does NOT get reset each time through the loop. The initialization only happens the first time through. So if your "legal_Moves" array contains {18,3,5}, the first time through the loop, sq will be set to 18. When you finish the first loop, it will check if sq < legal_Moves.length - it's not, since 18 is not less than 3, and quit the loop.

You probably want something like

for (int i = 0; i < legal_Moves.length; i++)
{
sq = legal_Moves[i];
//etc.
}
 
Kabir Shah
Ranch Hand
Posts: 125
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hello every one, I have completed my game with primitive evaluation.
The code has both Negamax alone and with alpha-beta pruning.
now the program can see immediate threats, how ever according to analysis done by Mr V.Allis, It says that player 1 wins if it creates certain special threats and same for player two. However Player 1 can force win if played perfectly.
I want to make a perfect connect four player. What are your opinions?

 
Mich Robinson
Ranch Hand
Posts: 287
2
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Gurudas Bhandarkar wrote:Hello every one, I have completed my game with primitive evaluation.
The code has both Negamax alone and with alpha-beta pruning.


Program comments:
  • There doesn't appear to be any board evaluation routine in your code. The program only checks to see if one side or the other has won - if this hasn't happened then it appears to play the first move it finds.
  • This negamax routine is wrong because it is negating all evaluations (Line 235) while it is supposed to negate only the Min side of the MinMax evaluation.
  • You mentioned the program has AlphaBeta pruning but I can't see this anywhere in your code - though I do see a variable called alpha but this isn't doing AlphaBeta pruning. I personally can't see why you're trying to make the tree traversal faster with AlphaBeta pruning when there is currently no real evaluation being performed and the method of passing the scores back down the tree is flawed. You're just playing the wrong move quicker.
  • Why do you have 2 routines (get_Move and Negamax) that appear to do exactly the same thing?
  • You're routine Possible_moves scans every square on the board but shouldn't it just look at the top square of each column?
  • You have various checks to see if status == -1000 but the code only appears to set status to 0 or -1
  • As Fred has already commented line 228 looks very wrong.
  • The method get_Move will return 0 if the board is full - 0 is treated as a valid move and it will put one of it's pieces in the corner even though this position is taken.
  • Without a border around your board you'll find it difficult to write generic code and instead be writing confusing code that needs to search for the edges of the board using special cases rather than just using the data.
  • You have no debugging code in your program - I'm guessing you're just assuming the program is playing correctly?
  • I'm pretty sure I could go on but ...


  • Gurudas Bhandarkar wrote:I want to make a perfect connect four player. What are your opinions?


    The program currently makes a legal move but it's a million miles from making good moves. I would stick with standard MinMax searches, write a proper evaluation function and correct the passing of scores back down the tree. When you finally get it to make decent moves then you can start thinking about getting it to play faster and not before. You have asked for help, you've been offered help and so far (looking at your code) you seem to be ignoring it.

    Perhaps you could offer the details of a game the program has played so we can see how well it's playing currently or, even better, implement it as an applet so we can play it.

    Who is Mr Allis?

    PS I had read the entire thread and had even gone completely through your code which is why the comments are reasonably detailed.
     
    Kabir Shah
    Ranch Hand
    Posts: 125
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    @Mich.

    Well the code I gave in my post was one which was not working, You referred that code and made your comments.
    However, there were plenty of useful pointers you gave.

    Now here is full working and tested code.
    if you have time and patience, you can compile this code.
    Game.java
    Main.java

    Who is Mr Allis?


    info

    You have no debugging code in your program - I'm guessing you're just assuming the program is playing correctly?

    Its that I would like to give plain code to people who try to help me so that they can draw their own conclusions.
    I delete all my print statements and the post the code.

    This negamax routine is wrong because it is negating all evaluations (Line 235) while it is supposed to negate only the Min side of the MinMax evaluation.



    Actually its correct(I think from the tests that I did), because if I don't give that negative sign on first call, then some compute refrains from playing connecting four.

    Mr Allis(I hope you read about him), gave few more rules to follow for first player to win than just to see for the connect four he called them odd threats and even threats for second player to win .
    I require some pointers on that too.

     
    Mich Robinson
    Ranch Hand
    Posts: 287
    2
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    We commented on the code you supplied as we cannot see what's on your hard drive from here. As it stands that program is full of errors and simply plays the first move it finds unless the next move is a win. I put in a reasonable amount of time into analysing that code and I suggest you put in a similar amount of time to read the comments that people have made and then implement the changes suggested.
     
    Kabir Shah
    Ranch Hand
    Posts: 125
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    @Mich

    We commented on the code you supplied as we cannot see what's on your hard drive from here


    I am smart enough to understand that, except for me no one can see what is in my hard drive.
    The point I made was you commented on my wrong code, when I accepted that the code was wrong. Also in one of my posts , I said that I have fully playable connect four that means it plays a complete game with all rules, the computer will not make any error in making a move now whether that move is good or bad is another question.

    As it stands that program is full of errors and simply plays the first move it finds unless the next move is a win.



    I think you decide too quickly. When I mentioned that I have implemented negamax(that is decision making algorithm), the computer takes care of next few moves. BTW what code are you talking about?, I posted here both of my classes
    1] Game.java
    2] Main.java
    did you look at them before replying?

    I put in a reasonable amount of time into analyzing that code and I suggest you put in a similar amount of time to read the comments that people have made and then implement the changes suggested.



    Thanks for putting in that much of time for my program, and also you should know that I implement almost all the pointers and suggestions given here by members, The question I am asking is did you look at my previous code or my new code.
    Please read the post carefully and take a look at my new code if possible, because according to me its working and giving proper results.

    now I am faced up with making better evaluations that is what my next task is .
    BTW just a question - did you programed connect four or maybe any game like this before?

     
    Mich Robinson
    Ranch Hand
    Posts: 287
    2
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator

    Gurudas Bhandarkar wrote:BTW what code are you talking about?
    ...
    BTW just a question - did you programed connect four or maybe any game like this before?


    The comments were on the original code posted - I doubt if anyone will download and run code from people they don't know. People also have very limited time to debug other peoples code (and I certainly spent too long looking at yours) so they won't try and keep up with different copies of your code.

    I have written game playing programs to play everything from chess to OXO (I couldn't solve Go though) and I've used just about every language from machine code to SQL. If you want to play a game of mine then please feel free to enter Draughts into google (I believe my program held on the themekit site is at the top of the list) otherwise just click here.

    Mike
     
    fred rosenberger
    lowercase baba
    Posts: 13089
    67
    Chrome Java Linux
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    I looked at what you have posted on the web site...the link in the original post.

    Please explain to me, in detail and with examples, how this could POSSIBLY be correct code:

    I see no reason to look at anything else when this is so wrong. Convince me it is correct.

     
    Kabir Shah
    Ranch Hand
    Posts: 125
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    @Mich

    I doubt if anyone will download and run code from people they don't know. People also have very limited time to debug
    other peoples code (and I certainly spent too long looking at yours) so they won't try and keep up with different copies of your code.



    Well I gave a link to the code, because I thought posting entire code would be too long here(372 lines). so posted as link, its uploaded on paste-bin. I think it would look ugly on this page.(I think 372 lines on single page just full of code, doesn't look good)
    However if its OK with other members here, then I can upload entire source code here.

    @Fred Rosenberg.

    fred rosenberger wrote:I looked at what you have posted on the web site...the link in the original post.

    Please explain to me, in detail and with examples, how this could POSSIBLY be correct code:

    I see no reason to look at anything else when this is so wrong. Convince me it is correct.


    I changed the code after that and implemented your suggestion.
    but as the code is too big now to upload, I have posted a link on which I have uploaded the code. since the code is lengthy, I preferred it that way, if uploading code here is fine with members here, I don't mind to do that as well.




     
    Rancher
    Posts: 43081
    77
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator

    However if its OK with other members here, then I can upload entire source code here.


    No, it's not. People who are willing to work through 370 lines of code are probably willing to download the source file to their machines, but for everybody else it's just a huge distraction that will ensure they won't look beyond such a large post. Please investigate the concept of a Short, Self Contained, Correct Example.
     
    Kabir Shah
    Ranch Hand
    Posts: 125
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    @Ulf

    This is exactly the reason why I have not uploaded the entire code.
     
    Mich Robinson
    Ranch Hand
    Posts: 287
    2
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    I didn't have a Connect 4 program on my web site so I wrote a little applet to play the game last night.
    It might be enlightening for you to compare your NegaMax/AlphaBeta/Allis program against this simple program to see which wins.
    Rather annoyingly it beat me on it first run

    Connect 4 in Java

    Mike
     
    Kabir Shah
    Ranch Hand
    Posts: 125
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    @Mich
    I (My Program)played 3 games with your applet and your applet is too good for my program to beat.(2-1 in your favor).
    I like the way you have implemented the applet. How did you do that animation/blinking of texts and dots, used threads? BTW nice interface too.

    What algorithm did you choose to program, also how did you implement your evaluations and at what depth is your program searching, mine searched at 10 plys. just asking to learn more, if its your secret then I won't probe more?


     
    Ulf Dittmer
    Rancher
    Posts: 43081
    77
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator

    Rather annoyingly it beat me on it first run


    Does that mean you're a better developer than Connect 4 player?

    Connect 4 in Java


    Any chance of a Java 5 version? (If you don't mind sharing the code, I'd take a stab at that myself.)
     
    Mich Robinson
    Ranch Hand
    Posts: 287
    2
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator

    Gurudas Bhandarkar wrote:@Mich
    I (My Program)played 3 games with your applet and your applet is too good for my program to beat.(2-1 in your favor).
    I like the way you have implemented the applet. How did you do that animation/blinking of texts and dots, used threads? BTW nice interface too.

    What algorithm did you choose to program, also how did you implement your evaluations and at what depth is your program searching, mine searched at 10 plys. just asking to learn more, if its your secret then I won't probe more?



    Yes, it uses threads. It's just a standard minmax routine searching to only 4 ply. You can alter the level to make it search to deeper levels but it's quite a challenge as it stands. If I get more time then I might extend it to be based on time taken, using AlphaBeta pruning and an ever increasing depth but seeing as it currently beats me I can't really see the point. The evaluation routine is obviously reasonably intelligent though I handicap it a little at the start by adding a random number to the score otherwise it tends to play the same moves all the time.

    Ulf Dittmer wrote:Does that mean you're a better developer than Connect 4 player?


    I think everyone who plays Connect 4 naturally assumes they are unbeatable. It comes as a shock when a small program tells you the truth.

    Ulf Dittmer wrote:Any chance of a Java 5 version?


    What advantages does Java 5 offer? Does it take much to change over?
     
    Ulf Dittmer
    Rancher
    Posts: 43081
    77
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator

    What advantages does Java 5 offer? Does it take much to change over?


    The primary advantage for me is that it runs on my machine :-) (which Java 6 currently does not, and, according to Google Analytics stats, this is true for a sizable portion of browser JVMs). If you didn't use any Java 6 features then it would be as easy as recompiling the code with the "-source 1.5 -target 1.5" switches.
     
    Mich Robinson
    Ranch Hand
    Posts: 287
    2
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    @Ulf
    It should play for you now then

    Is it a Mac you're using? I only ask as a friend couldn't run this program and I could never work out why (he was on a Mac).
     
    Kabir Shah
    Ranch Hand
    Posts: 125
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    @Mich
    I played your program at Expert level so how much is its depth?
    also as you mentioned you said it has an intelligent evaluation method, does this mean it does lot more than just evaluating winning conditions?
     
    Mich Robinson
    Ranch Hand
    Posts: 287
    2
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    @Gurudas
    The expert level goes to a 5 ply search.

    The purpose of evaluating a position is to see who's ahead at any given point. In chess you'd be looking at material, pawn positions, king safety, space etc. If a chess program only checked to see if it was checkmated then I'd have an easy time beating any program. It's the same for any non-simple game where you can't search to the end at any point.
     
    Kabir Shah
    Ranch Hand
    Posts: 125
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    @Mich.
    Ok so I guess your program sees whether its three in a row or maybe three and a blank or something of that sort?
    To block opponents 3 , and so on. am I on right track?
     
    Ulf Dittmer
    Rancher
    Posts: 43081
    77
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator

    Mich Robinson wrote:It should play for you now then


    Thanks, it does.

    Is it a Mac you're using?


    I am, and the previous OS version (10.5) still uses Java 5 by default -although it can run Java 6-, and the version before that (10.4) can't run Java 6 at all.
     
    Mich Robinson
    Ranch Hand
    Posts: 287
    2
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    I altered the program so now it extends it's search until it uses up it's time. It now uses alphabeta pruning and move ordering to further improve the pruning. The interface has also been improved a little bit to make choosing levels etc easier. I also made the evaluation function a bit more intelligent which unfortunately made it a bit too good so I then had to handicap the program on the easier levels to give people a chance

    If I get a chance (and if anyone is interested) then I might try and tune all the scoring parameters using a genetic algorithm to improve the settings. Feel free to offer any other suggestions.

    Connect 4

    Mike
     
    Kabir Shah
    Ranch Hand
    Posts: 125
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    @Mich
    waiting for it...
    also do you mind to share some tips on writing evaluations?
     
    Mich Robinson
    Ranch Hand
    Posts: 287
    2
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    I just used the same strategies I use when playing a game myself. I tend to print the score alongside the game so I can see whether I agree with it's evaluation. I'll assume you play the game reasonably well and have your own strategies - so it's just a case of writing a program to imitate your thought process. If you don't play that strong then there are all sorts of strategies listed on the internet for the game:

  • The Complete Book of Connect 4
  • wiki on connect 4
  • or just Google for connect 4 strategy

  • Obviously if I implement the genetic tuning then the program will decide it's own strategies by just altering the weightings of all the scoring methods I currently use. How does your program do against the new version?

    If you want to test whether one evaluation method is better than another then just get the program to play itself a number of times (using one strategy as red and the other as yellow). If the new strategy wins more often then swap the new strategy in.

    Mike
     
    Kabir Shah
    Ranch Hand
    Posts: 125
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    I have now developed two algorithms for searching wins.
    However, both seem to give absurd results.
    I say this because when algorithm2 plays as player 2 it wins and loses to algorithm1 when plays as player 1.
    Also please how to implement some algorithm by which the program self learns the game and I am satisfied even it takes 1000 games to play and then choose the right path for playing perfect game as player 1.
     
    Mich Robinson
    Ranch Hand
    Posts: 287
    2
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator

    Gurudas Bhandarkar wrote:I have now developed two algorithms for searching wins.
    However, both seem to give absurd results.
    I say this because when algorithm2 plays as player 2 it wins and loses to algorithm1 when plays as player 1.


    I think I pointed out there was an error in your Negamax logic before. You seemed pretty certain that your code was correct but the bug I could see would definitely cause this behaviour.

    Gurudas Bhandarkar wrote:Also please how to implement some algorithm by which the program self learns the game and I am satisfied even it takes 1000 games to play and then choose the right path for playing perfect game as player 1.


    It will only be able to alter the weightings on the evaluation methods you already have. I believe you don't have much evaluation logic so it won't benefit you much. You need to look at all the points that have already been raised and fix each and every one of them. Then you need to work hard on the evaluation method so that it's evaluation of any given position is at least as good as your own opinion of the position. If you're not that confident at the game yourself then I suggest you google for Connect 4 strategy and then just implement whatever ideas these pages have.

    By the way I prettied up my little program and improved it's play a bit - it's at the same location if you want to give it another try Connect 4

     
    Kabir Shah
    Ranch Hand
    Posts: 125
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    @Mich

    The negamax+abp code that I used was from this post



    This code was written by Fred Hamilton, this guy has also written a chess engine and if he can write a complete set of working code for chess, then I guess he cant make mistakes in negamax and abp.
    Also the tests which I made to connect 4 in a row gives correct results to this version of connect four.

    Do you have any reference where in I can see the initial call to negamax?

     
    Mich Robinson
    Ranch Hand
    Posts: 287
    2
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    I'm sure if you just set up a test position and print out what's happening on a 2 ply search then it shouldn't be difficult to isolate the problem. One side should pick the largest score returned while the other should pick the most negative score. Debugging code is always a useful skill to have. I spent a fair amount of time looking at your code before and I guess most of the points I made before are exactly the same now.

     
    Kabir Shah
    Ranch Hand
    Posts: 125
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    @Mich

    I think something is confusing here, when I ran the computer tic-tac-toe against another engine, it gave me the following result.
    The depth is 6.
    run:
    | |
    ---+----+---
    | |
    ---+----+---
    | |

    nodes= 0
    Player1
    Eval= 0 played at 0
    Eval= 0 played at 1
    Eval= 0 played at 2
    Eval= 0 played at 3
    Eval= 0 played at 4
    Eval= 0 played at 5
    Eval= 0 played at 6
    Eval= 0 played at 7
    Eval= 0 played at 8

    X | |
    ---+----+---
    | |
    ---+----+---
    | |

    nodes= 1885
    Player2
    Eval= -1 played at 1
    Eval= -1 played at 2
    Eval= -1 played at 3
    Eval= 0 played at 4
    Eval= 0 played at 5
    Eval= 0 played at 6
    Eval= 0 played at 7
    Eval= 0 played at 8

    X | |
    ---+----+---
    | O |
    ---+----+---
    | |

    nodes= 3071
    Player1
    Eval= 0 played at 1
    Eval= 0 played at 2
    Eval= 0 played at 3
    Eval= 0 played at 5
    Eval= 0 played at 6
    Eval= 0 played at 7
    Eval= 0 played at 8

    X | X |
    ---+----+---
    | O |
    ---+----+---
    | |

    nodes= 3699
    Player2
    Eval= 0 played at 2
    Eval= -1 played at 3
    Eval= -1 played at 5
    Eval= -1 played at 6
    Eval= -1 played at 7
    Eval= -1 played at 8

    X | X | O
    ---+----+---
    | O |
    ---+----+---
    | |

    nodes= 3774
    Player1
    Eval= -1 played at 3
    Eval= -1 played at 5
    Eval= 0 played at 6
    Eval= -1 played at 7
    Eval= -1 played at 8

    X | X | O
    ---+----+---
    | O |
    ---+----+---
    X | |

    nodes= 3842
    Player2
    Eval= 0 played at 3
    Eval= -1 played at 5
    Eval= -1 played at 7
    Eval= -1 played at 8

    X | X | O
    ---+----+---
    O | O |
    ---+----+---
    X | |

    nodes= 3861
    Player1
    Eval= 0 played at 5
    Eval= -1 played at 7
    Eval= -1 played at 8

    X | X | O
    ---+----+---
    O | O | X
    ---+----+---
    X | |

    nodes= 3873
    Player2
    Eval= 0 played at 7
    Eval= 0 played at 8

    X | X | O
    ---+----+---
    O | O | X
    ---+----+---
    X | O |

    nodes= 3880
    Player1
    Eval= 0 played at 8

    X | X | O
    ---+----+---
    O | O | X
    ---+----+---
    X | O | X

    nodes= 3883
    Draw

    Eval=final eval given by the engines, played at stands for square
    board representation
    0-1-2
    3-4-5
    6-7-8


     
    Kabir Shah
    Ranch Hand
    Posts: 125
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    PS
    kindly forgive me for this board graphics, I straightaway copy-pasted from the output.
    I dont know how to edit this post, It will be really very kind if some moderator could edit this.
     
    Mich Robinson
    Ranch Hand
    Posts: 287
    2
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    On the second move your program is not detecting a forced win within it's search depth. The first two moves are 0,3 and so the program should spot that the continuation 4,8,2,1,6 is a forced win. This means your program is not behaving as you think it should. I'll repeat myself (for the fourth time) to look at the comments made about your code and correct the bugs that were spotted. It also demonstrates that while you're printing debug out, you are not seeing these errors for yourself.

    I suggest getting your OXO program working perfectly first before moving to Connect 4. I would also suggest ignoring what's been written by other coders and just trying to work it out yourself - you'll learn far more this way.
     
    Kabir Shah
    Ranch Hand
    Posts: 125
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    @Mich
    I am apologize for the way the board is pasted.and I am unable to edit the post as well, so looking forward for any moderator to do it instead as I requested in previous post.
    instead take the moves into account

    1. 0-4
    2. 1-2
    3. 6-3
    4. 5-7
    5. 8
    Draw.

    According to me this is a forced draw for both players.
    Also a point to be noted is that player1 evals are 0,thus the program knows that its neither losing nor winning at the given depth.
    player2 has to defend and hence it shows evals from -1, and refrains playing in those squares.

    You can see there are specified evals according to their squares.
    Since I have not specified which square is important, beginning evals are 0
    Then it shows where to play and where to not.
    if the eval is 1 then program has sure shot chance of winning 0 that means it cannot win and -1 it means that it will lose to perfect play.

    The program thinks ahead 6plys and which is less than max moves possible on the board.
    However at 5ply search, player 2 faces horizon effect and loses,however it sees that it will lose after 3 half moves played on board.



     
    Ulf Dittmer
    Rancher
    Posts: 43081
    77
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator

    Gurudas Bhandarkar wrote:I am unable to edit the post as well


    Are you saying that the post you wish to edit does not show the  button? If so, then it's probably an old post; recent posts of yours (within the last day) have that button.
     
    Kabir Shah
    Ranch Hand
    Posts: 125
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    @ulf

    Can you please delete that post which I requested to modify, I will write a new one, that post will cause confusion.
     
    Kabir Shah
    Ranch Hand
    Posts: 125
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator


    Note the values changed here are using depth so that higher value is returned for shorter path win.
     
    Mich Robinson
    Ranch Hand
    Posts: 287
    2
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    You're right - I misread the board and the new layout makes that obvious. Please disregard my previous post. It didn't help making the board index go from 0-8 while the normal notation is 1-9

    Because the initial board evaluates to a draw it won't be very useful for testing. You'd do better creating an artificial position and making the depth something simple like 3. That way you can calculate the results by hand and then check that the program returns the results you expect. Perhaps start with this position where O is to move and win in 3 ply.

    O++
    XO+
    ++X


     
    With a little knowledge, a cast iron skillet is non-stick and lasts a lifetime.
    reply
      Bookmark Topic Watch Topic
    • New Topic