Need a heuristic for drop four game

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.

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

Will

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.

Alvaro, I never ceased to be amazed by that solution. Absolutely brilliant. Now do one for chess! :D lol.


Will

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.

Minimax with alpha beta pruning

drop four has been solved already and rules for perfect play of the player playing first exist.

I did not know that, where is good information that we can post here, where we can learn more about that.

clicky

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.

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

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!

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