1700540960
1700540961
另有如下3个约束：
1700540962
1700540963
∀j, Σisixij≥dj
1700540964
1700540965
（14.2）
1700540966
1700540967
∀i, Σjxij≤1
1700540968
1700540969
（14.3）
1700540970
1700540971
∀i, j, xij≥0
1700540972
1700540973
（14.4）
1700540974
1700540975
其中式（14.2）规定每个合约规定的总曝光量必须得到满足；式（14.3）表示每类曝光机会选择各个合约的总概率之和应该小于等于1；式（14.4）表达概率xij的非负性。对上述问题求解即可找到一个最优解，当然在总供给量不够的情况下，上面的问题也可能无解，这时需要在式（14.2）中添加一个变量uj，代表合约j的欠曝光量（under-delivery），且约束变更为：Σisixij+uj≥dj。与此同时，在目标函数中也需要加入欠曝光量所带来的惩罚，具体的公式参照文献[51]。
1700540976
1700540977
在竞价广告的模式下，广告投放机根据点击率预估的结果对广告进行排序和选择。对于一个新上线的广告，如果没有充分的曝光，是无法对其点击率做出准确预测的。这时如果我们仅采用利用的方案，会倾向于选择其他点击率更高的广告，或给出一个较低的出价。长此以往，该广告很可能丧失足够的曝光机会，我们也永远无法对其点击率进行合理的估计。因此，我们需要对曝光量不足的广告进行探索，但仅仅采用探索的方案显然也是不行的。对于已有足够曝光量的广告，还是应该遵循点击率预估的结果进行排序、选择和出价。探索与利用是一对矛盾的主体，需要在其间找到平衡，才能达到最佳的投放效果，这也是强化学习所重点关注与解决的问题。在强化学习的场景下，一开始我们并没有足够多的带标注样本，需要与环境进行交互（投放广告），通过获得反馈的方式来改进模型，最终获得一个最优的投放策略。在程序化交易的场景中，需求方平台还需要对选定的广告进行出价，如何优化出价也是一个独立的研究课题，在这里就不展开了，有兴趣的读者可以参考文献[52]。
1700540978
1700540979
综上所述，计算广告的相关算法几乎包含了本书介绍内容的方方面面。要想成为一个优秀的广告算法工程师，除了熟练掌握业务流程之外，还要为各类算法、理论和方法打好坚实的基础，并在实践中不断掌握算法优化的经验。在面试中，关于理论、方法、实践经验等相关的问题都会涉及，所以也请各位读者能够认真阅读前面的面试题和解答，为以后的工作打下坚实的基础。
1700540980
1700540981
1700540982
1700540983
1700540984
百面机器学习：算法工程师带你去面试 [:1700532254]
1700540985
百面机器学习：算法工程师带你去面试 02 游戏中的人工智能
1700540986
1700540987
1700540988
1700540989
自人类文明诞生起，就有了游戏。游戏是人类最早的集益智与娱乐为一体的活动，传说四千年前就有了围棋。几个世纪以来，人们创造出不计其数的各类游戏，比如象棋、国际象棋、跳棋、扑克、麻将、桌游等。半个多世纪前，电子计算机技术诞生，自此游戏焕发了新貌。1980年前后，电视游戏（Video Game）和街机游戏（Arcade Game）开始进入人们视线，当时还是一个小众活动。20世纪90年代，你是否还记得风靡街头的游戏机厅，以及走进千家万户的小霸王学习机。然后，个人计算机的普及将游戏带入了一个崭新的时代。当前，电子游戏不限于电脑，手机、平板等各类带屏平台都被游戏一一拿下。2010年，游戏已是数千亿美元的产业，全球市场利润远超其他娱乐业。
1700540990
1700540991
现在，定义游戏的边界不再清晰。周末聚一帮好友吃着串玩狼人杀，是一种游戏；深夜与千里之外素不相识的网友，组织一小队去做任务，也是一种游戏。然而游戏不只有娱乐功能，还可以教孩子学英文、帮新兵熟悉战场环境，游戏营造出的奖励机制和现场体验，让学习过程事半功倍。心理学家认为，人们玩游戏时的娱乐体验，构建在智力活动之上。游戏中层层关卡设计，代表不同级别的智力难度，玩家在过关之前，需要投入一定的脑力，观察、思考、实验、学习并动用过去积累的常识知识。这种对智力逐级考察并及时奖励的过程，是我们产生愉悦感的来源，也是游戏和智能密不可分的联系。
1700540992
1700540993
■ 游戏AI的历史
1700540994
1700540995
早在人工智能处于萌芽期，先驱们就产生用计算机解决一些智力任务的想法。人工智能之父——阿兰·图灵很早就从理论上提出用MiniMax算法来下国际象棋的思路[53]。
1700540996
1700540997
第一款成功下棋的软件诞生于1952年，记录在道格拉斯的博士论文中，玩的是最简单的Tic-Tac-Toe游戏（见图14.10（a））。几年后，约瑟夫塞·缪尔开发出下西洋跳棋（见图14.10（b））的软件，是第一款应用机器学习算法的程序，现在这个算法被人们称为强化学习。在早期的游戏中，AI都集中在解决经典棋类游戏的问题上，人们相信人类挑战了几百年甚至上千年的游戏，必定是人类智能的精华所在。然后，三十年的努力，人们在树搜索技术上取得突破。1994年，乔纳森·斯卡费尔的西洋跳棋程序Chinook打败了人类冠军马里恩·汀斯雷[54]；2007年，他在《科学》杂志宣布“Checkers is solved”（西洋跳棋已被攻克）[55]。
1700540998
1700540999
1700541000
1700541001
1700541002
（a）Tic-Tac-Toe游戏
1700541003
1700541004
1700541005
1700541006
1700541007
（b）西洋跳棋
1700541008
1700541009
