`

对于A*算法、alpha-beta算法的思考

阅读更多
A* 算法以估值函数为核心。
alpha-beta 以剪枝为核心。简单的说就是把比已知的一步棋更臭的棋剪掉。

现在我希望寻求某个问题接下来几步的最优解,蛮力计算是不可行的。A* 的准确性较差。但这本身不是一个博弈情况,所以alpha-beta不适用,只能期望于一种比较好的搜索算法。

正在构思一种逆A*算法。A*算法以价值为中心,逆A* 算法以代价(cost)为中心。
A* 算法采用宽度搜索获取最优解。逆A* 算法采用深度搜索。

部分代码冗余,在任何步骤都不足以满足目标价值时
一个lua的实现
local currentcost;
local wantedvalue;
local maxvalue,mincost,maxrate =0,0,0
local statusmap;--状态图,棋盘
local callcount;
routes={};
if table.getn == nil then
	local fun, err = loadstring("return function(tb) return #tb end")
	table.getn = fun()
end 
--depth 最大限制深度
--value 目标价值
-- cost 花费
--return: min cost,max value
--TODO: jstar(map,depth) return routes,状态空间对应的路由是确定的 
function jstar(depth,needvalue,costed)
     
	if(depth<=0)then
		--计算maxvalue,未实现,重要
		return 0
	end
	callcount=callcount+1;
	local actions = getActions(map);
	for i=1,table.getn(actions) do
		a = actions[i]
		v = needvalue - getValue(a);
		c = getCost(a)+costed;
		if(v <=0 )then
			if( c < mincost)then
				mincost=c;
				exec(map,a)
				routes={}
				--clone
				for j=1,table.getn(map.routing) do
					routes[j]=map.routing[j]
				end
				routes.cost=c
				routes.value=v
				undo(map)
			end
		elseif(c<mincost)then
			exec(map,a)
			jstar(depth-1,v,c)
			undo(map)
		--else 则超出最优解范围,忽略
		end
	end
end

local testzb={{2,3,1},{4,5,1},{3,5,1},{4,7,1},{2,9,1},{300,100,1},{8,9,2},{10,10,1}}
map={}
map.current={5,5}
map.routing={}
--获取所有可能的点
function getActions(m)
	ac={}
	for i=1,table.getn(testzb) do
		f=true
		for j=1,table.getn(m.routing) do
			if(map.routing[j]==i)then f=false;break;end
		end
		if(f)then
			table.insert(ac,i)
		end
	end
	return ac
end
														   
function exec(m,action)
	m.old=map.current;
	m.current=testzb[action]
	table.insert(m.routing,action)
end

function undo(m)
	if(table.getn(m.routing)==1)then 
		m.current={5,5} 
	else
		m.current=testzb[m.routing[table.getn(m.routing)-1]]
	end
	
	table.remove(m.routing,table.getn(m.routing))
end

function getValue(a)
	return testzb[a][3]
end

function getCost(a)
	dx = map.current[1]-testzb[a][1]
	dy = map.current[2]-testzb[a][2]
	return math.sqrt(dx*dx+dy*dy)
end

--执行jstar算法,初始参数深度
function  start(depth,w)
  wantedvalue=w;
  maxvalue=0;
  mincost=1000000000;
  callcount=0;
  jstar(depth,wantedvalue,0);
  print(callcount);
end

start(5,5)
print(callcount)
print(table.concat(routes,','))

分享到:
评论

相关推荐

    人工智能小项目,2048棋盘游戏,Alpha-beta剪枝算法, Expectimax搜索

    **Alpha-beta剪枝算法**:这是一种用于优化最小化-最大化搜索的策略,常用于棋类游戏。在2048游戏中,计算机需要预测每个可能的移动,并评估其结果。Alpha代表当前找到的最好结果的最大值,而Beta则代表当前找到的最...

    Python使用Min-max算法和Alpha-Beta剪枝的黑白棋游戏AI代码 Pygame可视化

    # Python使用Min-max算法和Alpha-Beta剪枝的黑白棋游戏AI代码 Pygame可视化 本项目是基于pygame实现的黑白棋(翻转棋)游戏,通过Min-max算法和Alpha-Beta剪枝实现人工智能对手。 使用方法: 1. 安装 pygame: $ pip...

    alpha-beta算法 一字棋

    而Alpha-Beta算法引入了两个值,Alpha代表当前搜索路径上的最大已知价值(对于Max节点),Beta代表最小已知价值(对于Min节点)。通过比较Alpha和Beta值,当发现某分支不可能产生更好的结果时,就进行剪枝,避免无用...

    alpha-beta剪枝算法实现中国象棋人机对战

    使用alpha-beta剪枝算法实现中国象棋人机对战,AI具有中级的智能,可以应对一般的象棋爱好者。

    JS五子棋AI,源码+教程,基于Alpha-Beta剪枝算法(不是神经网络).zip

    JS五子棋AI,源码+教程,基于Alpha-Beta剪枝算法(不是神经网络) JS五子棋AI,源码+教程,基于Alpha-Beta剪枝算法(不是神经网络) JS五子棋AI,源码+教程,基于Alpha-Beta剪枝算法(不是神经网络) JS五子棋AI,...

    象棋ai算法Alpha-Beta

    本项目采用C++编程语言实现了一个具有较高智能的单机AI,它采用了经典的Alpha-Beta剪枝算法来优化搜索策略,使得电脑棋手能够进行高效而精准的决策。 Alpha-Beta剪枝算法是基于Minimax树搜索的一种优化方法,主要...

    alpha-beta剪枝五子棋

    本文将深入探讨“alpha-beta剪枝五子棋”的实现及其与贪心算法的结合。 五子棋是一种策略性游戏,两个玩家轮流在棋盘上下棋,目标是形成连续的五个棋子线(横向、纵向或对角线)。由于五子棋的所有可能状态数量巨大...

    人工智能alpha-beta剪枝

    在人工智能领域,搜索算法是解决问题的关键技术之一,而Alpha-Beta剪枝是其中最著名、最高效的优化策略,尤其在棋类游戏的决策过程中。它结合了Alpha(α)和Beta(β)两个值,用于在多层深度优先搜索中避免无效的...

    精选_基于alpha-beta剪枝博弈树算法实现的一字棋游戏_源码打包

    在这个基于alpha-beta剪枝的博弈树算法实现中,我们深入探讨如何利用计算机科学中的智能算法来创建一个能与玩家对战的智能系统。本文将详细介绍alpha-beta剪枝算法及其在一字棋游戏中的应用。 首先,我们要理解博弈...

    alpha-beta_as_line2ine_alphabeta_Frame_

    5. **实现细节**:包括代码示例,展示如何在实际编程中应用线性化的Alpha-Beta算法。 6. **性能分析**:对比线性化方法与传统递归方法的性能,可能包含实验数据和图表,以证明优化的有效性。 7. **应用场景**:...

    [人工智能]alpha-beta剪枝算法及实践.pdf

    【人工智能】Alpha-Beta剪枝算法是用于解决博弈树搜索问题的一种优化方法,特别是在棋类游戏AI中广泛应用。它是极大极小搜索算法的改进版,旨在提高搜索效率,减少不必要的计算分支。 **算法原理** Alpha-Beta剪枝...

    几个变形的Alpha-Beta搜索算法(很经典)

    Alpha-Beta 搜索算法是一种经典的优化版的最小-最大搜索策略,主要用于解决决策树型问题,特别是棋类游戏中的最佳走法选择。该算法源于最小-最大搜索,但通过剪枝技术显著提高了效率。 最小-最大搜索算法的核心是...

    简单的alpha-beta剪枝算法

    Alpha-beta剪枝是一种在棋盘游戏中优化搜索策略的算法,它是Minimax算法的改进版本,用于减少不必要的计算,提高搜索效率。在这个简单的alpha-beta剪枝算法中,我们将深入理解其原理、实现步骤以及如何构建搜索树。 ...

    人工智能小游戏-基于alpha-beta剪枝算法实现的五子棋源码

    is used to build a single project or subproject. Other users can share the project (.dsp) file, but they should export the makefiles locally. fir.h This is the main header file for the application...

    一篇讲alpha-beta 剪枝及其算法分析的论文

    Alpha-Beta 剪枝是一种在博弈树搜索算法中用来减少必须评估节点数量的技术,常用于计算机游戏如国际象棋和围棋等。其基本思想是在Minimax搜索树的过程中,根据已搜索到的极值来剪去那些不可能成为最终最优决策的节点...

    C# alpha-beta 剪枝五子棋AI 算法

    《C#实现的Alpha-Beta剪枝五子棋AI算法详解》 在计算机科学领域,游戏AI的设计一直是吸引人们兴趣的焦点。其中,五子棋作为一款策略性较强的棋类游戏,其AI开发更是挑战性十足。本篇文章将深入探讨如何使用C#编程...

    极大极小值搜索-基于alpha-beta剪枝算法的AI五子棋人机博弈游戏python源码.zip

    极大极小值搜索-基于alpha-beta剪枝算法的AI五子棋人机博弈游戏python源码.zip极大极小值搜索-基于alpha-beta剪枝算法的AI五子棋人机博弈游戏python源码.zip极大极小值搜索-基于alpha-beta剪枝算法的AI五子棋人机...

    基于ALPHA-BETA算法的五子棋程序

    《基于ALPHA-BETA算法的五子棋程序详解》 在人工智能领域,游戏是一个极佳的测试平台,其中五子棋作为经典的二人对弈游戏,因其规则简单却变化多端,成为了研究算法的重要载体。本篇文章将深入探讨一个基于ALPHA-...

    JS五子棋AI源码+项目说明+教程(基于Alpha-Beta剪枝算法(不是神经网络)).zip

    【资源说明】 1、该资源包括项目的全部源码,下载可以直接使用! 2、本项目适合作为计算机、数学、电子信息等专业的课程设计、期末大...JS五子棋AI源码+项目说明+教程(基于Alpha-Beta剪枝算法(不是神经网络)).zip

Global site tag (gtag.js) - Google Analytics