Questions tagged [heuristics]

In AI, the term "heuristic" is used in the context of non-blind (i.e., informed) search and planning: the problem of finding a sequence of actions to find/generate a desired state from an initial state. Heuristics" are problem relaxations of the original problem. They get as input the current state/search node and output the cost of the relaxed solution from there to goal. This heuristic value is then used for search guidance.

Filter by
Sorted by
Tagged with
0
votes
0answers
10 views

Tweaking MCTS to account for opponent knowing the state of the game

I'm making an artificial intelligence for a card game using MCTS. With a standard 52-cards deck, 4 hands are dealt: 1 for each of the 3 players and one extra hand. Then, each player gets the choice to ...
1
vote
0answers
38 views

Is the minimum and maximum of a set of admissible and consistent heuristics also consistent and admissible?

Let's suppose I have a set of heuristics $S$ = {$h_1, h_2, ..., h_n$}. If all heuristics in $S$ are admissible, does that mean that a heuristic that takes the $MIN(S)$ (or $MAX$ for that matter) is ...
2
votes
1answer
47 views

Admissible and consistent heuristics

I am wondering about a problem that I was given to solve: Given circular trail divided by n segments(n>2) labeled 0..n-1. In the beginning an agent is at the start of segment number 0 (the edge ...
2
votes
1answer
93 views

Why Nilsson's Sequence Score isn't an admissible heuristic?

I understand what an admissible heuristic is, I just don't know how to tell if one heuristic is admissible or not. So, in this case, I'd like to know why Nilsson heuristic isn't admissible.
2
votes
3answers
162 views

Heuristic function for BayesChess

I am reading BayesChess: A computer chess program based on Bayesian networks (Fernandez, Salmeron; 2008) It is a chess playing engine using Bayesian networks. The following is mentioned about ...
4
votes
1answer
40 views

What kind of decision rule algorithm is usable in this situation?

I am trying to write an AI to a game, where there is no real adversary. This means, that only the AI player has choices in which move to perform, his opponent may or may not react to the move the AI ...
1
vote
2answers
790 views

What heuristic to use when doing A* search with multiple targets?

The problem of multi-goal path planning was introduced in an ICRA paper in the year 2011: “Multi-goal planning is a task which arises in many robotics applications. It combines the challenging ...
5
votes
2answers
290 views

More effective way to improve the heuristics of an AI… evolution or testing between thousands of pre-determined sets of heuristics?

I'm making a Connect Four game where my engine uses Minimax with Alpha-Beta pruning to search. Since Alpha-Beta pruning is much more effective when it looks at the best moves first (since then it can ...
0
votes
1answer
851 views

How do you calculate the heuristic value in this specific case?

The A* algorithm uses the "evaluation function" $f(n) = g(n) + h(n)$, where $g(n)$ = cost of the path from the start node to node $n$ $h(n)$ = estimated cost of the cheapest path from $n$ to the ...
4
votes
1answer
122 views

Why has the General problem solver failed?

I'm reading currently through the old papers of Allen Newell and Herbert Simon in the late 1950s about their project to build a general problem solver. As far as i understand the concept of operators ...
5
votes
1answer
4k views

Admissible/Consistent Heuristic Theorems

I understand that a heuristic is admissible if it never overestimates the true cost to reach the goal node from n. I also understand that if a heuristic is consistent then the heuristic value of n is ...
3
votes
1answer
197 views

Snake path finding variant : Algorithm choice

I am working on a project which maps to a variant of path finding problem. I am new to this area and I would be very grateful if you could give suggestions/ point to libraries for relevant algorithms. ...
1
vote
0answers
17 views

Approach for data transformation needed

I am looking for an algorithm to transform an input data to a goal data using a series of operations. The shorter the series the better. The following is known: the input data the goal data input ...
2
votes
0answers
45 views

How to open up a rigid structure made of connected panels?

By open up I mean slightly open up so that a theoretical structure of panels with no width looks three-dimensional. The original structure being an ideal object where any number several panels can ...
3
votes
1answer
444 views

How do I write a good evaluation function?

I'm currently writing an Alpha-Beta-Pruning algorithm for a board game. Now I need to come up with a good evaluation function. The game is a bit like snakes and ladders (you have to finish the race ...
2
votes
2answers
376 views

Evaluation Function for a Go like game

I am trying to find a good evaluation function for a game with: A 7x7 tile board 2 players, given equal number(>=3 currently undetermined) of stones placed randomly on the tiles A turn is consisted ...
11
votes
1answer
156 views

Strategic planning and multi dimensional knapsack problem

I'm trying to find a planning approach to solve a problem that attempts to model learning of new material. We assume that we only have one resource such as Wikipedia, which contains a list of articles ...
3
votes
1answer
1k views

Blocks world Game: A* heuristic solution approach

I am developing a heuristic solution for blocks world problem. I tried using number of blocks out of place as my h(n). It seems little ineffective. Can someone please point out a suitable heuristic ...
1
vote
0answers
671 views

Has Tic-Tac-Toe been solved with a single heuristic?

By this I mean a single axiom for placement. (I'm working on a solution that involves positional valuation and vectors, and appears to be solid, but my assumption would be this has been done ...
4
votes
1answer
61 views

What are state-of-the-art ways of using greedy heuristics to initially set the weights of a Deep Q-Network in Reinforcement Learning?

I am interested in the current state-of-the-art ways to use quick, greedy heuristics in order to speed up the learning in a Deep Q-Network in Reinforcement Learning. In classical RL, I initially set ...
2
votes
0answers
68 views

Reproduce Firefly Algorithm experiments of original paper?

I have been trying to reproduce the experiments done in the original: "Firefly Algorithm for multimodal optimization" (linked in the question) so far: unsuccesfully. For the moment being I'm okay if ...
5
votes
2answers
155 views

How does A* search work given there are (more than) two goal states?

When I have read through the fundamentals of AI, I saw a situation (i.e., a search space) which is illustrated in the following picture. These are the heuristic estimates: ...
2
votes
0answers
35 views

Knapsack of mixture with constraints

I'm trying to find the optimized mixture for a specific set of substances. Each of those substances have characteristics that I want to optimize in the mixture (some characteristics I want to minimize ...
3
votes
3answers
57 views

Is a subset of a problem solution, used to recreate complete solution considered a heuristic?

This is a question about a nomenclature - we already have the algorithm/solution, but we're not sure whether it qualifies as utilizing heuristics or not. feel free to skip the problem explanation: ...
12
votes
6answers
398 views

Are methods of exhaustive search considered to be AI?

Some programs do exhaustive searches for a solution while others do heuristic searches for a similar answer. For example, in chess, the search for the best next move tends to be more exhaustive in ...