Teachnique for Heuristic

[zak100]

Hi,

I am creating a two board game. Kindly guide me about a simple technique related to Heuristics.If possible kindly tell me about pruning. I have 8 pieces on both sides. I am thinking to move 3 pieces of both ends together and keep two pieces fixed. Is this a good idea for Heuristics

 

Zulfi.

[Ghideon]

6 hours ago, zak100 said:

Kindly guide me about a simple technique related to Heuristics.

An initial step in this case could be to understand the Hill Climbing* algorithm. Hill Climbing algorithm is straight forward and different variants are available making it easier to discuss the difference between heuristics. Once the basics are understood we may introduce minimax algorithm that is useful in two player games. 

6 hours ago, zak100 said:

If possible kindly tell me about pruning.

Alpha-Beta pruning goes well together with minimax algorithm.

 

6 hours ago, zak100 said:

I have 8 pieces on both sides. I am thinking to move 3 pieces of both ends together and keep two pieces fixed. Is this a good idea for Heuristics

No. The heuristic you use to find an answer to your questions are not the best idea. You are posting too few details resulting in too much guesswork and/or many skilled members opting not to enter the discussion at all. There are too much room for misunderstanding and discussion progress slowly. 

In this specific case; how would one know what is a good vs a bad heuristic without having a clue about the rules of the game and the conditions for winning the game? Or are you maybe asking about the much more general case; two player games and heuristics in general? 
 

 

*) I know from other posts that OP has specific interest in understanding that specific algorithm, that's why I pick that as a first option in this case. It is not necessarily the optimal choice in a more general context. The level of assumed background knowledge have an impact on recommendations.

 

Edited October 8, 2020 by Ghideon

[Ghideon]

22 hours ago, zak100 said:

I am creating a two board game.

Had some time for a followup, here is a short introduction to minimax. 

Minimax is a kind of backtracking algorithm that is used to find the optimal move for a player “A”, assuming that the opponent player “B” also plays optimally. It can be used in two player turn-based games such as Tic-Tac-Toe.

Every board state has an associated value. A positive value means the board is in favour of player A, for instance if A has a stronger position in Tic-Tac-Toe. Negative values means player B has the upper hand. The values of the board states are calculated by some heuristics which are unique for every type of game. 

In Minimax the two players A and B are called maximiser and minimiser. The algorithm, when starting from some state where it is player A's turn, will assume that A will make the move that maximises the value associated with the next step. In the next level in the search tree the algorithm will assume player B makes the move that minimises the associated value. This goes on until a final winning state is found or some optimisation stops the search. (out of scope for this discussion) 

Due to the backtracking the algorithm will reject moves that initially looked good but later turned bad. An example being a chess move where A threatens B’s king but opens up for B to move into an even better position for instance a check mate. 

Typically the search tree may be too large so that the algorithm can’t evaluate all possible future moves more than a limited amount of steps ahead from the current state.

Initial questions:  Is your game turn based? Is luck involved (for instance a dice rolling)

Note that the topic in the opening post is very broad (ind interesting!). Answering this in detail requires writing considerable amount of text, maybe better suited for a book.
 

Edited October 9, 2020 by Ghideon

[zak100]

Hi,

Thanks a lot. I would try with my approach right now because time is too short for submission. But I want to learn how we can apply heuristic based upon minimax or HCA (Hill climbing Alg). Hope we may continue this discussion. I have example of Tic Toe but can't understand how minimax works for it.

 

Zulfi.

[Ghideon]

On 10/9/2020 at 3:19 PM, zak100 said:

Hope we may continue this discussion

That is indeed possible, just contribute something that allows for an interesting conversation.