Sign in to follow this  

Need a heuristic for drop four game

This topic is 4671 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Well, computing the evaluation should be fast too so you don't want any too complex functions. Something like taking a weighted sum of how many and how long non-blocked rows the players have on board could be a start.. Maybe add some bonus to having balls closer the center. And learn the weights from millions of repeated games.

Share this post


Link to post
Share on other sites
Quote:
Original post by RPGeezus
Use the search button at the top of the screen.. Alvaro (I think it was him) had determined a way to tell who should win any given position by examining the board (i.e. no game tree required).

Yeah, it probably was me. But it's not true that you don't need a tree. Once you get to a position where no new threats can be created, I have a mechanism to know exactly who will win, and no search is required. But in the early stages of the game, my ideas only give you an indication of what type of threats matter and which don't.

http://www.gamedev.net/community/forums/topic.asp?topic_id=225611&whichpage=1

I strongly disagree with speed being the most important factor here. No reasonable ammount of seaching is going to let you know that in this position
_ _ _ _ _ _ _
_ _ _ _ _ _ _
_ _ _ _ _ _ _
_ _ _ 1 1 _ _
_ _ _ 2 1 _ _
_ _ 2 1 2 _ _
player number 1 will win easily.

Share this post


Link to post
Share on other sites
Man, I just wrote a Connect Four game in Computer Science 3 class in TrueBASIC over a month ago, wewt! :)

I'm not exactly sure what you mean by heuristic.. just a way of doing things? What I did for it was I basically just gave each "cell" an ID, using a formula (it was something like id = y*6 + x, where 6 was the number of cells per row).

To see if anyone won, what I did was I went through each x,y pair and did some checking to see whether there was a vertical win, horizontal win, or diagonal. Basically just have a variable for the number_in_a_row_so_far and increase the X value by 1 and check if there's another one of the player's tokens there and if so increase the number_in_a_row_so_far and yeah.. you get the idea.

Hope this was somewhere in the ballpark of what you requested.

Share this post


Link to post
Share on other sites
Thanks for all of you people for ur concern. Talking about the heuristic I mean we cant ofcource search for the all possible states and we have to stop the tree somewhere so at that point we have to make the evaluation that evaluation funcion i think is heuristic. and as far as i have learned there are 7 cells per row(for jost1billion). well jost you could have been a real help if you can explain this for me with more detail. i actually not getting your idea. and talking to you Trap i know it must have already solved but i am actually new here i dont know how can properly learn from the forums may be you people can help me. but lot of thanks for u people for showing concern.

Share this post


Link to post
Share on other sites
I think what jost was talking about is detecting a win/lose condition (correct me if i am wrong) which is needed, but to address your 'heuristic' question, you need to run a search on the search space, effictively by getting the A.I. to simulate the next possible moves..A Heuristic is effectively an estimation or guess on the current state of your world, to hopefully lead the A.I. into making the correct move. (e.g. A* heuristic to estimate distance), What i proposed earlier is the Minimax algorithm, which works out really well in situations where the search space gets smaller and eventually may goto 0. (e.g. Tic-Tac-Toe when all squares are filled, Connect4, etc).

A quick search on Connect4 and Minimax gave sent me to the following link

http://thecodeproject.com/netcf/Connect4AB.asp

I wrote a minimax for tic-tac-toe which is a much smaller search space, and easier to implement the minimax search on, give that a shot for a first run, and then upgrade to connect four
-Syn

Share this post


Link to post
Share on other sites
Quote:
Original post by Syntax
I think what jost was talking about is detecting a win/lose condition (correct me if i am wrong) which is needed, but to address your 'heuristic' question, you need to run a search on the search space, effictively by getting the A.I. to simulate the next possible moves..A Heuristic is effectively an estimation or guess on the current state of your world, to hopefully lead the A.I. into making the correct move.


Oh, I see, a heuristic basically means AI. :P Well in that case.. my Connect Four game had completely random AI so I can't help you (I made it that way because that was what was assigned on the project.. maybe I'll write a Connect Four again someday.. but in the meantime I have to work on Stealth Prankster 2, w00t).

Good luck with your Connect Four game, Syed!

Share this post


Link to post
Share on other sites
well i just use the simplest and quicker method possible. always best just to return a high value for a win, and a low value for a lose. also, i'd make it so that the value is slightly higher for a quick win (depth of win) and slighly lower for a quick lose (depth of win). this works very well for me...

Share this post


Link to post
Share on other sites

This topic is 4671 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this